第2章數(shù)據(jù)排序(C版) (1)

1、第二章 數(shù)據(jù)排序 信息獲取后通常需要進行處理，處理后的信息其目的是便于人們的應(yīng)用。信息處理方法有多種，通常有數(shù)據(jù)的排序，查找，插入，刪除，歸并等操作。讀者已經(jīng)接觸了一些這方面的知識，本章重點介紹數(shù)據(jù)排序的幾種方法。1. 選擇排序（1） 基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在待排序的數(shù)列的最前，直到全部待排序的數(shù)據(jù)元素排完。（2）排序過程：【示例】：初 始 關(guān)鍵字 49 38 65 97 76 13 27 49第一趟排序后 1338 65 97 76 49 27 49第二趟排序后 13 2765 97 76 49 38 49第三趟排序后 13 27 38 97

2、 76 49 65 49第四趟排序后 13 27 38 49 76 97 65 49第五趟排序后 13 27 38 49 49 97 65 76第六趟排序后 13 27 38 49 49 65 97 76第七趟排序后 13 27 38 49 49 65 76 97最后排序結(jié)果 13 27 38 49 49 65 76 97 例2.1 輸入n個數(shù)，將n個數(shù)按從小到大的順序輸出(n=10000)。輸入樣例: 8 49 38 65 97 76 13 27 49輸出樣例: 13 27 38 49 49 65 76 97歸納上述排序過程，具體實現(xiàn)步驟如下： 讀入數(shù)據(jù)存放在a數(shù)組中。 在a1an中選擇值最

3、小的元素，與第1位置元素交換，則把最小值元素放入a1中。 在a2an中選擇值最小的元素，與第2位置元素交換，則把最小值元素放入a2中， 直到第n-1個元素與第n個元素比較排序為止。 程序?qū)崿F(xiàn)方法：用兩層循環(huán)完成算法，外層循環(huán)i控制當(dāng)前序列最小值存放的數(shù)組位置，內(nèi)層循環(huán)j控制從i+1到n序列中選擇最小的元素所在位置k。程序如下：#includeusing namespace std;const int MAXN=10001;int main() int n,k,i,j; float temp,aMAXN; cinn; for (i=0;iai; /輸入n個數(shù) for (i=0;in;i+) /i

4、控制當(dāng)前序列中最小值存放的數(shù)據(jù)位置 k=i; for (j=i+1;jn;j+) /在當(dāng)前無序區(qū)ai.n中選最小的元素ak if (ajak) k=j; if (k!=i) /交換ai和ak，將當(dāng)前最小值放到ai位置 temp=ai;ai=ak;ak=temp; for (i=0;in;i+) coutai ; return 0; 2.冒泡排序 冒泡排序的思想：以n個人站隊為例，從第1個開始，依次比較相鄰的兩個是否逆序?qū)?高在前，矮在后)，若逆序就交換這兩人，即第1個和第2個比，若逆序就交換兩人，接著第2個和第3個比，若逆序就交換兩人，接著第3個和第4個比，若逆序就交換兩人，直到n-1和n比較

5、，經(jīng)過一輪比較后，則把最高的人排到最后，即將最高的人像冒泡一樣逐步冒到相應(yīng)的位置。原n個人的排序問題，轉(zhuǎn)換為n-1個人的排序問題。第二輪從第1個開始，依次比較相鄰的兩個人是否逆序?qū)?，若逆序就交換兩人，直到n-2和n-1比較。如此，進行n-1輪后，隊列為有序的隊列。 從上述分析中可以看出，每進行一輪的比較之后，n個數(shù)的排序規(guī)模就轉(zhuǎn)化為n-1個數(shù)的排序規(guī)模。 例如有6個元素需要排序： 6 5 3 4 1 2第一趟排序：第二趟排序：第三趟排序：第四趟排序：第五趟排序： 五趟結(jié)束后，6個整數(shù)就已經(jīng)排序完成。排序過程中，大數(shù)慢慢的往后，相當(dāng)于氣泡上升，所以叫冒泡排序。 歸納上述排序過程，具體實現(xiàn)步驟如下

