本文主要针对各种排序算法之间的特性进行比较。

1.2 排序总结

排序算法按照排序的种类、稳定性、时间复杂度和空间复杂度进行总结。

名称 排序类型 排序方式 时间复杂度(平均) 时间复杂度(最好) 时间复杂度(最坏) 空间复杂度 稳定性
冒泡排序 比较 交换排序 $O(n^2)$ $O(n)$ $O(n^2)$ O(1) 稳定
快速排序 比较 交换排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ $O(logn)$ 不稳定
插入排序 比较 插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 比较 插入排序 $O(n^{4/3})$ $O(nlogn)$ $O(n^{3/2})$ $O(1)$ 不稳定
选择排序 比较 选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 比较 选择排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ O(1) 不稳定
归并排序 比较 归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ 稳定
计数排序 非比较 计数 $O(n+r)$ $O(n+r)$ $O(n+r)$ $O(n)$ 稳定
基数排序 非比较 - $O(n*\frac{k}{d})$ $O(n)$ $O(n*\frac{k}{d})$ $O(n+2^d)$ 稳定
桶排序 非比较 - $O(n+r)$ - $O(n+r)$ $O(n+r)$ 稳定