常用排序算法的性能

admin

常用排序算法的性能算法平均时间复杂度最好情况最差情况空间复杂度排序方式稳定性
冒泡排序O(n2)O(n2)O(n)O(n)O(n2)O(n2)O(1)O(1)in-place稳定
选择排序O(n2)O(n2)O(n2)O(n2)O(n2)O(n2)O(1)O(1)in-place不稳定
插入排序O(n2)O(n2)O(n)O(n)O(n2)O(n2)O(1)O(1)in-place稳定
希尔排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(n2)O(n2)O(1)O(1)in-place不稳定
归并排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(n)O(n)out-place稳定
快速排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(n2)O(n2)O(n)O(n)in-place不稳定
堆排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(1)O(1)in-place不稳定
计数排序O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(k)O(k)out-place稳定
桶排序O(n+k)O(n+k)O(n+k)O(n+k)O(n2)O(n2)O(n)O(n)out-place稳定
基数排序O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(n+k)O(n+k)out-place稳定

我们日常用的最多的可能是快速排序和堆排序，这两个算法都是性能很高的排序算法，缺点是不稳定。
TimSort 算法性能比快速排序和堆排序还高，且是稳定排序算法。

算法平均时间复杂度最好情况最差情况空间复杂度排序方式稳定性
冒泡排序O(n2)O(n2)O(n)O(n)O(n2)O(n2)O(1)O(1)in-place稳定
选择排序O(n2)O(n2)O(n2)O(n2)O(n2)O(n2)O(1)O(1)in-place不稳定
插入排序O(n2)O(n2)O(n)O(n)O(n2)O(n2)O(1)O(1)in-place稳定
希尔排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(n2)O(n2)O(1)O(1)in-place不稳定
归并排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(n)O(n)out-place稳定
快速排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(n2)O(n2)O(n)O(n)in-place不稳定
堆排序O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(nlogn)O(nlog⁡n)O(1)O(1)in-place不稳定
计数排序O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(k)O(k)out-place稳定
桶排序O(n+k)O(n+k)O(n+k)O(n+k)O(n2)O(n2)O(n)O(n)out-place稳定
基数排序O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(n+k)O(n+k)out-place稳定