精华内容
下载资源
问答
  • 稳定排序

    2019-05-18 23:15:17
    大家都知道,快速排序是不稳定排序方法。 如果对于数组中出现的任意a[i],a[j](i<j),其中a[i]==a[j],在进行排序以后a[i]一定出现在a[j]之前,则认为该排序稳定的。 某高校招生办得到一份成绩列表,上面记录了...

    Problem Description

    大家都知道,快速排序是不稳定的排序方法。
    如果对于数组中出现的任意a[i],a[j](i<j),其中a[i]==a[j],在进行排序以后a[i]一定出现在a[j]之前,则认为该排序是稳定的。

    某高校招生办得到一份成绩列表,上面记录了考生名字和考生成绩。并且对其使用了某排序算法按成绩进行递减排序。现在请你判断一下该排序算法是否正确,如果正确的话,则判断该排序算法是否为稳定的。

    Input

    本题目包含多组输入,请处理到文件结束。
    对于每组数据,第一行有一个正整数N(0<N<300),代表成绩列表中的考生数目。
    接下来有N行,每一行有一个字符串代表考生名字(长度不超过50,仅包含'a'~'z'),和一个整数代表考生分数(小于500)。其中名字和成绩用一个空格隔开。
    再接下来又有N行,是上述列表经过某排序算法以后生成的一个序列。格式同上。

    Output

    对于每组数据,如果算法是正确并且稳定的,就在一行里面输出"Right"。如果算法是正确的但不是稳定的,就在一行里面输出"Not Stable",并且在下面输出正确稳定排序的列表,格式同输入。如果该算法是错误的,就在一行里面输出"Error",并且在下面输出正确稳定排序的列表,格式同输入。

    注意,本题目不考虑该排序算法是错误的,但结果是正确的这样的意外情况。

    Sample Input

    3

    aa 10

    bb 10

    cc 20

    cc 20

    bb 10

    aa 10

    3

    aa 10

    bb 10

    cc 20

    cc 20

    aa 10

    bb 10

    3

    aa 10

    bb 10

    cc 20

    aa 10

    bb 10

    cc 20

    Sample Output

    Not Stable

    cc 20

    aa 10

    bb 10

    Right

    Error

    cc 20

    aa 10

    bb 10

    Author

    linle

    Source

    2008浙大研究生复试热身赛(2)——全真模拟

     

    思路

    建立两个数组,一组用来存用标准方法排序的序列,一组用来存题目给出的序列,比较两组数组即可

    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    struct f{//构建结构体
    
           char s[100];
    
           int x,d;
    
    };
    
    bool cmp(f n,f m)//排序方法重载
    
    {
    
           if(n.x==m.x)//若分数相同,则按入列序号从小到大排序
    
           return n.d<m.d;
    
           else //否则按分数从大到小排序
    
           return n.x>m.x;
    
    }
    
    int main()
    
    {
    
           int n,i,j;
    
           struct f a[1001];
    
           struct f b[1001];
    
           while(scanf("%d",&n)!=EOF)
    
           {
    
                  for(i=0;i<n;i++)
    
                  {
    
                         scanf("%s %d",&a[i].s,&a[i].x);//输入原序列
    
                         a[i].d=i;//记录入列序号
    
                  }
    
                  sort(a,a+n,cmp);//结构体排序
    
                  int f=0;
    
                  for(i=0;i<n;i++)
    
                  {
    
                         scanf("%s %d",&b[i].s,&b[i].x);//输入改变后的序列
    
                         b[i].d=0;
    
                         if(f<2)
    
                         {
    
                                if(strcmp(b[i].s,a[i].s)!=0)//比较函数,比较该序列的名字是否正确
    
                                f=1;
    
                                if(b[i].x!=a[i].x)// 比较该序列的分数是否正确
    
                                f=2;
    
                         }
    
                  }
    
                  if(f==0)//若全正确
    
                  printf("Right\n");
    
                  else
    
                  {
    
                         if(f==1)//若名字错误
    
                         printf("Not Stable\n");
    
                         else if(f==2)//若分数错误
    
                printf("Error\n");
    
                for(i=0;i<n;i++)//输出正确的排序
    
                printf("%s %d\n",a[i].s,a[i].x);
    
                  }
    
           }
    
           return 0;
    
    }
    
    

     

    展开全文
  • 稳定排序与不稳定排序分类① 稳定性排序:② 不稳定性排序: 分类 ① 稳定性排序: 冒泡排序,插入排序、归并排序、基数排序 ② 不稳定性排序: 选择排序、快速排序、希尔排序、堆排序 参考链接:...

    分类

    ① 稳定性排序:

    冒泡排序,插入排序、归并排序、基数排序

    ② 不稳定性排序:

    选择排序、快速排序、希尔排序、堆排序

    参考链接:https://www.cnblogs.com/yadiel-cc/p/11829360.html

    展开全文
  • 稳定排序、非稳定排序稳定排序排序分类稳定排序好处 稳定排序 稳定排序: 待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj(即i&lt;j).若在排序后的序列中Ri仍然领先于...

    稳定排序、非稳定排序

    稳定排序

    稳定排序:

    待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj(即i<j).若在排序后的序列中Ri仍然领先于Rj,则称所用的方法是稳定的。

    参考 这儿
    顾名思义,不能满足上述条件的,就是非稳定排序了。

    排序分类

    哪些是稳定排序,哪些是非稳定排序呢?
    稳定:

    插入排序
    基数排序
    归并排序
    冒泡排序
    计数排序

    非稳定排序

    快速排序,希尔排序,简单选择排序,堆排序1

    稳定排序好处

    说了这么多,当然是有好处的,不然谁会用呢?
    举个简单的列子吧:

    比如我们先根据数值进行排序,得到的稳定排序结果是:

    a[0][z] a[1][y] a[2][x] a[2][y] a[2][x] a[3][z]

    如果我们想对排序后的结果,再根据x, y , z 进行排序,我们希望是基于已有的重新再做一次排序。

    a[2][x] a[2][x] a[1][y] a[2][y] a[0][z] a[3][z]

    非稳定排序得到的结果有可能是:

    a[2][x] a[2][x] a[1][y] a[2][y] a[0][z] a[3][z]

    或者

    a[2][x] a[2][x] a[2][y] a[1][y] a[0][z] a[3][z]

    对比两次的结果来看,已经排序好的顺序都不会被改变,否则非稳定排序的第二种结果,就不是我们希望看到的了。


    1. 注脚的解释 ↩︎

    展开全文
  • 稳定排序和不稳定排序

    千次阅读 2019-07-01 14:30:35
    通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同,则称之为稳定排序,在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前则为稳定排序,...

    转载自:https://www.cnblogs.com/ella-ella/p/3775833.html

    稳定排序和不稳定排序的区别:

           通俗地讲就是能保证排序前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个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    展开全文
  • 排序算法问题:稳定排序与不稳定排序

    万次阅读 多人点赞 2019-05-26 12:52:02
    稳定排序和不稳定排序 这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据...
  • 稳定排序与不稳定排序的区别

    千次阅读 2020-03-10 12:48:29
    稳定排序与不稳定排序的区别-2020-3-10 假设有两数A和B相等, 在初始末排序状态时A排在B之前, 排序后如果可以保证A仍然在B之前, 则称为稳定排序,否则为不稳定排序。 ...
  • 如果队列中存在两个相等的数字排序过程中 这两个数字的先后顺序如果不会发生变化 就叫做稳定的排序反之叫做不稳定 参考文章:稳定排序和不稳定排序. ...
  • 稳定排序与不稳定排序方法

    千次阅读 2018-08-28 17:52:15
    稳定排序与不稳定排序方法  首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在...
  • 稳定排序算法(if(ai == aj &amp;&amp; i &lt; j):aftersort(i &lt; j))冒泡排序:冒泡排序将最大值或最小值排到队首或队尾,通过比较相邻元素大小进行交换,故而每次只改变两个相邻元素位置,不...
  • 稳定排序 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10289 Accepted Submission(s): 3742 Problem Description 大家都知道,快速排序是不稳定的排序...
  • 内部排序 稳定排序稳定排序

    千次阅读 2014-10-15 17:10:50
    如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当
  • 转载自:https://www.cnblogs.com/tigerson/p/7156648.html 稳定排序的使用情景: 一个物品有多个属性:价格,销量,要求对价格升序的同时销量也升序。显然需要稳定的算法。...
  • 稳定排序和不稳定排序 转自https://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html    首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和...
  • 稳定排序和不稳定排序分析

    千次阅读 2016-08-23 23:25:12
    稳定排序和不稳定排序  这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据...
  • 稳定排序 指的是相等的元素排序完成后,其顺序保持不变。 用途 例如: 每周考试之后,按照分数高低进行排序,但是分数相同的同学怎么办呢?按照上次的分数来分高低。上次分数高的排在前面。 班级同学排序,按照学号...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,824
精华内容 8,329
关键字:

稳定排序