八大排序算法复杂度

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

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

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

参考资料