一、稳定的定义

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

二、冒泡排序

冒泡排序每次两两比较,把两者中大(小)的往后调。当两个元素相等时,一般不会将他们交换。故冒泡算法是一种稳定的排序算法。

三、选择排序

选择排序是每次选最小的给第一个换,依次类推。故当遇到如3 7 3 2 9时,第一步将2与3对换,变为2 7 3 3 9,此时两个3的相对位置发生了改变,故不稳定。

四、插入排序

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。故没有改变相等元素的相对位置,故稳定。

五、快速排序

每次找一基准点,不妨取第一个,然后划分使用挖坑法,每次是基准点左边小(大)于它,右边大(小)于它。则对于6 3 3 4 3 8,以6为基准点,先从右往左走,找到3,然后将3填入6的位置,则此时,3的相对位置发生了改变,故不稳定、

六、归并排序

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

七、基数排序(详解)

基数排序是按照低位先排序,再按照高位排序;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前,故稳定。

八、希尔排序

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

九、堆排序

堆的结构是节点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个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

十、桶排序

桶排序在不考虑空间消耗的情况下,可以说是速度最快的排序之一。一般来说,认为桶排序是稳定的,如基数排序中就运用额桶排序。

十一、计数排序(详解

基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数,则可以确定这个数的位置。例如要排序的数为 7 4 2 1 5 3 1 5;则比7小的有7个数,所有7应该在排序好的数列的第八位,同理3在第四位,对于重复的数字,1在1位和2位(暂且认为第一个1比第二个1小),5和1一样位于6位和7位。故稳定。

十二、总结


image.png

你可能感兴趣的文章

评论区

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

您好,欢迎到访网站!
  查看权限

«   2019年3月   »
123
45678910
11121314151617
18192021222324
25262728293031