技术开发算法
算法
Source
Edit
History

八大排序算法复杂度

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

排序方法 平均时间 最坏时间 辅助空间 稳定性
冒泡排序 $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 为原数组个数。

参考资料