各種排序算法比較

1、排序算法專題- -排序算法一、插入排序(Insertion Sort)1.基本思想：每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。2.排序過程:廿【示例】：初始關鍵字49 38 65 97 76 13 27 49J=2(38) 38 49 65 97 76 13 27 49J=3(65) 38 49 65 97 76 13 27 49J=4(97) 38 49 65 97 76 13 27 49J=5(76) 38 49 65 76 97 13 27 49J=6(13) 13 38 49 65 76 97 27 49J=7

2、(27) 13 27 38 49 65 76 97 49J=8(49) 13 27 38 49 49 65 76 97Procedure In sertSort(Var R : FileType);Begi nfor I := 2 To N Do beginR0 := RI; J := I - 1;While R0 RJ Do beginRJ+1 := RJ;J := J - 1endRJ + 1 := R0;endEnd;/對R1.N按遞增序進行插入排序，R0是監(jiān)視哨/依次插入 R2,.,Rn查找RI的插入位置/將大于RI的元素后移/插入 RI /In sertSort /二、選擇排序1.基

3、本思想：每一趟從待排序的數據元素中選出最小(或最大)的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。2.排序過程:【示例】：初始關鍵字 49 38 65 97 76 13 27 49 第一趟排序后 13 : 38 65 97 76 49 27 49 第二趟排序后1327 : 65 97 76 49 38 49第三趟排序后1327 38 97 76 49 65 49第四趟排序后1327 38 49 49 97 65 76第五趟排序后1327 38 49 49 97 97 76第六趟排序后13 2738 49 4976 76 97第七趟排序后13 2738 49 4976

4、76 97最后排序結果13 2738 49 4976 76 97Procedure SelectSort(Var R : FileType);Begi nfor I := 1 To N - 1 DobeginK := I;For J := I + 1 To N DobeginIf RJ RK Then K := J/對R1.N進行直接選擇排序/做N - 1趟選擇排序/在當前無序區(qū) RI.N中選最小的元素 RKen d;If K I Then/交換 RI和 RK /begi n Temp := RI; RI := RK; RK := Temp; end;endEnd./SelectSort /三

5、、冒泡排序(BubbleSort)基本思想：兩兩比較待排序數據元素的大小，發(fā)現兩個數據元素的次序相反時即進行交換， 直到沒有反序的數據元素為止。排序過程：設想被排序的數組 R : 1.N 垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則， 從下往上掃描數組R,凡掃描到違反本原則的輕氣泡，就使其向上漂浮，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止?？凇臼纠浚?9 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97

6、65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97Procedure BubbleSort(Var R : FileType) / 從下往上掃描的起泡排序 /BeginFor I := 1 To N-1 Do/做 N-1 趟排序 /beginNoSwap := True;置未排序的標志/For J := N - 1 DownTo 1 Do/從底部往上掃描 /beginIf RJ+1 RJ Then/交換元素 /beginTemp := RJ+1; RJ+1 := RJ; R

7、J := Temp;NoSwap := Falseen d;en d;If NoSwap Then Return endII本趟排序中未發(fā)生交換，則終止算法/End./BubbleSort/四、計數排序計數排序的思想是若待排序的記錄的關鍵字在一個明顯的有限范圍內 (整數)時，可設計 個數組，出現與數組下標值一樣的數，該下標的數組元素值加1 ，最后掃描整個數組，根據 統(tǒng)計的信息給出一個有序數列。五、快速排序(Quick Sort )基本思想：在當前無序區(qū)R1.H中任取一個數據元素作為比較的”基準(不妨記為X)，用此基準將 當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R1.l-1和RI+1.H，且左邊的

