刷题
刷题
learn
learn
日期
Sep 1, 2024
- 稳定性
- 排序算法的稳定性是指：同样大小的样本在排序之后不会改变原始的相对次序
- 稳定性对基础类型对象（整型、浮点型等）来说毫无意义；稳定性对非基础类型对象有意义，可以保留之前的相对次序。
主要算法时间、空间、稳定性总结
算法名称
时间
空间
稳定性
注意：随机快排的复杂度要按照概率上的期望估计，而不能用最坏情况的复杂度
基于比较的排序，时间复杂度，空间复杂度低于，还具有稳定性的排序算法目前没有找到
TimSort也不行，虽然在实际应用中TimSort通常不需要这么多的额外空间，但空间复杂度指标就是
ShellSort也不常用
所以，选择什么排序算法就是看你在排序过程中更看重什么
- 数据量非常小的情况下可以做到非常迅速：插入排序
- 性能优异、实现简单且利于改进（面对不同业务可以选择不同划分策略）、不在乎稳定性：随机快排
- 性能优异，不在乎额外空间占用、具有稳定性：归并排序
- 性能优异、额外空间占用要求、不在乎稳定性：堆排序