穩定排序

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

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 因為sort排序的不穩定，如果排序中出現相同的，則在排序時有時不一定按照先前的順序進行排序。這是在結構體中添加一個變量，用于儲存其原來的位置，當出現不穩定的情況時，可以用這個變量進行決定。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std;struct node {char bad[106];double val;int vml; }e[200]; bool cmp(node x, node y) {if (x.val == y.val) {return x.vml > y.vml;}return x.val < y.val; } int main() {int t, n;double p, vml;scanf("%d", &t);while (t--) {scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s %lf %d", e[i].bad, &e[i].val, &e[i].vml);if (e[i].vml < 200) {i--;n--;}else {if (e[i].vml/200 <= 5) {e[i].val /= e[i].vml/200;}else {e[i].val /= 5;}}}sort(e, e + n, cmp);printf("%s\n", e[0].bad);}return 0; }

轉載于:https://www.cnblogs.com/cniwoq/p/6770933.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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