精华内容
下载资源
问答
  • 首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置...

    首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。

      其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。
    

    回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。

    (1)冒泡排序

    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

    (2)选择排序

    选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n - 1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

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

    (4)快速排序
    快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j,交换a[i]和a[j],重复上面的过程,直到i > j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。

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

    (6)基数排序
    基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

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

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

    综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

    展开全文
  • 在下列排序方法中,不稳定方法有 正确答案: C 你的答案: C (正确) 归并排序与基数排序 插进排序与希尔排序排序与快速排序 选择排序与冒泡排序 添加笔记 收藏 纠错 这道题同:将一个从大...

    在下列排序方法中,不稳定的方法有

    正确答案: C   你的答案: C (正确)

    归并排序与基数排序
    插进排序与希尔排序
    堆排序与快速排序
    选择排序与冒泡排序


    排序方法        平均情况        最好情况        最坏情况        辅助空间        稳定性
    冒泡排序         O(n^2)           O(n)              O(n^2)            O(1)                稳定
    选择排序         O(n^2)          O(n^2)            O(n^2)            O(1)              不稳定
    插入排序         O(n^2)           O(n)              O(n^2)            O(1)                稳定
    希尔排序O(n*log(n))~O(n^2) O(n^1.3)       O(n^2)            O(1)              不稳定
    堆排序          O(n*log(n))     O(n*log(n))    O(n*log(n))       O(1)              不稳定
    归并排序       O(n*log(n))     O(n*log(n))    O(n*log(n))       O(n)                稳定
    快速排序       O(n*log(n))     O(n*log(n))      O(n^2)            O(1)              不稳定

    冒泡排序经过优化以后,最好时间复杂度可以达到O(n)。设置一个标志位,如果有一趟比较中没有发生任何交换,可提前结束,因此在正序情况下,时间复杂度为O(n)。

    选择排序在最坏和最好情况下,都必须在剩余的序列中选择最小(大)的数,与已排好序的序列后一个位置元素做交换,依次最好和最坏时间复杂度均为O(n^2)。

    插入排序是在把已排好序的序列的后一个元素插入到前面已排好序(需要选择合适的位置)的序列中,在正序情况下时间复杂度为O(n)。

    堆是完全二叉树,因此树的深度一定是log(n)+1,最好和最坏时间复杂度均为O(n*log(n))。

    归并排序是将大数组分为两个小数组,依次递归,相当于二叉树,深度为log(n)+1,因此最好和最坏时间复杂度都是O(n*log(n))。

    快速排序在正序或逆序情况下,每次划分只得到比上一次划分少一个记录的子序列,用递归树画出来,是一棵斜树,此时需要n-1次递归,且第i次划分要经过n-i次关键字比较才能找到第i个记录,因此时间复杂度是\sum_{i=1}^{n-1}(n-i)=n(n-1)/2,即O(n^2)。


    展开全文
  • 冒泡排序 目录: 1.原理 2.代码实现 3.时间复杂度 4.稳定性 5.应用 1.原理 试问冒泡排序谁不会?这篇文章重点不是叫你怎样写冒泡排序,而是总结了一点应用层面的东西。 冒泡排序的思想:挨个比较,两两比较,每一层...

    冒泡排序

    目录:
    1.原理
    2.代码实现
    3.时间复杂度
    4.稳定性
    5.应用

    1.原理

    • 试问冒泡排序谁不会?这篇文章重点不是叫你怎样写冒泡排序,而是总结了一点应用层面的东西。
    • 冒泡排序的思想:挨个比较,两两比较,每一层循环会使得一个最大/小值到数组的最后面。就像一个个气泡被升上去一样,故名冒泡排序。
    • 放原理图
      在这里插入图片描述

    2.代码实现

    这是一种比较偷懒的方法,如果要代码更规范一些,可以考虑用函数和指针来实现

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,i,j;
        cin>>n;
        int arr[n+5];
        for(i=0;i<n;i++)cin>>arr[i];
        for(i=0;i<n-1;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(arr[i]<arr[j])
                {
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        for(i=0;i<n;i++)
        {
            cout<<arr[i];
            if(i!=n-1)cout<<" ";
        }
        cout<<endl;
        return 0;
    }
    
    

    用函数解决代码如下

    #include<bits/stdc++.h>
    using namespace std;
    void swapp(int *x,int *y)
    {
        int temp=*x;
        *x=*y;
        *y=temp;
    }
    void maopaosort(int *a,int n)
    {
        int j,i;
        for(i=0;i<n-1;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(a[i]<a[j])
                {
                    swapp(&a[i],&a[j]);
                }
            }
        }
    }
    int main()
    {
        int n,i;
        cin>>n;
        int arr[n+5];
        for(i=0;i<n;i++)cin>>arr[i];
        maopaosort(arr,n);
        for(i=0;i<n;i++)
        {
            cout<<arr[i];
            if(i!=n-1)cout<<" ";
        }
        cout<<endl;
        return 0;
    }
    
    

    3.时间复杂度

    • 当数列是正序的时候,只需遍历一遍n-1个元素,没有移动次数,即最佳时间复杂度为O(n)
    • 当数列是逆序的时候,冒泡排序总比较次数为n(n-1)/2,移动次数为3n(n-1)/2,最差时间复杂度为O(n^2),
    • 一般我们认为原始序列是杂乱的,我们认为算法的平均时间复杂度为O(n^2)

    4.稳定性

    因为算法只是元素的两两交换,相同元素前后的顺序没有变化,冒泡排序是一种稳定的算法

    5.应用

    1. 有一个题(我忘了找不到了,描述一下),给你一组数据,要求排成上升序列,每次可以换两个元素的位置,求交换的次数。
      这是典型的应用:求逆序数,所谓逆序数,举个例子,若规定上升序列为正序,则以下序列:3 ,5 ,1 ,4,其中的逆序数有{3,1}{5,1}{5,4},冒泡排序没交换一次,就消除了一对逆序数,所以: 冒泡排序交换次数为此数列逆序数对数
      2.随意输入两个数字,将这两个数字转为最小后相加
      例如:54321 16249
      输出:12345+12469=24814
      想法1:输入两个数据存入两个int,把数字存到数组中,然后排序(好像随便一个排序方法都行,那么为什么要放在这个地方呢?因为我暂时没想到别的题),最后输出就得。
      想法2:可以考虑用bool数组来存出现过的数字
    展开全文
  • 排序算法,相信你不会陌生~快排、冒泡、选择、归并等等,几大排序算法中,有的是稳定排序,有的则是不稳定排序。但是你有没有想过,既然排序得到的结果都是有序的,为什么还要区分稳定不稳定呢?

    对于排序算法,相信你一定不陌生吧!如我们常见的几大经典排序:

    冒泡排序插入排序选择排序快速排序归并排序堆排序等等。


    这些排序算法中,性能、内存消耗各有优劣,同时也各有各的适用场景,而我们也不能仅仅从时间复杂度和空间复杂度的优劣去评断一个排序算法的好与坏,比如冒泡排序插入排序,两者的时间复杂度均是O(n²),空间复杂度也都是O(1),但是插入排序却更常用,而且在很多实际场景中,执行效率更高,至于原因,你可以思考一下,此文暂不做讨论。


    而排序算法中,除了时间复杂度和空间复杂度,还有着一个我们比较常关注的性质:稳定性

    我们这里简单描述一下什么是排序算法的稳定性:

    对于某一种排序算法,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序保持不变,那么就说这个排序算法是稳定的。

    而上面所提到的几种排序算法中,冒泡排序、插入排序、归并排序属于稳定排序,选择排序、快速排序、堆排序属于不稳定排序。


    简单举个例子:

    假设对数组[3, 2, 2, 5, 1, 4]进行递增排序,数组中有两个元素是相等的即2,为方便标识,我们先用2'表示第二个2,即原数组为:[3, 2, 2', 5, 1, 4]。

    • 如果使用稳定排序,那么排序后有且仅有一种结果:[1, 2, 2', 3, 4, 5]。

    • 如果使用不稳定排序,那么排序后,可能会出现这种结果:[1, 2', 2, 3, 4, 5]


    排序的稳定性很好去理解,也很容易去分析。但是你有没有想过:

    既然所有的排序算法排出来的结果都是有序的,为什么还要区分稳定性和不稳定性的算法呢?



    我们用下面一个场景来说明。


    假设有一万条订单记录,要对这些订单进行一个排序,要求按照金额有小到大的顺序排列,如果订单金额相同,则按照下单时间的先后进行排列。

    假设订单数据为:

    在开始进行排序时,有一点先要弄明白:像这种存在需要对多个关键字进行排序的,每一次排序只能基于其中某一个且仅一个关键字进行排序,无法对多个关键字同时排序。之所以提这一点,是为了避免有人拿Java的比较器Comparator做对比,那根本是两码事。

    而对于需要针对多个关键字排序的情况,优先级最高的要放在最后排才行,比如这里先按照金额大小排序,在金额大小相同的情况下,再按照下单时间排序,优先级最高的就是金额,那么就应该最后再排金额。如果先排金额,在排序后,如果有金额相同的,再排下单时间,那么最后的结果就是以下单时间的先后为准了,你好好想一想,是不是这么回事?

    好,那我们进行排序,先对下单时间进行排序,得到的结果为:

    得到这个结果后,我们再对金额进行一次排序就OK了,但是这里为了达到需求要求的效果,即金额相同的,下单时间早的要排在前面,则第二次排序只能用稳定排序。如果使用不稳定排序,第二次按照金额排序后,得到的结果虽然在金额上是有序的,但下单时间上就不一定有序了,换一种说法就是:第一次按照订单时间排序的结果,没有被第二次按照金额排序利用上,先看图:

    使用稳定排序后的结果:

    这样子你应该明白了吧,如果使用不稳定排序,那么第二次排序后的结果,就可能不符合要求,不稳定排序会改变相同元素的原有顺序。在这个场景中,不稳定排序就可能会把金额均是30的原有顺序改变了(注意哦,这个顺序是已经按照下单时间排好序的结果),从而导致最终的排序结果对于金额相同的,没有按照时间先后来排序。但是这种问题,使用稳定排序就不会出现。


    所以,现在你明白了吧,之所以区分排序的稳定性和不稳定性,是有它的实际应用场景的,它的意义在于:

    在需要对多个(也意味着多次)具有优先级的关键字进行排序的场景下,稳定排序能利用上一次排序的结果服务于本次排序,从而保证对于值相同的元素的两次排序结果相同。


    用这个场景来解释就是:

    第一次排序先对下单时间进行排序,得到的排序结果中,两个金额为30的记录在下单时间上已经是有序的了;然后第二次排序对金额进行排序,由于使用了稳定排序,两个金额为30的记录的顺序就不会被改变了,这就相当于第一次排序的结果被第二次排序利用上了。



    如果你还是不能够完全理解,再举一个实际场景:


    对考生的成绩进行排名,如果总分相同的,则按照语文分数高低排,如果语文分数还相同的,继续按照数学分数高低排。

    看到这个例子,你是否恍然大悟了呢?

    在这个例子中,排序的优先级是:总分 > 语文 > 数学,如果使用稳定排序,我们就能得到预期且是正确的结果;如果使用不稳定排序,就有可能会出现,对于总分相同的,语文分数较低的就排在了更前面,这个结果对于成绩排名,就不是正确的。


    这就是稳定排序的实际应用场景,对于某些场景,不稳定排序得到结果可能是不正确的。


    THE END

    展开全文
  • 排序算法 稳定不稳定 最近在一次采访中,在对排序算法提出了一些最初的问题(例如,您如何编写QuickSort或QuickSort与MergeSort之间的区别)之后,访问者问您是否了解稳定不稳定排序算法之间的区别? 这个...
  • 排序之简单排序方法

    2017-05-13 18:54:36
    最近我整理了经常用到的排序算法。排序就是按关键字的递减或递增顺序对一组记录重新进行整队的操作。对于排序来说,主要...复杂排序方法将在我的下一篇博客中整理。 一、简单选择排序 1、排序思想首先,在带排序序列
  • 选择排序、快速排序、希尔排序、堆排序不是稳定排序算法, 冒泡排序、插入排序、归并排序和基数排序稳定排序算法。 冒泡法:  这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的...
  • 有两个6,a[0]和a[3]。排序结果就有两种可能: 如果排序结束后,a[0]可以保证一定在a[3]前头,也就是他们原有的顺序不变,那...(比如常见的选择排序,希尔排序,堆排序,快速排序等都是不稳定排序算法) 要证...
  • 排序方法及二叉树

    2018-10-22 21:31:30
    排序算法可以说是一项基本功,解决实际问题中经常遇到,针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率,有时候排序稳定性还是实际问题中必须考虑的,这篇博客对常见的排序算法进行整理,包括:...
  • 常见的排序算法有选择排序、快速排序、希尔排序、堆排序、冒泡排序、插入排序、归并排序和基数排序。 快速排序的应用: 补充知识: 结构体: typedef struct Pat{ int num; string sid; int age; }PAT; //相当于...
  • 排序方法的比较

    千次阅读 2015-07-31 14:08:51
    首先给出各个排序方式的性能比较...排序方法的比较 类别 排序方法 时间复杂度 空间复杂度 稳定性 平均情况 最好情况 最坏情况 辅助存储 插入排序 直接插入 O(n2) O(n) O(n2) O(1)
  • 各种排序方法的比较

    2021-03-17 14:18:39
    在选用排序方法的时候,我们应该综合考虑以下方面: 1)时间复杂度; 2) 空间复杂度; 3)稳定性; 4)算法简单性; 5)待排序记录个数n的大小; 6)记录本身信息量的大小; 7)关键码的分布情况; 下面先从...
  • 算法 - 内部排序方法总结

    万次阅读 2019-03-05 16:53:26
    各种排序方法的性能比较 排序方法 最好时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 直接插入排序 O(n) O(n2) O(n2) O(1) 稳定 简单选择排...
  • 哪些排序不稳定的?稳定又意味着什么?

    万次阅读 多人点赞 2019-06-21 14:48:37
    最近有看到稳定排序不稳定排序这一说,貌似还是挺常识的概念,排序可能大家在面试当中经常被问到,但是对于稳定性和不稳定性,又了解多少呢?下面通过这篇文章给大家全面讲解一下。 对于排序稳定性的意义: 通俗...
  • Java常见排序方法

    千次阅读 2019-03-10 14:41:28
    日常操作中常见的排序方法有:冒泡排序、快速排序、选择排序、插入排序、希尔排序,甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。 以下常见算法的定义 1. 插入排序:插入排序基本操作就是将一个...
  • C# 各种内部排序方法的实现(直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序以下代码为我在学习数据结构时自己敲出来的,转载请标明出处。 数据结构学习视频为青岛大学...
  • 八大排序算法

    万次阅读 多人点赞 2012-07-23 16:45:18
    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...
  • 各种排序方法总结

    2016-10-01 10:22:35
    选择排序、快速排序、希尔排序、堆排序不是稳定排序算法, 冒泡排序、插入排序、归并排序和基数排序稳定排序算法。   冒泡法:  这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的...
  • 排序方法汇总

    2016-08-02 10:00:32
    要点 算法思想算法分析 冒泡排序算法的性能 时间复杂度 算法稳定性优化完整参考代码 JAVA版本参考资料相关阅读 要点 冒泡排序是一种交换排序。 什么是交换排序呢? 交换排序:两两比较待排序的关键字,并交换...
  • 几种不稳定排序算法

    2014-04-25 17:52:38
    几种常用的不稳定排序算法的整理。 [code="java"] package com.study.sort; import java.util.Random; public class UnstableSort { /** * 生成一个随机数组 * @param length 数组长度 ...
  • 在选择排序方法时,主要需考虑以下因素。 1)数据表的大小,即待排序数据元素的个数。 2)关键字的分布情况。 3)对排序稳定性要求。 考虑上述因素,在此提出下列建议供参考。 1)若数据表的长度较小(如n<50)时,...
  • 最近在一次采访中,在对排序算法提出了一些最初的问题(例如,您如何编写QuickSort或QuickSort和MergeSort之间的区别)之后,访问者问您是否了解稳定不稳定排序算法之间的区别? 这个问题对我的读者来说是新问题...
  •  日常操作中常见的排序方法有:冒泡排序、快速排序、选择排序、插入排序、希尔排序,甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。 以下常见算法的定义 1. 插入排序:插入排序基本操作就是将...
  • 在这篇文档中将介绍几种...不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 空间复杂度:是指算法在计...
  • 前面课时中,我们学习了分治法的思想,以及二分查找的实现方法。我们讲到,二分查找要求原数组必须有序。其实,由无序到有序,这是算法领域最常见的一类问题,即排序...衡量一个排序算法的优劣,我们主要会从以下 3 个
  • 常见排序方法

    2014-09-25 21:04:52
    1.选择排序 定义:首先,选出数组中最小的元素,将它与数组中第一个元素交换。然后找出次小的元素,并将它与数组中第二个元素交换。按照这种方法一直进行下去,直到整个数组排完序。 交换次数:N-1 缺点:...
  • 排序算法中,分为稳定排序不稳定排序。一个算法是否稳定,根据排序前后排序前后相同数的相对位置是否发生变化来判断。相对位置变化的称为不稳定排序变化的称为稳定排序稳定排序分为以下四类: 冒泡...
  • 常用的内部排序方法-比较排序

    千次阅读 2017-01-22 14:58:03
    排序过程中需要对磁盘进行读写。同时,内排序也一般假定所有用到的辅助空间也可以直接存在于内存中。与之对应地,另一类排序称作外排序,即内存中无法保存全部数据,需要进行磁盘访问,每次读入部分数据到内存进行...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 94,477
精华内容 37,790
关键字:

以下不稳定的排序方法是