各種排序算法的總結和比較

1、各種排序算法的總結和比較快速排序（ QuickSort ）快速排序是一個就地排序，分而治之，大規(guī)模遞歸的 算法。從本質上來說，它是歸并排序的就地版本?？?速排序可以由下面四步組成。（1 ） 如果不多于 1 個數據，直接返回。（2 ） 一般選擇序列最左邊的值作為支點數據。（3 ） 將序列分成 2 部分，一部分都大于支點數據， 另外一部分都小于支點數據。（4 ） 對兩邊利用遞歸排序數列?？焖倥判虮却蟛糠峙判蛩惴ǘ家臁１M管我們可以在 某些特殊的情況下寫出比快速排序快的算法，但是就 通常情況而言，沒有比它更快的了。快速排序是遞歸 的，對于內存非常有限的機器來說，它不是一個好的 選擇。歸并排序（ Me

2、rgeSort ） 歸并排序先分解要排序的序列，從 1 分成 2 ，2 分成 4 ，依次分解，當分解到只有 1 個一組的時候，就可 以排序這些分組，然后依次合并回原來的序列中，這 樣就可以排序所有數據。合并排序比堆排序稍微快一 點，但是需要比堆排序多一倍的內存空間，因為它需 要一個額外的數組。堆排序( HeapSort )堆排序適合于數據量非常大的場合(百萬數據)。堆排序不需要大量的遞歸或者多維的暫存數組。這對 于數據量非常巨大的序列是合適的。比如超過數百萬 條記錄，因為快速排序，歸并排序都使用遞歸來設計 算法，在數據量非常大的時候，可能會發(fā)生堆棧溢出 錯誤。堆排序會將所有的數據建成一個堆，最

3、大的數據在堆 頂，然后將堆頂數據和序列的最后一個數據交換。接 下來再次重建堆，交換數據，依次下去，就可以排序 所有的數據。Shell 排序( ShellSort )Shell 排序通過將數據分成不同的組，先對每一組進 行排序，然后再對所有的元素進行一次插入排序，以 減少數據交換和移動的次數。 平均效率是 O(nlogn) 。 其中分組的合理性會對算法產生重要的影響?，F在多 用 D.E.Knuth 的分組方法。Shell 排序比冒泡排序快 5 倍，比插入排序大致快 2 倍 。 Shell 排 序 比 起 QuickSort ， MergeSort ， HeapSort 慢很多。但是它相對比較簡單

4、，它適合于 數據量在 5000 以下并且速度并不是特別重要的場 合。它對于數據量較小的數列重復排序是非常好的。插入排序( InsertSort )插入排序通過把序列中的值插入一個已經排序好的序 列中，直到該序列的結束。插入排序是對冒泡排序的 改進。它比冒泡排序快 2 倍。一般不用在數據大于 1000 的場合下使用插入排序，或者重復排序超過 200 數據項的序列。冒泡排序( BubbleSort ) 冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它通過一趟又一趟地比較數組中的每一 個元素，使較大的數據下沉，較小的數據上升。它是 0(n八2)的算法。交 換 排 序 ( Exchange

5、Sort ) 和 選 擇 排 序( SelectSort )這兩種排序方法都是交換方法的排序算法，效率都是 O(n 2)。在實際應用中處于和冒泡排序基本相同的 地位。它們只是排序算法發(fā)展的初級階段，在實際中 使用較少。基數排序( RadixSort )基數排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法，但是它只能用于整數的排序，如果我們要把同樣的辦法運用到浮點數上，我們必須了解浮點數的存儲格式，并通過特殊的方式將浮點數映射到整數上，然后再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是， 這樣算法也需要較多的存儲空間9總結卜面是一個總的表格，大致總結了我們常見的所有的 排序算法的特點排序法平均時間最差情形穩(wěn)定度額外空間備注冒泡O(n 2)O(n 2)穩(wěn)定0(1)n小時較好交換O(n 2)O(n 2)不穩(wěn)定0(1)n小時較好選擇O(n 2)O(n 2)不穩(wěn)定0(1)n小時較好插入O(n 2)O(n 2)穩(wěn)0(1)大部分定已排序 時較好rd goco)rd goco)穩(wěn)定7 n /