穩定排序就是相同元素排序后次序不會發生改變的排序方法.

冒泡是穩定排序.

快一點的歸并也是穩定排序.

?

　　　　　　　　　　　　　　　穩定排序

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2766????Accepted Submission(s): 1081

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）——全真模擬

?

Recommend lcy #include <stdio.h> #include <string.h> #include <string> #include <iostream> using namespace std;struct node {char str[100];int key; };node g[300],g1[300];int main() {int n;while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++){scanf("%s %d",g[i].str,&g[i].key);}for(int i=0;i<n;i++)scanf("%s %d",g1[i].str,&g1[i].key);for(int i=0;i<n;i++)for(int j=i;j>0;j--){if(g[j].key>g[j-1].key) {char tmp[100];strcpy(tmp,g[j-1].str);strcpy(g[j-1].str,g[j].str);strcpy(g[j].str,tmp);int tt;tt=g[j].key;g[j].key=g[j-1].key;g[j-1].key=tt;}}int flag=0;for(int i=0;i<n;i++){if(g1[i].key!=g[i].key){flag=1;break;}}if(flag==1){printf("Error\n");for(int i=0;i<n;i++)printf("%s %d\n",g[i].str,g[i].key);continue;}for(int i=0;i<n;i++){if(strcmp(g1[i].str,g[i].str)!=0){flag=1;break;}}if(flag==1){printf("Not Stable\n");for(int i=0;i<n;i++)printf("%s %d\n",g[i].str,g[i].key);continue;}printf("Right\n");}return 0; }

?

　 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu 1872(稳定排序)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。