八大排序算法复杂度

排序算法时间空间复杂度表

排序方法 平均时间 最坏时间 辅助空间 稳定性
冒泡排序 $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
简单选择排序 $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
直接插入排序 $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 $O(n \log n)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(n \log n)$ $O(n \log n)$ $O(1)$ 不稳定
并归排序 $O(n \log n)$ $O(n \log n)$ $O(n)$ 稳定
快速排序 $O(n \log n)$ $O(n^2)$ $O(n \log n)$ 不稳定
基数排序 $O(d(n+r))$ $O(d(n+r))$ $O(n)$ 稳定

注:基数排序中,d 为位数,r 为基数,n 为原数组个数。

参考资料