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

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

2、13 27 38 97 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 void SelectSort(int R) /對(duì)R1.N進(jìn)行直接選擇排序 for (int i=1;i=n-1;i+) /做N - 1趟選擇排序 K = I; For (int j=i+1;j=n;j+) /在當(dāng)前無(wú)序區(qū)RI.N中選最小的元素RK I

3、f (RJ RK) K = J; If (K!=I) /交換RI和RK Temp = RI; RI = RK; RK = Temp; /SelectSort2.冒泡排序冒泡排序（1）基本的冒泡排序 基本思想依次比較相鄰的兩個(gè)數(shù)，把大的放前面，小的放后面。即首先比較第1個(gè)數(shù)和第2個(gè)數(shù)，大數(shù)放前,小數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù).直到比較最后兩個(gè)數(shù)。第一趟結(jié)束，最小的一定沉到最后。重復(fù)上過(guò)程,仍從第1個(gè)數(shù)開(kāi)始,到最后第2個(gè)數(shù)，然后.由于在排序過(guò)程中總是大數(shù)往前，小數(shù)往后，相當(dāng)氣泡上升，所以叫冒泡排序。下面是6個(gè)元素的排序的過(guò)程 4 5 7 1 2 3 5 4 7 1 2 3 5 7 4 1 2

4、 3 5 7 4 1 2 3 5 7 4 2 1 3 第一趟結(jié)束第一趟結(jié)束 5 7 4 2 3 7 5 4 2 3 1 7 5 4 2 3 1 7 5 4 2 3 1 第二趟結(jié)束第二趟結(jié)束 7 5 4 3 1 7 5 4 3 2 1 7 5 4 3 2 1 第三趟結(jié)束第三趟結(jié)束 7 5 4 2 1 7 5 4 3 2 1 第四趟結(jié)束第四趟結(jié)束 7 5 3 2 1 第五趟結(jié)束第五趟結(jié)束 4 3 2 1算法實(shí)現(xiàn)算法實(shí)現(xiàn) for (int i=1;i=n-1;i+) for (int j=1;j=n-i;j+) if (ajaj+1) temp=aj; aj=aj+1; aj+1=temp; （2）

5、改進(jìn)）改進(jìn) 上例中，可以發(fā)現(xiàn)，第二趟結(jié)束已經(jīng)排好序。但是計(jì)算機(jī)此時(shí)并不知道已經(jīng)排好序。上例中，可以發(fā)現(xiàn)，第二趟結(jié)束已經(jīng)排好序。但是計(jì)算機(jī)此時(shí)并不知道已經(jīng)排好序。所以，還需進(jìn)行一次比較，如果沒(méi)有發(fā)生任何數(shù)據(jù)交換，則知道已經(jīng)排好序，可以不干所以，還需進(jìn)行一次比較，如果沒(méi)有發(fā)生任何數(shù)據(jù)交換，則知道已經(jīng)排好序，可以不干了。因此第三趟比較還需進(jìn)行，第四趟、第五趟比較則不必要。了。因此第三趟比較還需進(jìn)行，第四趟、第五趟比較則不必要。 我們?cè)O(shè)置一個(gè)布爾變量我們?cè)O(shè)置一個(gè)布爾變量bo 來(lái)記錄是否有進(jìn)行交換。值為來(lái)記錄是否有進(jìn)行交換。值為false表示本趟中進(jìn)行了交換，表示本趟中進(jìn)行了交換，true 則沒(méi)有。代碼

6、如下則沒(méi)有。代碼如下:int i=1;do bo=true; for (int j=1;j=n-i;j+) if (ajaj+1) temp=aj; aj=aj+1; aj+1=temp; bo=false; i+;while (!bo);3. 桶排序 桶排序的思想是若待排序的記錄的關(guān)鍵字在一個(gè)明顯有限范圍內(nèi)(整型)時(shí)，可設(shè)計(jì)有限個(gè)有序桶，每個(gè)桶裝入一個(gè)值（當(dāng)然也可以裝入若干個(gè)值），順序輸出各桶的值，將得到有序的序列。例：輸入n個(gè)0到100之間的不相同整數(shù)，由小到大排序輸出。#include#include using namespace std;int main() int b101,k,i