6、： 讀入數(shù)據(jù)存放在a數(shù)組中。 比較相鄰的前后兩個數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將兩個數(shù)據(jù)交換。 對數(shù)組的第0個數(shù)據(jù)到n-1個數(shù)據(jù)進行一次遍歷后，最大的一個數(shù)據(jù)就“冒”到數(shù)組第n-1個位置。 n=n-1，如果n不為0就重復(fù)前面二步，否則排序完成。 程序?qū)崿F(xiàn)方法：用兩層循環(huán)完成算法，外層循環(huán)i控制每輪要進行多少次的比較，第1輪比較n-1次，第2輪比較n-2次，最后一輪比較1次。內(nèi)層循環(huán)j控制每輪i次比較相鄰兩個元素是否逆序，若逆序就交換這兩個元素?！境绦?qū)崿F(xiàn)】#includeusing namespace std;const int MAXN=10001;int main() int n,i

7、,j; float temp,aMAXN; cinn; for (i=0;iai; /輸入n個數(shù) for(i=n-1; i=1; i-) /進行n-1輪冒泡 for(j=0; jaj+1) /相鄰兩個元素比較，若逆序就交換 swap(aj, aj+1); /交換 for (i=0;in;i+) /輸出排序結(jié)果 coutai=1; i-) ok=true; /判斷是否有交換 for(int j=1; jaj+1) swap(aj,aj+1); ok=false; if(ok=true) break; /沒有交換就退出例2.2 車廂重組【問題描述】 在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中

8、心的橋墩水平旋轉(zhuǎn)。一個車站的職工發(fā)現(xiàn)橋的長度最多能容納兩節(jié)車廂，如果將橋旋轉(zhuǎn)180度，則可以把相鄰兩節(jié)車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負(fù)責(zé)用這座橋?qū)⑦M站的車廂按車廂號從小到大排列。他退休后，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序。【輸入文件】 輸入文件有兩行數(shù)據(jù)，第一行是車廂總數(shù)N（不大于10000），第二行是N個不同的數(shù)表示初始的車廂順序。【輸出文件】 一個數(shù)據(jù)，是最少的旋轉(zhuǎn)次數(shù)。【輸入樣例】 4 4 3 2 1 【輸出樣例】 6程序如下：#include#includeusing namesp

9、ace std;long n,i,j,t,s,a10000;int main() cinn; for (i=1; iai; /輸入n個車廂號 for (i=1; i=n-1; i+) /冒泡排序另一種寫法 for (j=1; jaj+1) /判斷車廂號是否逆序 swap(aj,aj+1); s+; /統(tǒng)計車廂旋轉(zhuǎn)的次數(shù) ; couts; /最少的旋轉(zhuǎn)次數(shù) return 0; 3. 插入排序 插入排序思想：回憶一下打牌時抓牌的情景，為了方便打牌，抓牌時一般一邊抓牌一邊按花色和大小插入恰當(dāng)?shù)奈恢?，?dāng)抓完所有的牌時，手中的牌便是有序的，這排序方法即插入排序。 當(dāng)讀入一個元素時，在已經(jīng)排序好的序列中，

10、搜尋它正確的位置，再放入讀入的元素。但不該忽略一個重要的問題：在插入這個元素前，應(yīng)當(dāng)先將將它后面的所有元素后移一位，以保證插入位置的原元素不被覆蓋。 例如:設(shè)n=8，數(shù)組a中8個元素是: 36,25,48,12,65,43,20,58，執(zhí)行插入排序程序后，其數(shù)據(jù)變動情況：第0步:36 25 48 12 65 43 20 58第1步:25 36 48 12 65 43 20 58第2步:25 36 48 12 65 43 20 58第3步:12 25 36 48 65 43 20 58第4步:12 25 36 48 65 43 20 58第5步:12 25 36 43 48 65 20 58第6

11、步:12 20 25 36 43 48 65 58第7步:12 20 25 36 43 48 58 65程序如下：#includeusing namespace std;const int MAXN=10001;int main() int n,i,j,k; float temp,aMAXN; cinn; for (i=0;iai; /輸入n個數(shù) for(i=0; i=0; j-) /在前面有序區(qū)間中為ai找合適的插入位置 if (ajj;k-) ak+1=ak; /將ai放在正確位置上 ak+1=temp; for (i=0;in;i+) coutai ; /輸出排序的結(jié)果 return 0

