【排序算法】(1)排序的稳定性

排序的稳定性


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、时间复杂度和空间复杂度

排序算法
类别排序方法时间复杂度空间复杂度稳定性应用依据剖析 
平均情况最好情况最坏情况辅助内存
插入排序直接插入O(n2)O(n)O(n2) O(1) 稳定大部分已经排序 
希尔排序 O(n1.3)O(n) O(n2 O(1) 不稳定  
选择排序直接选择O(n2)O(n2)O(n2) O(1) 不稳定n比较小 
堆排序O(nlog2n) O(nlog2n)O(nlog2n)  O(1) 不稳定n比较大 
交换排序冒泡排序O(n2) O(n)  O(n2O(1)  稳定n比较小 
快速排序O(nlog2n) O(nlog2n) O(n2 O(log2n)~O(n) 不稳定n比较大 
归并排序 O(nlog2n) O(nlog2n)O(nlog2n)  O(1) 稳定n比较大 
基数排序    O(1) 稳定  

相关推荐