快速排序是壹個就地排序,分而治之,大規模遞歸的算法。從本質上來說,它是歸並排序的就地版本。快速排序可以由下面四步組成。
(1) 如果不多於1個數據,直接返回。
(2) 壹般選擇序列最左邊的值作為支點數據。
(3) 將序列分成2部分,壹部分都大於支點數據,另外壹部分都小於支點數據。
(4) 對兩邊利用遞歸排序數列。
快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法,但是就通常情況而言,沒有比它更快的了。快速排序是遞歸的,對於內存非常有限的機器來說,它不是壹個好的選擇。
2 歸並排序(MergeSort)
歸並排序先分解要排序的序列,從1分成2,2分成4,依次分解,當分解到只有1個壹組的時候,就可以排序這些分組,然後依次合並回原來的序列中,這樣就可以排序所有數據。合並排序比堆排序稍微快壹點,但是需要比堆排序多壹倍的內存空間,因為它需要壹個額外的數組。
3 堆排序(HeapSort)
堆排序適合於數據量非常大的場合(百萬數據)。
堆排序不需要大量的遞歸或者多維的暫存數組。這對於數據量非常巨大的序列是合適的。比如超過數百萬條記錄,因為快速排序,歸並排序都使用遞歸來設計算法,在數據量非常大的時候,可能會發生堆棧溢出錯誤。
堆排序會將所有的數據建成壹個堆,最大的數據在堆頂,然後將堆頂數據和序列的最後壹個數據交換。接下來再次重建堆,交換數據,依次下去,就可以排序所有的數據。
4 Shell排序(ShellSort)
Shell排序通過將數據分成不同的組,先對每壹組進行排序,然後再對所有的元素進行壹次插入排序,以減少數據交換和移動的次數。平均效率是O(nlogn)。其中分組的合理性會對算法產生重要的影響。現在多用D.E.Knuth的分組方法。
Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相對比較簡單,它適合於數據量在5000以下並且速度並不是特別重要的場合。它對於數據量較小的數列重復排序是非常好的。
5 插入排序(InsertSort)
插入排序通過把序列中的值插入壹個已經排序好的序列中,直到該序列的結束。插入排序是對冒泡排序的改進。它比冒泡排序快2倍。壹般不用在數據大於1000的場合下使用插入排序,或者重復排序超過200數據項的序列。
6 冒泡排序(BubbleSort)
冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它通過壹趟又壹趟地比較數組中的每壹個元素,使較大的數據下沈,較小的數據上升。它是O(n^2)的算法。
7 交換排序(ExchangeSort)和選擇排序(SelectSort)
這兩種排序方法都是交換方法的排序算法,效率都是 O(n2)。在實際應用中處於和冒泡排序基本相同的地位。它們只是排序算法發展的初級階段,在實際中使用較少。
8 基數排序(RadixSort)
基數排序和通常的排序算法並不走同樣的路線。它是壹種比較新穎的算法,但是它只能用於整數的排序,如果我們要把同樣的辦法運用到浮點數上,我們必須了解浮點數的存儲格式,並通過特殊的方式將浮點數映射到整數上,然後再映射回去,這是非常麻煩的事情,因此,它的使用同樣也不多。而且,最重要的是,這樣算法也需要較多的存儲空間。
9 總結
下面是壹個總的表格,大致總結了我們常見的所有的排序算法的特點。
排序法 平均時間 最差情形 穩定度 額外空間 備註
冒泡 O(n2) O(n2) 穩定 O(1) n小時較好
交換 O(n2) O(n2) 不穩定 O(1) n小時較好
選擇 O(n2) O(n2) 不穩定 O(1) n小時較好
插入 O(n2) O(n2) 穩定 O(1) 大部分已排序時較好
基數 O(logRB) O(logRB) 穩定 O(n)
B是真數(0-9),
R是基數(個十百)
Shell O(nlogn) O(ns) 1<s<2 不穩定 O(1) s是所選分組
快速 O(nlogn) O(n2) 不穩定 O(nlogn) n大時較好
歸並 O(nlogn) O(nlogn) 穩定 O(1) n大時較好
堆 O(nlogn) O(nlogn) 不穩定 O(1) n大時較好