学步园

排序算法总表

排序算法稳定性

在这个表格中，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)

说明：虽然完全逆序的情况下，快速排序会降到选择排序的速度，不过从概率角度来说(参考信息学理论，和概率学)，不对算法做编程上优化时，快速排序的平均速度比堆排序要快一些。