常用排序算法的性能

算法	平均时间复杂度	最好情况	最差情况	空间复杂度	排序方式	稳定性
冒泡排序	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 算法性能比快速排序和堆排序还高，且是稳定排序算法。