稳定性的分析可结合相关排序的思想理解 !
◎ 稳定性介绍
稳定性指 : 排序前后两个相等的数的相对位置 .
○ 相对位置改变 , 即 : 该排序不稳定.
○ 相对位置没有改变 , 即 : 该排序稳定.
● 简单选择排序
重点理解 !
思想: 第一次在原始序列中选择一个最小的和最左边的交换 , 依次选择 ,直至有序.
特殊情况:
以上这种情况 , 虽然保证了 1 的稳定性 , 但是对于 3 来说 ,其相对位置是发生改变的.
故: 简单排序是 不稳定 的.
● 冒泡排序
思想 : 相邻两个比较进行交换 , 相等时就不交换了 . 所以 ,相等的数的相对位置不会发生变化.
故: 冒泡排序是 稳定 的.
● 堆排序
思想 : 堆顶元素和堆最后一个元素要发生交换 , 交换以后还要进行堆调整. 这其中一定会发生相对位置的变化.
故: 堆排序是 不稳定 的.
● 直接插入排序
思想 : [ 0 , end ] 有序 , end + 1 位置插入 , 当 end + 1 位置大于有序中的某一位置时停止 --end ,进行插入 , 因为该排序不涉及交换 , 所以相等数的相对位置不会发生改变.
故: 直接插入排序是 稳定 的.
● 希尔排序
思想 : 分 gap 组 , 每组进行插入排序的思想 , 虽然也不涉及交换 , 但分为了不同组别在不同组的插入中会有相等数相对位置变化的情况 .
故: 希尔排序是 不稳定 的.
● 快速排序
思想 : 选 key , 左边找大, 右边找小 , 找到了交换 , 当左边做 key 时右边先走 , 那么相遇位置一定比 key 小 ,就要和 key 位置交换.
这样的场景 6 的相对位置发生改变 .
故: 快速排序是 不稳定 的.
● 归并排序
思想 : 左右有序开始归并 , 两个区间小的尾插到新的空间中 , 等于时两个顺序是不变的.
故: 归并排序是 稳定 的.