xpj娱乐平台:1872稳定排序,稳定排序和不稳定排序

HDU–1872 稳固排序,hdu–1872稳固排序

大家都掌握,飞速排序是动荡的排序方法。 
大器晚成经对于数组中现身的任性aii,ajj(i<j),个中aii==ajj,在开展排序今后aii一定出将来ajj以前,则认为该排序是和煦的。 

某大学招收办获得后生可畏份成绩列表,上边记录了考生名字和考生战绩。並且对其选用了某排序算法按成绩进行依次减少排序。以往请您判断一下该排序算法是或不是科学,若是对的的话,则推断该排序算法是不是为平稳的。 
Input 本题目富含多组输入,请管理到文件截至。 
对此每组数据,第生龙活虎行有一个正整数N(0<N<300),代表战绩列表中的考生数量。 
xpj娱乐平台:1872稳定排序,稳定排序和不稳定排序。接下去有N行,每生龙活虎行有三个字符串代表考生名字(长度不超过50,仅满含’a’~’z’),和叁个子弹头代表考生疏数(小于500)。当中名字和战表用多少个空格隔断。 
再接下去又有N行,是上述列表经过某排序算法未来生成的三个系列。格式同上。
Output 对于每组数据,如若算法是不易况兼稳固的,就在黄金年代行里面输出”Right”。假如算法是无可争辩的但不是平安的,就在生机勃勃行里面输出”Not
Stable”,而且在下边输出正确牢固排序的列表,格式同输入。假诺该算法是大错特错的,就在风度翩翩行里面输出”Error”,并且在上边输出正确牢固排序的列表,格式同输入。 

介怀,本标题不考虑该排序算法是错误的,但结果是没有错的那样的竟然景况。
萨姆ple Input    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

题意:
sort直接排序可能存在不稳定性
题解:
分数不相同直接sort从高到低排序,分数如果相同,按输入名字的id的先后顺序排(这里不是按字典序排,是按名字出现的先后,即刚开始在前,排后也在前。“这个地方迷失了好久好久,当成了字典序排序...”) 
AC代码:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 struct stu
 6 {  int id; 
 7    char num[51];
 8    int score;
 9 }p[300],q[300];
10 bool cmp(stu x,stu y)
11 {
12    if(x.score!=y.score)
13        {if(x.score>y.score)
14           return true;
15         else return false;   
16         }
17    else 
18     {if(x.id<y.id)
19        return true;
20       else return false;  
21       
22     }  
23 }
24 int main()
25 {
26 int n,i,j,k;
27 while(scanf("%d",&n)!=EOF)
28   {for(i=0;i<n;i++)
29      {scanf("%s %d",p[i].num,&p[i].score);
30       p[i].id=i;     
31      }
32    for(i=0;i<n;i++)
33      scanf("%s %d",q[i].num,&q[i].score);  
34    sort(p,p+n,cmp);
35    j=0;
36    k=0;
37 
38    for(i=0;i<n;i++)
39     {if(strcmp(p[i].num,q[i].num)==0) 
40       j++;
41       if(p[i].score==q[i].score)       
42       k++;                                                           
43     }
44    if(j==n&&k==n) printf("Right\n");  
45     else if(k==n&&j!=n) 
46    {printf("Not Stable\n");
47     for(i=0;i<n;i++)
48     printf("%s %d\n",p[i].num,p[i].score);
49    } 
50    else  
51    {printf("Error\n");
52     for(i=0;i<n;i++)
53     printf("%s %d\n",p[i].num,p[i].score);
54        
55    }
56   }
57 return 0;
58 }

 

 

稳固排序,hdu–1872稳固排序
大家都驾驭,快速排序是不安静的排序方法。 借使对于数组中冒出的自便a i i,a
j j(ij),在那之中a i i==a j j,在…

转载:

 首先,排序算法的平静我们应该都精通,通俗地讲就是能确定保障排序前2个非常的数其在连串的光景地点顺序和排序后它们三个的前后地点顺序相似。在简要形式化一下,如果Ai
= Aj,Ai原本在岗位前,排序后Ai依旧要在Aj地点前。

