500      阿裏雲  技術社區[雲棲]

排序算法

排序算法總表

排序算法穩定性

在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。

穩定的

• 冒泡排序（bubble sort） — O(n²)
• 雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n²)
• 插入排序 （insertion sort）— O(n²)
• 桶排序 （bucket sort）— O(n); 需要 O(k) 額外空間
• 計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外空間
• 合並排序 （merge sort）— O(n log n); 需要 O(n) 額外空間
• 原地合並排序 — O(n²)
• 二叉排序樹排序 （Binary tree sort） — O(n log n)期望時間; O(n²)最壞時間; 需要 O(n) 額外空間
• 鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間
• 基數排序 （radix sort）— O(n·k); 需要 O(n) 額外空間
• Gnome 排序 — O(n²)
• 圖書館排序 — O(n log n) with high probability, 需要 (1+ε)n 額外空間

不穩定

• 選擇排序 （selection sort）— O(n²)
• 希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
• 組合排序 — O(n log n)
• 堆排序 （heapsort）— O(n log n)
• 平滑排序 — O(n log n)
• 快速排序 （quicksort）— O(n log n) 期望時間, O(n²) 最壞情況; 對於大的、亂數列表一般相信是最快的已知排序
• Introsort — O(n log n)
• Patience sorting — O(n log n + k) 最壞情況時間，需要 額外的 O(n + k) 空間，也需要找到最長的遞增子串行（longest increasing subsequence）

不實用的排序算法

• Bogo排序 — O(n × n!)，最壞的情況下期望時間為無窮。
• Stupid sort — O(n³); 遞歸版本需要 O(n²) 額外存儲器
• 珠排序（Bead sort） — O(n) or O(√n), 但需要特別的硬件
• Pancake sorting — O(n), 但需要特別的硬件

平均時間複雜度

平均時間複雜度由高到低為：

• 冒泡排序 O(n²)
• 插入排序 O(n²)
• 選擇排序 O(n²)
• 歸並排序 O(n log n)
• 堆排序 O(n log n)
• 快速排序 O(n log n)
• 希爾排序 O(n^1.25)
• 基數排序 O(n)

說明：雖然完全逆序的情況下，快速排序會降到選擇排序的速度，不過從概率角度來說(參考信息學理論，和概率學)，不對算法做編程上優化時，快速排序的平均速度比堆排序要快一些。

最後更新：2017-04-03 19:06:48

  上一篇： 雅安，挺住！

  下一篇： 怎樣花兩年時間去麵試一個人