12、; 4. 桶排序 桶排序的思想是若待排序的值在一個明顯有限范圍內(nèi)(整型)時，可設(shè)計有限個有序桶，待排序的值裝入對應(yīng)的桶（當(dāng)然也可以裝入若干個值），桶號就是待排序的值，順序輸出各桶的值，將得到有序的序列。例：輸入n個0到100之間的整數(shù)，由小到大排序輸出?！境绦?qū)崿F(xiàn)】#include#include using namespace std;int main() int b101,n,i,j,k; memset(b,0,sizeof(b); /初始化 cinn; for (i=1;ik; bk+; /將等于k的值全部裝入第k桶中 for (i=0;i0) /相同的整數(shù)，要重復(fù)輸出 couti ;

13、bi-; /輸出一個整數(shù)后，個數(shù)減1 coutendl; 例2.3 明明的隨機數(shù)(Noip2006)【問題描述】 明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查，為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數(shù)（N100），對于其中重復(fù)的數(shù)字，只保留一個，把其余相同的數(shù)去掉，不同的數(shù)對應(yīng)著不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請你協(xié)助明明完成“去重”與“排序”的工作?！据斎胛募?輸入文件random.in 有2行， 第1行為1個正整數(shù)，表示所生成的隨機數(shù)的個數(shù)：N 第2行有N個用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)。【輸出文件】 輸出文件ra

14、ndom.out 也是2行，第1行為1個正整數(shù)M，表示不相同的隨機數(shù)的個數(shù)。第2行為M個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機數(shù)。【輸入樣例】 10 20 40 32 67 40 20 89 300 400 15【輸出樣例】 8 15 20 32 40 67 89 300 400【分析】 本題有一個重要的特點就是每一個數(shù)都介于0到1000之間的整數(shù),可以開設(shè)一個下標(biāo)為01000的數(shù)組b，b0記錄值為0的個數(shù),b1記錄值為1的個數(shù)，bx記錄值為x的個數(shù)，那么從小到大的順序輸出b數(shù)組值不為0的b數(shù)組下標(biāo)值。程序如下：#include#include#includeusing names

15、pace std;int main() int b1001,n,i,j,m=0,x; memset(b,0,sizeof(b); /初始化 cinn; for (i=1;ix; if (bx=0) m+; /bx為0表示x為新的隨機數(shù),m加1 bx+; /將等于x的值全部裝入第x桶中 coutmendl; /不相同的隨機數(shù)的個數(shù) for (i=0;i0) couti ; coutj為止。 快速排序的時間的復(fù)雜性是O(nlog2n)，速度快,但它是不穩(wěn)定的排序方法。就平均時間而言，快速排序是目前被認(rèn)為是最好的一種內(nèi)部排序方法 由以上討論可知，從時間上看，快速排序的平均性能優(yōu)于前面討論過的各種排序

16、方法，但快速排序需一個?？臻g來實現(xiàn)遞歸。若每一趟排序都將記錄序列均勻地分割成長度相接近的兩個子序列，則棧的最大深度為log(n+1)?？焖倥判蛩惴╲oid qsort(int l,int r) int i,j,mid,p; i=l; j=r; mid=a(l+r) / 2; /將當(dāng)前序列在中間位置的數(shù)定義為分隔數(shù) do while (aimid) j-; /在右半部分尋找比中間數(shù)小的數(shù) if (i=j) /若找到一組與排序目標(biāo)不一致的數(shù)對則交換它們 p=ai; ai=aj; aj=p; i+; j-; /繼續(xù)找 while (i=j); /注意這里不能少了等號 if (lj) qsort(l,

17、j); /若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間 if (ir) qsort(i,r);6.歸并排序 歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 例如有8個數(shù)據(jù)需要排序：10 4 6 3 8 2 5 7 歸并排序主要分兩大步：分解、合并。 合并過程為：比較ai和aj的大小，若aiaj，則將第一個有序表中的元素ai復(fù)制到rk中，并令i和k分別加上1；否則將第二個有序表中的元素aj復(fù)制

18、到rk中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實現(xiàn)，先把待排序區(qū)間s,t以中點二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間s,t?！境绦?qū)崿F(xiàn)】void msort(int s,int t) if(s=t) return; /如果只有一個數(shù)字則返回，無須排序 int mid=(s+t)/2; msort(s,mid); /分解左序列 msort(mid+1,t); /分解右序列 int i=s, j=mid+1, k=s; /

19、接下來合并 while(i=mid & j=t) if(ai=aj) rk=ai; k+; i+; else rk=aj; k+; j+; while(i=mid) /復(fù)制左邊子序列剩余 rk=ai; k+; i+; while(j=t) /復(fù)制右邊子序列剩余 rk=aj; k+; j+; for(int i=s; i1)，其中所有數(shù)字各不相同。如果存在正整數(shù) i, j 使得 1 i Aj，則 這個有序?qū)ΨQ為 A 的一個逆序?qū)?，也稱作逆序數(shù)。 例如，數(shù)組（3，1，4，5，2）的逆序?qū)τ?3,1),(3,2),(4,2),(5,2)，共4個。 所謂逆序?qū)Φ膯栴}，即對給定的數(shù)組序列，求其逆序?qū)Φ臄?shù)

