十大排序算法前序

937F34DE-7319-4F55-8462-6BA9D280CCFE.png

• 以上表格是基于数据进行排序的一般性结论
• 冒泡、选择、插入、归并、快速、希尔、堆排序、属于比较排序

排序算法的稳定性

• 如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法

排序前：5, 1, 3𝑎, 4, 7, 3𝑏
稳定的排序： 1, 3𝑎, 3𝑏, 4, 5, 7
不稳定的排序：1, 3𝑏, 3𝑎, 4, 5, 7

• 对自定义对象进行排序时，稳定性会影响最终的排序结果

• 冒泡排序属于稳定的排序算法

稍有不慎，稳定的排序算法也能被写成不稳定的排序算法，比如下面的冒泡排序代码是不稳定的

02DEF2A2-5BC4-4888-BCB0-C39A0BAB21FE.png

原地算法

什么是原地算法？

1. 不依赖额外的资源或依赖比较少的额外资源，仅依靠输出来覆盖输入。

2. 空间复杂度为 𝑂(1)的都可以认为是原地算法

非原地算法，称为Not-in-place或Out-of-place