8、無序子區(qū)中數據元素均小于等于基準元素，右邊的無序子區(qū)中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R1.l-1 X.KeyW RI+1.H(1 1齊當R1.l-1和RI+1.H均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數據元素均已排序為止。排序過程：Q【示例】：初始關鍵字 49 38 65 97 76 13 27 49 :第一次交換后27 38 65 97 76 13 49 49 :第二次交換后27 38 49 97 76 13 65 49 :J向左掃描，位置不變，第三次交換后27 38 13 97 76 49 65 49:I向右掃描，位置不變，第四次交換后

9、27 38 13 49 76 97 65 49:J 向左掃描 27 38 13 49 76 97 65 49 :(一次劃分過程)初始關鍵字 49 38 65 97 76 13 27 49 :一趟排序之后27 38 13: 49 : 76 97 65 49 :二趟排序之后13 27 :38 49 : 49 65: 76 :97三趟排序之后13 27 38 49 49 : 65 76 97最后的排序結果13 27 38 49 49 65 76 97各趟排序之后的狀態(tài)Procedure Partti on( Var R : FileType; L, H : In teger; Var I : In

10、teger);對無序區(qū)R1,H做劃分，I給以出本次劃分后已被定位的基準元素的位置/BeginI := 1; J := H; X := RI;初始化，X 為基準 /RepeatbeginJ := J - 1If I = X) And (I J) Do從右向左掃描，查找第 1個小于X的元素/ 已找到 RJ X/beginRl:-RJ;相當于交換 RI和RJI := I+ 1end;While (RI-X) And (I J) DoI := I+ 1從左向右掃描，查找第1個大于X的兀素/en d;If I X /beginRJ :- RI;/相當于交換 RI和 RJ/J := J-1endUn ti

11、l I = J5RI := X/基準X已被最終定位/End;/Parttion /Procedure QuickSort(Var R :FileType; S,T: Integer); / 對 RS.T快速排序 / BeginIf S T Then /當RS.T為空或只有一個元素是無需排序/beginPartion(R, S,T, I);對 RS.T做劃分/QuickSort(R,S, I-1);/ 遞歸處理左區(qū)間RS,l-1QuickSort(R,I+1,T);遞歸處理右區(qū)間RI+1.T /en d;End./QuickSort/六、幾種排序算法的比較和選擇選取排序方法需要考慮的因素：待排序

