八大排序

时间复杂度总结

排序方法	平均时间	最好时间	最坏时间	稳定性
选择排序	O(n^2)	O(n^2)	O(n^2)	✔️
希尔排序	O(n^1.3)			✔️
快速排序	O(nlogn)	O(nlogn)	O(n^2)	✔️
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	✔️
冒泡排序	O(n^2)	O(n)	O(n^2)	✖
插入排序	O(n^2)	O(n)	O(n^2)	✖
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	✖
基数排序	O(n)	O(n)	O(n)	✖

稳定性

在待排序中，存在 多条相同的记录。如果排序后，这些相同记录的 相对次序 没有发生改变，则称这种排序算法是稳定的；

例如：待排序数组为[3, 1, 1, 2]，有两个相同关键字（1）。经过稳定算法排序后，原序列前方的1依旧在序列中还保持在前方，这就是稳定的。