Feeling

　　　　三人行，必有我師焉

:: :: 新隨筆 :: 聯系 :: :: 管理 ::

185 隨筆 :: 0 文章 :: 392 評論 :: 0 Trackbacks

1 快速排序（QuickSort）

快速排序是一個就地排序，分而治之，大規模遞歸的算法。從本質上來說，它是歸并排序的就地版本。快速排序可以由下面四步組成。

（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(n²)。在實際應用中處于和冒泡排序基本相同的地位。它們只是排序算法發展的初級階段，在實際中使用較少。

8 基數排序（RadixSort）

基數排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法，但是它只能用于整數的排序，如果我們要把同樣的辦法運用到浮點數上，我們必須了解浮點數的存儲格式，并通過特殊的方式將浮點數映射到整數上，然后再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是，這樣算法也需要較多的存儲空間。

9 總結

下面是一個總的表格，大致總結了我們常見的所有的排序算法的特點。

排序法	平均時間	最差情形	穩定度	額外空間	備注
冒泡	O(n²)	O(n²)	穩定	O(1)	n小時較好
交換	O(n²)	O(n²)	不穩定	O(1)	n小時較好
選擇	O(n²)	O(n²)	不穩定	O(1)	n小時較好
插入	O(n²)	O(n²)	穩定	O(1)	大部分已排序時較好
基數	O(log_RB)	O(log_RB)	穩定	O(n)	B是真數(0-9)， R是基數(個十百)
Shell	O(nlogn)	O(n^s) 1<2	不穩定	O(1)	s是所選分組
快速	O(nlogn)	O(n²)	不穩定	O(nlogn)	n大時較好
歸并	O(nlogn)	O(nlogn)	穩定	O(1)	n大時較好
堆	O(nlogn)	O(nlogn)	不穩定	O(1)	n大時較好

posted on 2012-11-10 22:30 三人行，必有我師焉閱讀(336) 評論(0) 編輯收藏

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理

GitHub | 開源中國社區 | maven倉庫 | 文件格式轉換

Feeling

常用鏈接

留言簿(53)

隨筆檔案(85)

朋友圈

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