排序演算法——總結

來自專欄演算法（第四版）學習筆記

1.排序演算法分類：

掌握以下常見演算法即可。

1.1.基於比較的排序法：

• 插入排序法：
• 常見：直接插入排序、希爾排序
• 罕見：伸展排序、二叉查找樹排序、圖書館排序、耐心排序
• 交換排序法：
• 常見：冒泡、快排（根據冒泡改進）。
• 罕見：雞尾酒排序、奇偶排序、梳排序、侏儒排序、臭皮匠排序、Bogo排序。
• 選擇排序法：
• 常見：直接選擇、堆排序。
• 罕見：平滑排序、笛卡爾樹排序、錦標賽排序、圈排序
• 歸併排序：
• 常見：歸併排序
• 罕見：梯級歸併排序、振蕩歸併排序、多相歸併排序、串列排序

1.2非基於比較的排序：

這些排序元素，因為其關鍵值本身就含有了定位特徵，因而不需要比較就可以確定其前後位置。

• 分布排序法：
• 常見：基數、計數、桶排序。
• 罕見：美國旗幟排序、珠排序、爆炸排序、鴿巢排序、相鄰圖排序、閃電排序、插值排序

1.3混合排序：

• 罕見：塊排序、Tim排序、內省排序、Spread排序、J排序

1.4並發類排序：

• 罕見：雙調排序器 Batcher歸併網路 兩兩排序網路

1.5其他排序：

• 罕見：拓撲排序、煎餅排序、意粉排序

2.演算法性能特點分析：

• 有很多辦法能將任意排序演算法變成穩定的，但一般只有在穩定性是必要的情況下穩定的排序演算法才算有優勢。
• 沒有任何基於比較的演算法能保證使用少於log(N!)~NlogN次比較將數組排序。

證明： 見書P177.

3.演算法使用場景：

排序演算法的選擇要考慮：數組大小、無序性、穩定應、空間。

• 數組大+要求穩定性+空間允許：歸併
• 數組大：堆排序、快排、歸併，因為他們是nlogn複雜度的方法。
• 中等大小數組：可以考慮希爾排序。
• 數組小（小於15）：冒泡、希爾排序、選擇
• 無序性高：快排，也可以用希爾排序。
• 無序性低：插入、冒泡，他倆可降為O(n)。

4.Java排序：

• Comparator介面允許為任何數據類型定義任意多種排序方法，用Comparator代替Comparable介面能夠更好地將數據類型的定義和兩個該類型的對象應該如何比較的定義區分開來，可以定義多種比較器。
• 對於任意大小的元素，引用在一般情況下交換的成本和比較的成本幾乎相同，代價是需要額外的空間存儲這些應用。
• java系統（Arrays.sort()）選擇對原始數據類型使用三項切分的快速排序，對引用類型使用歸併排序。這些選擇實際上暗示著用速度和空間（對於原始數據類型）來換取穩定性（對於引用類型）。

5.應用：

• 問題規約：為解決某個問題而發明的演算法正好用來解決另一種問題。
• 找出重複的元素
• 排名
• 優先隊列
• 中位數與順序統計：找出中位數，計算TopM（用快排的切分）。

推薦閱讀：