排序的稳定性

2019-11-10  09:42:11  by冲冲

1、稳定性

① 定义：能保证两个相等的数，经过排序之后，其在序列的前后位置顺序不变。（A1=A2，排序前A1在A2前面，排序后A1还在A2前面）

② 意义：稳定性本质是维持具有相同属性的数据的插入顺序，如果后面需要使用该插入顺序排序，则稳定性排序可以避免这次排序。

比如，公司想根据“能力”和“资历”（以进入公司先后顺序为标准）作为本次提拔的参考，假设A和B能力相当，如果是稳定性排序，则第一次根据“能力”排序之后，就不需要第二次根据“”资历

排序了，因为“资历”排序就是员工插入员工表的顺序。如果是不稳定排序，则需要第二次排序，会增加系统开销。

2、分类

① 稳定性排序：冒泡排序，插入排序、归并排序、基数排序

② 不稳定性排序：选择排序、快速排序、希尔排序、堆排序

3、例析

（1）稳定性排序

① 冒泡排序

冒牌排序本质是，从左到右开始不断把大的元素往后调（或者，从右往左开始不断把小的元素往前调）。比较是比较相邻的两个元素，交换也是发生在这两个元素之间。所以，如果两个元素相等，你总不会无聊地把它俩交换一下吧。如果两个相等元素没有相邻，那么也会经过一波两两交换使他们相邻，此时也不会发生交换。

② 插入排序

插入排序本质是，在一个已经有序的小序列基础上，通过从右往左比较，一次插入一个元素。刚开始这个小序列只有一个元素。比较是从有序序列的末尾开始，想插入的元素和已经有序的最大者开始比较，如果比它大则直接插在其后面，否则一直往前比较，直到找到比它小的或与它相等的，然后插在其后面。

③ 归并排序

归并排序本质是，把序列递归地分成短序列，递归出口是短序列只有1个元素(此时认为直接有序)或者2个序列(1次比较和交换)，然后把各个有序的短序列合并成一个有序的长序列，不断合并直到原序列全部排好序。当存在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，因此不会破坏稳定性。那么在短的有序序列合并的过程中，稳定是否受到破坏？没有。合并过程中当两个当前元素相等时，处在前面序列的元素依然保存在结果序列的前面。

④ 基数排序

基数排序本质是，按照低位先排序，然后收集，再按照高位排序，然后再收集，依次类推，直到最高位。比如序列“171(1),331,171(2)”，低位排序（个位）结果是“171(1),331,171(2)”，高位排序（十位）结果是“331171(1),171(2)”，高位排序（百位）结果是“171(1),171(2),331”。

（2）不稳定性排序

① 选择排序

选择排序本质是，给每个位置选择剩下元素中最小的。比如给第一个位置选择最小的，给第二个位置选择剩余元素里面第二小的，依次类推。例如序列“5(1),8,5(2),2,9”，5(1)会和2交换，破坏稳定性。

② 快速排序

快速排序本质是，选取第一个元素为中枢元素a[center_index]（index=0）。从两个方向入手，首先左边的i下标一直往右走，当a[i] > a[center_index]停止，由右边的j下标开始往左走，当a[j] <= a[center_index]停止，由左边i下标开始刚才的表演，重复上面的过程，直到i>j，交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 “5,3(1),4,3(2),8,11,9”， 现在中枢元素5和3(2)交换就会把元素3的稳定性打乱。不稳定发生在中枢元素和a[j]交换的时刻。

③ 希尔排序

希尔排序本质是，按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

④ 堆排序

堆排序本质是，我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

4、时间复杂度和空间复杂度