정렬 알고리즘 시간 복잡 도, 안정성 비교

본문 전재:http://blog.163.com/baicai_xiao/blog/static/190202407201162592126982/
작 가 는 총 결 이 잘 되 어 총 결 을 하지 않 고 바 뀌 었 다.
각종 정렬 알고리즘 의 안정성 과 시간 복잡 도 소결
정렬, 빠 른 정렬, 힐 정렬, 쌓 기 정렬 이 안정 적 인 정렬 알고리즘 이 아 닙 니 다.
거품 정렬, 삽입 정렬, 병합 정렬 과 기수 정렬 은 안정 적 인 정렬 알고리즘 입 니 다.

        ，        O(n ^2)。  

 2.2     （Selection Sort）   

                     n-1    ， i     L[i..n]     L[i]    。  ，  i     ， i             。            ，      O(n ^2 )。   

2.3      （Insertion Sort）   

          ，  i-1    ,L[1..i-1]    。 i     L[i]  L[1..i-1]     ，  L[1..i]         。       ，            。    L[i] L[i-1]，  L[i-1]≤ L[i]， L[1..i]    ， i       ；    L[i] L[i-1]   ，    L[i-1] L[i-2]，         j(1≤j≤i-1)，  L[j] ≤L[j+1]   。 1    4            ，   (a),(b),(c)    。             ，        O(n ^2) 。  

2.4       

            ，      ， A[n]               ，                                。           ，       O(nlog n)。   

2.5        

      （  ）                ，    A[l..m]，A[m+1..h]，            ，    A[l..h]。                            O(nlog2n)。   

2.6        

                 。              ，                。      ，                    ，              1。          ，       （       ）         ，        。                  ，                。            ，            O(nlog2n)，  O(n ^2)。  

2.7       

          ，       ，        1   ，                 。          （     ）  ，             ，                  。D.L.shell 1959                     。                d     ，          d.            ，               ，         。     1 ，            ，    。           ，       O(n ^2)。