12、的元素數目n;元素本身信息量的大??；關鍵字的結構及其分布情況；語言工具的條件，輔助空間的大小等。小結：若n較小(n .87879.332 *6.785 33242堆排序000.0310.1090.0310.015直接插入排序00.0478.70557.800024.865Shell排序000.0470.1100.0150.015歸并排序000.0310.0940.0320.032基數排序000.470.1090.0470.046算法與結果聯合分析冒泡排序：在最優(yōu)情況下只需要經過n- 1次比較即可得出結果，(這個最優(yōu)情況那就是序列己是正序，從 100K的正序結果可以看出結果正是如此)，但在最壞情

13、況下，即倒序(或一個較小值在最后)，下沉算法將需要n(n-1)/2 次比較。所以一般情況下，特別是在逆序時，它很不理想。它是對數據有序性非常敏感的排序算法。冒泡排序2:它是冒泡排序的改良(一次下沉再一次上浮)，最優(yōu)情況和最壞情況與冒泡排序差不多，但是一般情況下它要好過冒泡排序，它一次下沉，再一次上浮，這樣避免了因一個數的逆序，而造成巨大的比較。如(2,3,4, , ,n- 1,n,1 )，用冒泡排序需要n(n-1)/2 次比較，而此排序只要 3輪，共比較(n-1)+(n-2)+(n-3)次，第一輪1將上移一位，第二輪1將 移到首位，第三輪將發(fā)現無數據交換，序列有序而結束。但它同樣是一個對數據有

14、序性 非常敏感的排序算法，只適合于數據基本有序的排序?？焖倥判颍核瑯邮敲芭菖判虻母倪M，它通過一次交換能消除多個逆序，這樣可以減 少逆序時所消耗的掃描和數據交換次數。在最優(yōu)情況下，它的排序時間復雜度為O (nlog2n)。即每次劃分序列時，能均勻分成兩個子串。但最差情況下它的時間復雜度將是O(nA2)。即每次劃分子串時，一串為空，另一串為m-1 (程序中的100K正 序和逆序就正是這樣，如果程序中采用每次取序列中部數據作為劃分點，那將在正序和逆時達到最優(yōu))。從100K中正序的結果上看“快速排序”會比“冒泡排序”更慢，這主要是“冒泡排序”中采用了提前結束排序的方法。有的書上這解釋“快速排序”，在

15、理論上講，如果每次能均勻劃分序列， 它將是最快的排序算法，因此稱它作快速排序。雖然很難均勻劃分序列，但就平均性能而言，它仍是基于關鍵字比較的內部排序算法中速度最快者。直接選擇排序：簡單的選擇排序，它的比較次數一定：n(n- 1)/2。也因此無論在序列何種情況下，它都不會有優(yōu)秀的表現(從上100K的正序和反序數據可以發(fā)現它耗時相差不多，相差的只是數據移動時間)，可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發(fā)現它在一般情況下將快于冒泡排序。堆排序：由于它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完 成排序的總比較次數為O (nlog2n)。它是對數

16、據的有序性不敏感的一種算法。但堆排序將需要做兩個步驟：-是建堆，二是排序(調整堆)。所以一般在小規(guī)模的序列中不合適，但對 于較大的序列，將表現出優(yōu)越的性能。直接插入排序：簡 單的插入排序，每次比較后最多移掉一個逆序，因此與冒泡排序的 效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值 移動，所以直接插入排序將要優(yōu)于冒泡排序。直接插入法也是一種對數據的有序性 非常敏感的一種算法。在有序情況下只需要經過 n-1次比較，在最壞情況下，將需要n(n-1)/2 次比較。希爾排序：增量的選擇將影響希爾排序的效率。但是無論怎樣選擇增量，最后一定要 使增量為1,進行一次直接

17、插入排序。但它相對于直接插入排序，由于在子表中每進行一次 比較，就可能移去整個經性表中的多個逆序，從而改善了整個排序性能。希爾排序算是一種基于插入排序的算法，所以對數據有序敏感。歸并排序：歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在 使用它對兩個己有序的序列歸并，將有無比的優(yōu)勢。其時間復雜度無論是在最好情況下還是在最壞情況下均是 0(nlog2n)。對數據的有序性不敏感。若數據節(jié)點數據量大，那將不適合。 但可改造成索引操作，效果將非常出色?；鶖蹬判颍涸诔绦蛑胁捎玫氖且詳抵档氖M制位分解，然后對空間采用一次性分配， 因此它需要較多的輔助空間 (10* n+10),(但我們可以

18、進行其它分解，如以一個字節(jié)分解， 空間采用鏈表將只需輔助空間n+256)?；鶖蹬判虻臅r間是線性的(即0(n)。由此可見，基數排序非常吸引人，但它也不是就地排序，若節(jié)點數據量大時宜改為索引排序。但基數排序有個前提，要關鍵字能象整型、字符串這樣能分解，若是浮點型那就不行了。按平均時間將排序分為類：2平方階(0(n )排序各類簡單排序，例如直接插入、直接選擇和冒泡排序；線性對數階(0(nlog2n)排序如快速排序、堆排序和歸并排序；1+ 0(n)排序是介于0和1之間的常數。希爾排序便是一種；線性階(0(n)排序本程序中的基數排序，此外還有桶、箱排序。排序方法的選擇因為不同的排序方法適應不同的應用環(huán)境和要求，所以選擇合適的排序方法很重要若n較小，可采用 直接插入 或直接選擇排序。當記錄規(guī)模較小時，直接插入排序較好，它會比選擇更少的比較次數；但當記錄規(guī)模較大時，因為直接選擇移動的記錄數少于直接插人，所以宜用選直接選擇排序。這兩種都是穩(wěn)定排序算法。若文件初始狀態(tài)基本有序(指正序)，則應選用 直接插人、冒泡或隨機的快速排序 為宜(這里的隨機是指基準取值的隨機，原因見上的快速排序分析)；這里快速排序算法將不穩(wěn)定。若n較大，則應采用時間復雜度為 0(nlog