技术开发算法
算法
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 为原数组个数。

参考资料