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)的都可以认为是原地算法
非原地算法，称为Not-in-place或Out-of-place
网友评论