近日笔试了好几回了,一而再碰着三个关于遍布排序算法稳固性判别的难题,往往照旧多选,对于本身以致和本人同意气风发拿不许的校友可不是叁个能随意下定论的主题素材,当然假诺你笔试此前曾经记住了数据结构书上哪些是稳固的,哪些不是平静的,做起来应当能够轻便化解。本文是针对性老是记不住那么些依然想实在掌握究竟为什么是平稳或许不平稳的人计划的。

     
其次,说一下和谐的受益。排序算法固然是牢固的,那么从三个键上排序,然后再从另多少个键上排序,第一个键排序的结果可以为第一个键排序所用。基数排序就是这么,先按未有排序,逐次按高位排序,低位肖似的成分其顺序再高位也雷同不时间是不会变动的。其它,如若排序算法稳定,对依靠相比的排序算法来说,成分交流的次数可能会少一些(个人感到,未有证实卡塔 尔(阿拉伯语:قطر‎。

第风姿罗曼蒂克,排序算法的稳固大家应该都驾驭,通俗地讲正是能作保排序前2个非常的数其在种类的光景地方顺序和排序后它们多少个的前后地方顺序相仿。在精练格局化一下,若是Ai
= Aj,Ai原本在岗位前,排序后Ai依旧要在Aj地方前。

归来大旨,今后深入分析一下广大的排序算法的安宁,每种都付出轻松的理由。

扶助,说一下牢固的补益。排序算法假若是安静的,那么从三个键上排序,然后再从另贰个键上排序,第4个键排序的结果可感觉第三个键排序所用。基数排序便是那样,先按未有排序,逐次按高位排序,低位雷同的因素其顺序再高位也相通一时候是不会变动的。其余,假诺排序算法牢固,对基于相比的排序算法来说,成分交流的次数大概会少一些(个人感到,未有证实卡塔尔国。

(1)冒泡排序

归来宗旨,今后解析一下科学普及的排序算法的心花怒放,每种都提交简单的理由。

冒泡排序正是把小的要素往前调大概把大的成分未来调。相比较是周边的三个因素相比,调换也爆发在这里四个因素之间。所以,假设八个要素相等,笔者想你是不会再俗气地把她们俩沟通一下的;假若四个格外的要素未有相邻,那么尽管通过后面的两两换来把多少个相邻起来,这时也不会换到,所以风度翩翩律成分的光景相继并不曾改革,所以冒泡排序是黄金年代种稳定排序算法。

(1)冒泡排序

(2)选取排序

冒泡排序正是把小的要素往前调或然把大的要素将来调。相比较是左近的多少个成分相比较,交换也发生在这里五个因素之间。所以,假如八个要素相等,笔者想你是不会再俗气地把她们俩换到一下的;要是四个分外的因素未有相邻,那么尽管通过后面包车型大巴两两置换把多个相邻起来,这个时候也不会换换,所以意气风发律成分的左右相继并未校正,所以冒泡排序是风度翩翩种和谐排序算法。

选料排序是给每一个岗位选取当前因素最小的,譬喻给第贰个职位接收最小的,在剩余元素里面给第一个要素选拔第二小的,依次类推,直到第n

1个因素,第n个要素不用选拔了,因为只剩下它三个最大的成分了。那么,在生龙活虎趟选取,假若当前因素比贰个因素小,而该小的要素又冒出在八个和脚下因素相等的成分后边,那么调换后稳固性就被磨损了。相比刚强,举个例证,连串5
8 5 2
9,大家领会第二次选拔第四个成分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次相比和沟通卡塔 尔(英语:State of Qatar),然后把种种有序的段连串归总成二个稳步的长类别,不断统一向到原连串全体排好序。能够开采,在1个或2个要素时,1个成分不会换换,2个因素假如大小约等于也还未有人有意识沟通,那不会毁掉牢固性。那么,在短的不改变类别归并的进度中,牢固是是或不是受到毁坏?未有,合併进度中大家得以确认保证要是五个当前因素相等时,我们把远在前边的类别的因素保存在结果系列的前头,那样就保证了地西泮。所以,合并列排在一条线序也是稳定的排序算法。

(6)基数排序 
基数排序是服从低位先排序,然后采摘;再依据高位排序,然后再搜罗;依次类推,直到最高位。不常候有些属性是有优先级依次的,先按低优先级排序,再按高优先级排序,最终的程序正是高优先级高的在前,高优先级雷同的低优先级高的在前。基数排序基于各自排序,分别访问,所以其是稳定的排序算法。

(7)Hill排序(shell) 
Hill排序是鲁人持竿不一致幅度对成分进行插入排序,当刚最先成分很严节的时候,步长最大,所以插入排序的要素个数比超少,速度快速;当成分基本不变了,步长相当小,
插入排序对于有序的行列作用极高。所以,Hill排序的时光复杂度会比O(n^2)好一些。由于一再插入排序,大家领会一遍插入排序是平安的,不会改动肖似成分的周旋顺序,但在差异的插入排序进程中,相像的元素恐怕在分其余插入排序中活动,最后其牢固就能够被打乱,所以shell排序是不稳定的。

(8)堆排序 
大家明白堆的组织是节点i的孩子为2 * i和2 * i +
1节点,大顶堆必要父节点大于等于其2个子节点,小顶堆供给父节点小于等于其2个子节点。在二个长为n
的行列,堆排序的长河是从第n /
2开头和其子节点共3个值接纳最大(大顶堆卡塔 尔(英语:State of Qatar)或许最小(小顶堆卡塔 尔(英语:State of Qatar),这3个元素之间的拈轻怕重自然不会损坏牢固性。但当为n
/ 2 – 1, n / 2 – 2, …
1那个个父节点选取成分时,就能够毁掉牢固性。有希望第n /
2个父节点交流把前面贰个因素沟通过去了,而第n / 2 –
1个父节点把前边多少个等同的成分没有调换,那么那2个大器晚成律的因素之间的安澜就被破坏了。所以,堆排序不是和煦的排序算法。

综上,得出结论: 选用排序、急忙排序、希尔排序、堆排序不是谐和的排序算法,而冒泡排序、插入排序、归总列排在一条线序和基数排序是安居乐业的排序算法

(2)选择排序

分选排序是给每一个岗位采用当前因素最小的,比方给第贰个地方选拔最小的,在剩余成分里面给第三个因素采取第二小的,依次类推,直到第n

相关文章