20、量。 從逆序?qū)Χx上分析，逆序?qū)褪菙?shù)列中任意兩個數(shù)滿足大的在前，小的在后的組合。如果將這些逆序?qū)Χ颊{(diào)整成順序（小的在前，大的在后），那么整個數(shù)列就變的有序，即排序。因而，容易想到冒泡排序的機制正好是利用消除逆序來實現(xiàn)排序的，也就是說，交換相鄰兩個逆序數(shù)，最終實現(xiàn)整個序列有序，那么交換的次數(shù)即為逆序?qū)Φ臄?shù)量。 冒泡排序可以解決逆序?qū)栴}，但是由于冒泡排序本身效率不高，時間復(fù)雜度為O(n2)，對于n比較大的情況就沒用武之地了。我們可以這樣認(rèn)為，冒泡排序求逆序?qū)π手缘?，是因為其在統(tǒng)計逆序?qū)?shù)量的時候是一對一對統(tǒng)計的，而對于范圍為n的序列，逆序?qū)?shù)量最大可以是(n+1)*n/2，因此其效率太低

21、。那怎樣可以一下子統(tǒng)計多個，而不是一個一個累加呢？這個時候，歸并排序就可以幫我們來解決這個問題。 在合并操作中，我們假設(shè)左右兩個區(qū)間元素為: 左邊：3 4 7 9 右邊：1 5 8 10 那么合并操作的第一步就是比較3和1，然后將1取出來，放到輔助數(shù)組中，這個時候我們發(fā)現(xiàn)，右邊的區(qū)間如果是當(dāng)前比較的較小值，那么其會與左邊剩余的數(shù)字產(chǎn)生逆序關(guān)系，也就是說1和3、4、7、9都產(chǎn)生了逆序關(guān)系，我們可以一下子統(tǒng)計出有4對逆序?qū)?。接下?，4取下來放到輔助數(shù)組后，5與左邊剩下的7、9產(chǎn)生了逆序關(guān)系，我們可以統(tǒng)計出2對。依此類推，8與9產(chǎn)生1對，那么總共有4+2+1對。這樣統(tǒng)計的效率就會大大提高，便可較好

22、的解決逆序?qū)栴}。 而在算法的實現(xiàn)中，我們只需略微修改原有歸并排序，當(dāng)右邊序列的元素為較小值時，就統(tǒng)計其產(chǎn)生的逆序?qū)?shù)量，即可完成逆序?qū)Φ慕y(tǒng)計?！境绦?qū)崿F(xiàn)】void msort(int s,int t) if(s=t) return; /如果只有一個數(shù)字則返回，無須排序 int mid=(s+t)/2; msort(s,mid); /分解左序列 msort(mid+1,t); /分解右序列 int i=s, j=mid+1, k=s; /接下來合并 while(i=mid & j=t) if(ai=aj) rk=ai; k+; i+; else rk=aj; k+; j+; ans+=mid-

