Sorting algorithm comparison

(图片来自 十大经典排序算法

算法对比

为了方便起见,本博客的排序算法都约定如下:

  • 目标是按照从小到大排序。
  • 允许修改待排序数组(即 in-place 修改)。
  • 待排序序列的数值范围为 $[0, k]$。
  • 待排序序列的数值的最大位数为 $d$。
  • 待排序序列的长度为 $n$。
# 排序算法 平均* 最好* 最坏* 空间 Out-Place 稳定 比较排序 本博客
1 冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ x
2 插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ x
3 选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ x x
4 归并排序 $O(n\log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$
5 希尔排序 $O(n\log n)$ $O(n \log^2 n)$ $O(n \log^2 n)$ $O(1)$ x x
6 计数排序 $O(n + k)$ $O(n + k)$ $O(n + k)$ $O(k)$ x
7 桶排序 $O(n + k)$ $O(n + k)$ $O(n^2)$ $O(n + k)$ x
8 基数排序 $O(n \times d)$ $O(n \times d)$ $O(n \times d)$ $O(n + d)$ x
9 堆排序 $O(n\log n)$ $O(n \log n)$ $O(n \log n)$ $O(1)$ x x
10 快速排序 $O(n\log n)$ $O(n \log n)$ $O(n^2)$ $O(\log n)$ x x
11 Timsort 排序

算法选择

TODO

算法性能测试

见《🔢 排序算法 00. 代码实现》(本博客)。

参考