7、,n; memset(b,0,sizeof(b); /初始化 cinn; for( i=1;ik; bk+; /將關(guān)鍵字等于k的值全部裝入第k桶 for( i=0; i0) couti ;bi-; /輸出排序結(jié)果 coutendl;4. 插入排序插入排序 插入排序是一種簡(jiǎn)單的排序方法，其算法的基本思想是： 假設(shè)待排序的數(shù)據(jù)存放在數(shù)組R1.n中，增加一個(gè)哨兵結(jié)點(diǎn)x。(1) R1自成1個(gè)有序區(qū)，無(wú)序區(qū)為R2.n;(2) 從i=2起直至i=n為止，將Ri放在恰當(dāng)?shù)奈恢?，使R1.i數(shù)據(jù)序列有序; x:=Ri; 將x與前i-1個(gè)數(shù)比較 , j:=i-1; while xaj do j:=j-1; 將R數(shù)

8、組的元素從j位置開(kāi)始向后移動(dòng): for k:=i downto j do ak:=ak-1; Rj=x;(3) 生成包含n個(gè)數(shù)據(jù)的有序區(qū)。. 例如:設(shè)n=8，數(shù)組R中8個(gè)元素是: 36,25,48,12,65,43,20,58，執(zhí)行插入排序程序后，其數(shù)據(jù)變動(dòng)情況：第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步:12

9、 20 25 36 43 48 65 58第7步:12 20 25 36 43 48 58 65該算法的程序簡(jiǎn)單，讀者自己完成。其算法的時(shí)間復(fù)雜性為該算法的程序簡(jiǎn)單，讀者自己完成。其算法的時(shí)間復(fù)雜性為O(n2)插入排序適插入排序適用于原先數(shù)據(jù)已經(jīng)排列好，插入一個(gè)新數(shù)據(jù)的情況。用于原先數(shù)據(jù)已經(jīng)排列好，插入一個(gè)新數(shù)據(jù)的情況。void insertsort(int r) /對(duì)r1.n按遞增序進(jìn)行插入排序，x是監(jiān)視哨 for (i=2;i=n;i+) /依次插入r2,.,rn x=ri; j= i-1; while (xj為止。 快速排序的時(shí)間的復(fù)雜性是O(nlog2n)，速度快,但它是不穩(wěn)定的排序方

10、法。就平均時(shí)間而言，快速排序是目前被認(rèn)為是最好的一種內(nèi)部排序方法 由以上討論可知，從時(shí)間上看，快速排序的平均性能優(yōu)于前面討論過(guò)的各種排序方法，但快速排序需一個(gè)?？臻g來(lái)實(shí)現(xiàn)遞歸。若每一趟排序都將記錄序列均勻地分割成長(zhǎng)度相接近的兩個(gè)子序列，則棧的最大深度為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ù)對(duì)則交換它們p

11、=ai; ai=aj; aj=p; i+; j-; /繼續(xù)找 while (i=j); /注意這里不能有等號(hào) if (lj) qsort(l,j); /若未到兩個(gè)數(shù)的邊界，則遞歸搜索左右區(qū)間 if (ir) qsort(i,r);6.歸并排序歸并排序 將兩個(gè)或兩個(gè)以上有序的數(shù)列(或有序表)，合并成一個(gè)仍然有序的數(shù)列(有序表)，這種操作稱(chēng)為歸并操作。這樣的方法經(jīng)常用于多個(gè)有序的數(shù)據(jù)文件歸并成一個(gè)有序的數(shù)據(jù)文件。若將兩個(gè)有序表合并成一個(gè)有序表則稱(chēng)為二路歸并，同理，有三路歸并、四路歸并等。二路歸并比較簡(jiǎn)單，所以我們只討論二路歸并。例如有兩個(gè)有序表: (7，10，13，15)和(4，8，19，20)，

12、歸并后得到的有序表為: (4，7，8，10，13，15，19，20)。 歸并過(guò)程為:比較Ai和Aj的大小，若AiAj，則將第一個(gè)有序表中的元素Ai復(fù)制到Rk中，并令i和k分別加1，即使之分別指問(wèn)后一單元，否則將第二個(gè)有序表中的元素Aj復(fù)制到Rk中，并令j和k分別加1;如此循環(huán)下去，直到其中的一個(gè)有序表取完,然后再將另一個(gè)有序表中剩余的元素復(fù)制到R中從下標(biāo)k到下標(biāo)t的單元.二路歸并算法描述為二路歸并算法描述為(As,t中的數(shù)據(jù)由小到大合并到中的數(shù)據(jù)由小到大合并到Rs,t中中):void merge(int s, int m,int t) /兩個(gè)有序表As,m和Am+1,t合并成一個(gè)有序表Rs,t

13、 /s是第一個(gè)有序表起點(diǎn)位置，m+1是第二個(gè)有序表的起點(diǎn) i=s; j=m+1; k=s; /i和j分別指向二個(gè)有序表的頭部 while (i=m&j=t) if (Ai =Aj ) Rk=Ai; i+; k+; else Rk=Aj; j+; k+; while (i=m) Rk=Ai; i+; k+; /復(fù)制第一路剩余 while ( j=t) Rk=Aj; j+; k+; /復(fù)制第二路剩余 歸并排序(Merge sort)就是利用歸并操作把一個(gè)無(wú)序表排列成一個(gè)有序表的過(guò)程。二路歸并排序的過(guò)程是首先把待排序區(qū)間（即無(wú)序表）中的每一個(gè)元素都看作為一個(gè)有序表，則n個(gè)元素構(gòu)成n個(gè)有序表，

14、接著兩兩歸并（即第一個(gè)表同第二個(gè)表歸并，第三個(gè)表同第四個(gè)表歸并，），得到n/2個(gè)長(zhǎng)度為2的有序表（最后一個(gè)表的長(zhǎng)度可能小于2），稱(chēng)此為一趟歸并，然后再兩兩有序表歸并，得到n/2/2個(gè)長(zhǎng)度為4的有序表（最后一個(gè)表的長(zhǎng)度可能小于4），如此進(jìn)行下去，直到歸并第log2n趟后得到一個(gè)長(zhǎng)度為n的有序表為止。 歸并排序算法我們用遞歸實(shí)現(xiàn)，先把待排序區(qū)間s,t以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間s,t。對(duì)左右子區(qū)間的排序與原問(wèn)題一樣，所以我們可以調(diào)用同樣的子程序，只是區(qū)間大小不一樣。歸并排序程序如下：歸并排序程序如下：program ex_

15、2;#includeusing namespace std;int a10001,r10001,n,i;/a是待排序數(shù)組，是待排序數(shù)組，r是臨時(shí)數(shù)組是臨時(shí)數(shù)組void mergesort(int s,int t) /對(duì)對(duì)s,t區(qū)間的無(wú)序數(shù)據(jù)進(jìn)行歸并排序區(qū)間的無(wú)序數(shù)據(jù)進(jìn)行歸并排序 int m,i,j,k; if (s=t) return; /若區(qū)間只有一個(gè)數(shù)據(jù)就不用排了若區(qū)間只有一個(gè)數(shù)據(jù)就不用排了 m = (s+t) / 2; /取區(qū)間的中點(diǎn)取區(qū)間的中點(diǎn) mergesort(s,m); /以中點(diǎn)二分，對(duì)左邊了區(qū)間進(jìn)行排序以中點(diǎn)二分，對(duì)左邊了區(qū)間進(jìn)行排序 mergesort(m+1,t); /以中

16、點(diǎn)二分，對(duì)右邊了區(qū)間進(jìn)行排序以中點(diǎn)二分，對(duì)右邊了區(qū)間進(jìn)行排序 i = s; /以下是一次歸并（合并）操作以下是一次歸并（合并）操作 j = m+1; k = s; while (i=m&j=t) do /二個(gè)子序列從小大到合并，直到有一列結(jié)束二個(gè)子序列從小大到合并，直到有一列結(jié)束 if (ai=aj ) rk = ai; i+; k+; else rk = aj; j+; k+; while (i=m) /*把左邊子序列剩余的元素接入進(jìn)來(lái)把左邊子序列剩余的元素接入進(jìn)來(lái)* rk = ai; i+; k+; while (j=t) /把右邊子序列剩余的元素接入進(jìn)來(lái)把右邊子序列剩余的元素接入

17、進(jìn)來(lái) rk = aj; j+; k+; for (i=s ;in; for(i=1;iai; mergesort(1,n); /對(duì)對(duì)1,n區(qū)間的無(wú)序數(shù)據(jù)進(jìn)行歸并排序區(qū)間的無(wú)序數(shù)據(jù)進(jìn)行歸并排序 for (i = 1;i=n;i+) /輸出輸出n個(gè)有序的數(shù)據(jù)個(gè)有序的數(shù)據(jù) coutai ; coutendl;7.各種排序算法的比較各種排序算法的比較1.穩(wěn)定性比較 插入排序、冒泡排序、二叉樹(shù)排序、二路歸并排序及其他線形排序是穩(wěn)定的。 選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的。2.時(shí)間復(fù)雜性比較 插入排序、冒泡排序、選擇排序的時(shí)間復(fù)雜性為O(n2)；快速排序、堆排序、歸并排序的時(shí)間復(fù)雜性為O(nl

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

19、1);4.其它比較 插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時(shí)，這種排序能達(dá)到較快的速度。反而在這種情況下，快速排序反而慢了。 當(dāng)n較小時(shí)，對(duì)穩(wěn)定性不作要求時(shí)宜用選擇排序，對(duì)穩(wěn)定性有要求時(shí)宜用插入或冒泡排序。 若待排序的記錄的關(guān)鍵字在一個(gè)明顯有限范圍內(nèi)時(shí),且空間允許是用桶排序。 當(dāng)n較大時(shí)，關(guān)鍵字元素比較隨機(jī)，對(duì)穩(wěn)定性沒(méi)要求宜用快速排序。 當(dāng)n較大時(shí)，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對(duì)穩(wěn)定性沒(méi)有要求時(shí)宜用堆排序 快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出

20、現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的?！旧蠙C(jī)練習(xí)上機(jī)練習(xí)】1、明明的隨機(jī)數(shù)（、明明的隨機(jī)數(shù)（Noip2006）【問(wèn)題描述問(wèn)題描述】 明明想在學(xué)校中請(qǐng)一些同學(xué)一起做一項(xiàng)問(wèn)卷調(diào)查，為了實(shí)驗(yàn)的客觀性，他先用計(jì)算機(jī)生成了N個(gè)1到1000之間的隨機(jī)整數(shù)（N100），對(duì)于其中重復(fù)的數(shù)字，只保留一個(gè)，把其余相同的數(shù)去掉，不同的數(shù)對(duì)應(yīng)著不同的學(xué)生的學(xué)號(hào)。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請(qǐng)你協(xié)助明明完成“去重”與“排序”的工作?！据斎胛募斎胛募枯斎胛募andom.in 有2行，第1行為1個(gè)正整數(shù)，表示所生成的隨機(jī)數(shù)的個(gè)數(shù)：N第2行有N個(gè)用空格隔開(kāi)的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)?！据敵?/p>

21、文件輸出文件】輸出文件random.out 也是2行，第1行為1個(gè)正整數(shù)M，表示不相同的隨機(jī)數(shù)的個(gè)數(shù)。第2行為M個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大排好序的不相同的隨機(jī)數(shù)?！据斎霕永斎霕永?020 40 32 67 40 20 89 300 400 15【輸出樣例輸出樣例】815 20 32 40 67 89 300 4002、車(chē)廂重組（、車(chē)廂重組（carry.pas）【問(wèn)題描述問(wèn)題描述】 在一個(gè)舊式的火車(chē)站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉(zhuǎn)。一個(gè)車(chē)站的職工發(fā)現(xiàn)橋的長(zhǎng)度最多能容納兩節(jié)車(chē)廂，如果將橋旋轉(zhuǎn)180度，則可以把相鄰兩節(jié)車(chē)廂的位置交換，用這種方法可以重新排列車(chē)廂的順序。于是他

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

23、多的整數(shù)稱(chēng)為眾數(shù)。求出它的眾數(shù)及它出現(xiàn)的次數(shù)?！据斎敫袷捷斎敫袷健?輸入文件第一行是正整數(shù)的個(gè)數(shù)N，第二行開(kāi)始為N個(gè)正整數(shù)?！据敵龈袷捷敵龈袷健?輸出文件有若干行，每行兩個(gè)數(shù)，第1個(gè)是眾數(shù)，第2個(gè)是眾數(shù)出現(xiàn)的次數(shù)?！据斎霕永斎霕永縨asses.in122 4 2 3 2 5 3 7 2 3 4 3【輸出樣例輸出樣例】masses.out2 43 45、軍事機(jī)密軍事機(jī)密(Secret.pas)【問(wèn)題描述問(wèn)題描述】 軍方截獲的信息由n（n=30000）個(gè)數(shù)字組成，因?yàn)槭菙硣?guó)的高端秘密，所以一時(shí)不能破獲。最原始的想法就是對(duì)這n個(gè)數(shù)進(jìn)行小到大排序，每個(gè)數(shù)都對(duì)應(yīng)一個(gè)序號(hào)，然后對(duì)第i個(gè)是什么數(shù)感興趣，

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

25、同學(xué)排在前面，這樣，每個(gè)學(xué)生的排序是唯一確定的。 任務(wù)：先根據(jù)輸入的3門(mén)課的成績(jī)計(jì)算總分，然后按上述規(guī)則排序，最后按排名順序輸出前5名學(xué)生的學(xué)號(hào)和總分。注意，在前5名同學(xué)中，每個(gè)人的獎(jiǎng)學(xué)金都不相同，因此，你必須嚴(yán)格按上述規(guī)則排序。例如，在某個(gè)正確答案中，如果前兩行的輸出數(shù)據(jù)（每行輸出兩個(gè)數(shù)：學(xué)號(hào)、總分）是： 7 279 5 279 這兩行數(shù)據(jù)的含義是：總分最高的兩個(gè)同學(xué)的學(xué)號(hào)依次是7號(hào)、5號(hào)。這兩名同學(xué)的總分都是279（總分等于輸入的語(yǔ)文、數(shù)學(xué)、英語(yǔ)三科成績(jī)之和），但學(xué)號(hào)為7的學(xué)生語(yǔ)文成績(jī)更高一些。如果你的前兩名的輸出數(shù)據(jù)是： 5 279 7 279 則按輸出錯(cuò)誤處理，不能得分。0【輸入格式輸

26、入格式】輸入文件scholar.in包含n+1行：第1行為一個(gè)正整數(shù)n，表示該校參加評(píng)選的學(xué)生人數(shù)。第2到n+1行，每行有3個(gè)用空格隔開(kāi)的數(shù)字，每個(gè)數(shù)字都在0到100之間。第j行的3個(gè)數(shù)字依次表示學(xué)號(hào)為j-1的學(xué)生的語(yǔ)文、數(shù)學(xué)、英語(yǔ)的成績(jī)。每個(gè)學(xué)生的學(xué)號(hào)按照輸入順序編號(hào)為1n（恰好是輸入數(shù)據(jù)的行號(hào)減1）。 所給的數(shù)據(jù)都是正確的，不必檢驗(yàn)?！据敵龈袷捷敵龈袷健枯敵鑫募cholar.out共有5行，每行是兩個(gè)用空格隔開(kāi)的正整數(shù), 依次表示前5名學(xué)生的學(xué)號(hào)和總分?！据斎胼敵鰳永斎胼敵鰳永?】scholar.in690 67 8087 66 9178 89 9188 99 7767 89 6478

27、 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ù)滿(mǎn)足：各學(xué)生的總成績(jī)各不相同100%的數(shù)據(jù)滿(mǎn)足：6=n=3007、統(tǒng)計(jì)數(shù)字、統(tǒng)計(jì)數(shù)字(Noip2007)【問(wèn)題描述問(wèn)題描述】 某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò)1500000000（1.5*109）。已知不相同的數(shù)不

28、超過(guò)10000個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計(jì)結(jié)果?！据斎敫袷捷斎敫袷健?輸入文件count.in包含n+1行： 第1行是整數(shù)n，表示自然數(shù)的個(gè)數(shù)。 第2n+1行每行一個(gè)自然數(shù)?！据敵龈袷捷敵龈袷健?輸出文件count.out包含m行（m為n個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù)），按照自然數(shù)從小到大的順序輸出。每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空格隔開(kāi)。count.incount.incount.outcount.out8 82 24 42 24 45 51001002 21001002 32 34 24 25 15 1100 2100 2【輸入輸出樣例輸入輸出樣例】【限制限制】 40%的數(shù)據(jù)