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

1、第二章第二章 數(shù)據(jù)排序數(shù)據(jù)排序 信息獲取后通常需要進(jìn)行處理，處理后的信息其目的是便于人們的應(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第三趟排序后

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) /對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)前無序區(qū)RI.N中選最小的元素RK I

3、f (RJ RK) K = J; If (K!=I) /交換RI和RK Temp = RI; RI = RK; RK = Temp; /SelectSort2.冒泡排序冒泡排序（1）基本的冒泡排序 基本思想依次比較相鄰的兩個數(shù)，把大的放前面，小的放后面。即首先比較第1個數(shù)和第2個數(shù)，大數(shù)放前,小數(shù)放后。然后比較第2個數(shù)和第3個數(shù).直到比較最后兩個數(shù)。第一趟結(jié)束，最小的一定沉到最后。重復(fù)上過程,仍從第1個數(shù)開始,到最后第2個數(shù)，然后.由于在排序過程中總是大數(shù)往前，小數(shù)往后，相當(dāng)氣泡上升，所以叫冒泡排序。下面是6個元素的排序的過程 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算法實現(xiàn)算法實現(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īng)排好序。上例中，可以發(fā)現(xiàn)，第二趟結(jié)束已經(jīng)排好序。但是計算機此時并不知道已經(jīng)排好序。所以，還需進(jìn)行一次比較，如果沒有發(fā)生任何數(shù)據(jù)交換，則知道已經(jīng)排好序，可以不干所以，還需進(jìn)行一次比較，如果沒有發(fā)生任何數(shù)據(jù)交換，則知道已經(jīng)排好序，可以不干了。因此第三趟比較還需進(jìn)行，第四趟、第五趟比較則不必要。了。因此第三趟比較還需進(jìn)行，第四趟、第五趟比較則不必要。 我們設(shè)置一個布爾變量我們設(shè)置一個布爾變量bo 來記錄是否有進(jìn)行交換。值為來記錄是否有進(jìn)行交換。值為false表示本趟中進(jìn)行了交換，表示本趟中進(jìn)行了交換，true 則沒有。代碼

6、如下則沒有。代碼如下: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)鍵字在一個明顯有限范圍內(nèi)(整型)時，可設(shè)計有限個有序桶，每個桶裝入一個值（當(dāng)然也可以裝入若干個值），順序輸出各桶的值，將得到有序的序列。例：輸入n個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. 插入排序插入排序 插入排序是一種簡單的排序方法，其算法的基本思想是： 假設(shè)待排序的數(shù)據(jù)存放在數(shù)組R1.n中，增加一個哨兵結(jié)點x。(1) R1自成1個有序區(qū)，無序區(qū)為R2.n;(2) 從i=2起直至i=n為止，將Ri放在恰當(dāng)?shù)奈恢茫筊1.i數(shù)據(jù)序列有序; x:=Ri; 將x與前i-1個數(shù)比較 , j:=i-1; while xaj do j:=j-1; 將R數(shù)

8、組的元素從j位置開始向后移動: for k:=i downto j do ak:=ak-1; Rj=x;(3) 生成包含n個數(shù)據(jù)的有序區(qū)。. 例如:設(shè)n=8，數(shù)組R中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步:12

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

10、法。就平均時間而言，快速排序是目前被認(rèn)為是最好的一種內(nèi)部排序方法 由以上討論可知，從時間上看，快速排序的平均性能優(yōu)于前面討論過的各種排序方法，但快速排序需一個?？臻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

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

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

13、 /s是第一個有序表起點位置，m+1是第二個有序表的起點 i=s; j=m+1; k=s; /i和j分別指向二個有序表的頭部 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)就是利用歸并操作把一個無序表排列成一個有序表的過程。二路歸并排序的過程是首先把待排序區(qū)間（即無序表）中的每一個元素都看作為一個有序表，則n個元素構(gòu)成n個有序表，接著兩兩

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

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

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

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

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

19、較 插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達(dá)到較快的速度。反而在這種情況下，快速排序反而慢了。 當(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)定性沒有要求時宜用堆排序 快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短；堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這

20、兩種排序都是不穩(wěn)定的?！旧蠙C練習(xí)上機練習(xí)】1、明明的隨機數(shù)（、明明的隨機數(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行，第1行為1個正整數(shù)，表示所生成的隨機數(shù)的個數(shù)：N第2行有N個用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)。【輸出文件輸出文件】輸

21、出文件random.out 也是2行，第1行為1個正整數(shù)M，表示不相同的隨機數(shù)的個數(shù)。第2行為M個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機數(shù)。【輸入樣例輸入樣例】1020 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度，則可以把相鄰兩節(jié)車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負(fù)責(zé)用這座橋?qū)?/p>

22、進(jìn)站的車廂按車廂號從小到大排列。他退休后，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序?！据斎胛募斎胛募?輸入文件有兩行數(shù)據(jù)，第一行是車廂總數(shù)N（不大于10000），第二行是N個不同的數(shù)表示初始的車廂順序。【輸出文件輸出文件】 一個數(shù)據(jù)，是最少的旋轉(zhuǎn)次數(shù)。【輸入樣例輸入樣例】carry .in44 3 2 1 【輸出樣例輸出樣例】carry .out63、眾數(shù)眾數(shù)(masses.pas)【問題描述問題描述】 由文件給出N個1到30000間無序數(shù)正整數(shù)，其中1N10000，同一個正整數(shù)可能會出現(xiàn)多次，出現(xiàn)次數(shù)最多的整數(shù)稱為眾數(shù)

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

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

25、樣，每個學(xué)生的排序是唯一確定的。 任務(wù)：先根據(jù)輸入的3門課的成績計算總分，然后按上述規(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【輸入格式輸入格式】輸入文件

26、scholar.in包含n+1行：第1行為一個正整數(shù)n，表示該校參加評選的學(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ù)都是正確的，不必檢驗?！据敵龈袷捷敵龈袷健枯敵鑫募cholar.out共有5行，每行是兩個用空格隔開的正整數(shù), 依次表示前5名學(xué)生的學(xué)號和總分?！据斎胼敵鰳永斎胼敵鰳永?】scholar.in690 67 8087 66 9178 89 9188 99 7767 89 6478 89 98 s

27、cholar.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ù)字、統(tǒng)計數(shù)字(Noip2007)【問題描述問題描述】 某次科研調(diào)查時得到了n個自然數(shù)，每個數(shù)均不超過1500000000（1.5*109）。已知不相同的數(shù)不超過10000個

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