23、i+1; /統(tǒng)計產(chǎn)生逆序?qū)Φ臄?shù)量 while(i=mid) /復(fù)制左邊子序列剩余 rk=ai; k+; i+; while(j=t) /復(fù)制右邊子序列剩余 rk=aj; k+; j+; for(int i=s; i=t; i+) ai=ri; return 0; 其中ans+=mid-i+1這句代碼統(tǒng)計新增逆序?qū)Φ臄?shù)量，ans作為全局變量，用于統(tǒng)計逆序?qū)Φ臄?shù)量，此時ans要增加左邊區(qū)間剩余元素的個數(shù)。當(dāng)歸并排序結(jié)束后，逆序?qū)栴}也得到解決，ans即為逆序?qū)Φ臄?shù)量。8.各種排序算法的比較1.穩(wěn)定性比較 插入排序、冒泡排序、二叉樹排序、二路歸并排序及其他線形排序是穩(wěn)定的。 選擇排序、希爾排序、快速

24、排序、堆排序是不穩(wěn)定的。2.時間復(fù)雜性比較 插入排序、冒泡排序、選擇排序的時間復(fù)雜性為O(n2)；快速排序、堆排序、歸并排序的時間復(fù)雜性為O(nlog2n)；桶排序的時間復(fù)雜性為O(n); 若從最好情況考慮，則直接插入排序和冒泡排序的時間復(fù)雜度最好，為O(n)，其它算法的最好情況同平均情況相同；若從最壞情況考慮，則快速排序的時間復(fù)雜度為O(n2)，直接插入排序和冒泡排序雖然平均情況相同，但系數(shù)大約增加一倍，所以運行速度將降低一半，最壞情況對直接選擇排序、堆排序和歸并排序影響不大。 由此可知，在最好情況下，直接插入排序和冒泡排序最快；在平均情況下，快速排序最快；在最壞情況下，堆排序和歸并排序最快

25、。3.輔助空間的比較 桶排序、二路歸并排序的輔助空間為O(n)，快速排序的輔助空間為O(log2n)，最壞情況為O(n)，其它排序的輔助空間為O(1);4.其它比較 插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。反而在這種情況下，快速排序反而慢了。 當(dāng)n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。 若待排序的記錄的關(guān)鍵字在一個明顯有限范圍內(nèi)時,且空間允許是用桶排序。 當(dāng)n較大時，關(guān)鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。 當(dāng)n較大時，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對穩(wěn)定性沒有要求時宜用堆排序 快速排序是目前基于比較

26、的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短；堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的?！旧蠙C練習(xí)】1、明明的隨機數(shù)（Noip2006）【問題描述】 明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查，為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數(shù)（N100），對于其中重復(fù)的數(shù)字，只保留一個，把其余相同的數(shù)去掉，不同的數(shù)對應(yīng)著不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請你協(xié)助明明完成“去重”與“排序”的工作?！据斎胛募枯斎胛募andom.in 有2行

27、，第1行為1個正整數(shù)，表示所生成的隨機數(shù)的個數(shù)：N第2行有N個用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)?！据敵鑫募枯敵鑫募andom.out 也是2行，第1行為1個正整數(shù)M，表示不相同的隨機數(shù)的個數(shù)。第2行為M個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機數(shù)?！据斎霕永?020 40 32 67 40 20 89 300 400 15【輸出樣例】815 20 32 40 67 89 300 4002、車廂重組（carry.pas）【問題描述】 在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉(zhuǎn)。一個車站的職工發(fā)現(xiàn)橋的長度最多能容納兩節(jié)車廂，如果將橋旋轉(zhuǎn)180度，則可以把相

28、鄰兩節(jié)車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負(fù)責(zé)用這座橋?qū)⑦M站的車廂按車廂號從小到大排列。他退休后，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序?！据斎胛募?輸入文件有兩行數(shù)據(jù)，第一行是車廂總數(shù)N（不大于10000），第二行是N個不同的數(shù)表示初始的車廂順序?！据敵鑫募?一個數(shù)據(jù)，是最少的旋轉(zhuǎn)次數(shù)?！据斎霕永縞arry .in44 3 2 1 【輸出樣例】carry .out63、眾數(shù)(masses.pas)【問題描述】 由文件給出N個1到30000間無序數(shù)正整數(shù)，其中1N10000，同一個正整數(shù)可能會出

29、現(xiàn)多次，出現(xiàn)次數(shù)最多的整數(shù)稱為眾數(shù)。求出它的眾數(shù)及它出現(xiàn)的次數(shù)?！据斎敫袷健?輸入文件第一行是正整數(shù)的個數(shù)N，第二行開始為N個正整數(shù)?！据敵龈袷健?輸出文件有若干行，每行兩個數(shù)，第1個是眾數(shù)，第2個是眾數(shù)出現(xiàn)的次數(shù)。【輸入樣例】masses.in122 4 2 3 2 5 3 7 2 3 4 3【輸出樣例】masses.out2 43 45、軍事機密(Secret.pas)【問題描述】 軍方截獲的信息由n（n=30000）個數(shù)字組成，因為是敵國的高端秘密，所以一時不能破獲。最原始的想法就是對這n個數(shù)進行小到大排序，每個數(shù)都對應(yīng)一個序號，然后對第i個是什么數(shù)感興趣，現(xiàn)在要求編程完成。【輸入格式】

30、 第一行n，接著是n個截獲的數(shù)字，接著一行是數(shù)字k，接著是k行要輸出數(shù)的序號?！据敵龈袷健?k行序號對應(yīng)的數(shù)字?！据斎霕永縎ecret.in5121 1 126 123 73243【輸出樣例】Secret.out71231216、獎學(xué)金(Noip2007)【問題描述】 某小學(xué)最近得到了一筆贊助，打算拿出其中一部分為學(xué)習(xí)成績優(yōu)秀的前5名學(xué)生發(fā)獎學(xué)金。期末，每個學(xué)生都有3門課的成績：語文、數(shù)學(xué)、英語。先按總分從高到低排序，如果兩個同學(xué)總分相同，再按語文成績從高到低排序，如果兩個同學(xué)總分和語文成績都相同，那么規(guī)定學(xué)號小的同學(xué)排在前面，這樣，每個學(xué)生的排序是唯一確定的。 任務(wù)：先根據(jù)輸入的3門課的成

31、績計算總分，然后按上述規(guī)則排序，最后按排名順序輸出前5名學(xué)生的學(xué)號和總分。注意，在前5名同學(xué)中，每個人的獎學(xué)金都不相同，因此，你必須嚴(yán)格按上述規(guī)則排序。例如，在某個正確答案中，如果前兩行的輸出數(shù)據(jù)（每行輸出兩個數(shù)：學(xué)號、總分）是： 7 279 5 279 這兩行數(shù)據(jù)的含義是：總分最高的兩個同學(xué)的學(xué)號依次是7號、5號。這兩名同學(xué)的總分都是279（總分等于輸入的語文、數(shù)學(xué)、英語三科成績之和），但學(xué)號為7的學(xué)生語文成績更高一些。如果你的前兩名的輸出數(shù)據(jù)是： 5 279 7 279 則按輸出錯誤處理，不能得分。0【輸入格式】輸入文件scholar.in包含n+1行：第1行為一個正整數(shù)n，表示該校參加評

32、選的學(xué)生人數(shù)。第2到n+1行，每行有3個用空格隔開的數(shù)字，每個數(shù)字都在0到100之間。第j行的3個數(shù)字依次表示學(xué)號為j-1的學(xué)生的語文、數(shù)學(xué)、英語的成績。每個學(xué)生的學(xué)號按照輸入順序編號為1n（恰好是輸入數(shù)據(jù)的行號減1）。 所給的數(shù)據(jù)都是正確的，不必檢驗。【輸出格式】輸出文件scholar.out共有5行，每行是兩個用空格隔開的正整數(shù), 依次表示前5名學(xué)生的學(xué)號和總分?！据斎胼敵鰳永?】scholar.in690 67 8087 66 9178 89 9188 99 7767 89 6478 89 98 scholar.out 6 2654 2643 2582 2441 237 【輸入輸出樣例2】scholar.in880 89 8988 98 7890 67 8087 66 9178 89 9188 99 7767 89 6478 89 98 scholar.out 8 2652 2646 2641 2585 258【限制】 50%的數(shù)據(jù)滿足：各學(xué)生的總成績各不相同100%的數(shù)據(jù)滿足：6=n=3007、統(tǒng)計數(shù)字(Noip2007)【問題描述】 某次科研調(diào)查時得到了n個自然數(shù)，每個數(shù)均不超過1500000000（1.5*109）。已知不相同的數(shù)不超過10000個，現(xiàn)在需要統(tǒng)計這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的