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

第二章數(shù)據(jù)排序

信息獲取后通常需要進(jìn)行處理，處理后的信息其目的是便于人們的應(yīng)用。信息處理方法有多種，通常有數(shù)據(jù)的排序，查找，插入，刪除，歸并等操作。讀者已經(jīng)接觸了一些這方面的知識，本章重點介紹數(shù)據(jù)排序的幾種方法。1.選擇排序（1）基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在待排序的數(shù)列的最前，直到全部待排序的數(shù)據(jù)元素排完。

（2）排序過程：【示例】：初始關(guān)鍵字[4938659776132749]

第一趟排序后13［38659776492749］

第二趟排序后1327［659776493849］

第三趟排序后132738[9776496549]

第四趟排序后13273849[76976549]

第五趟排序后1327384949[976576]

第六趟排序后132738494965[9776]

第七趟排序后13273849496576[97]

最后排序結(jié)果1327384949657697

voidSelectSort(intR[]) //對R[1..N]進(jìn)行直接選擇排序{for(inti=1;i<=n-1;i++)//做N-1趟選擇排序

{K=I;For(intj=i+1;j<=n;j++)//在當(dāng)前無序區(qū)R[I..N]中選最小的元素R[K]{If(R[J]<R[K])K=J;}If(K!=I)//交換R[I]和R[K]{Temp=R[I];R[I]=R[K];R[K]=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

3

┗━━┛

5

7

4

1

2

3

┗━━┛

5

7

4

2

1

3

┗━━┛

第一趟結(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é)束

7

5

4

3

②

1┗━━┛

7

5

4

3

2

1

┗━━┛

7

5

4

3

2

1

┗━━┛

第三趟結(jié)束

7

5

4

③

2

1

┗━━┛7

5

4

3

2

1

┗━━┛

第四趟結(jié)束

7

5

④

3

2

1

┗━━┛

第五趟結(jié)束

⑦

⑤

4

3

2

1②算法實現(xiàn)

for(inti=1;i<=n-1;i++)

for(intj=1;j<=n-i;j++)

if(a[j]<a[j+1]){

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;}（2）改進(jìn)上例中，可以發(fā)現(xiàn)，第二趟結(jié)束已經(jīng)排好序。但是計算機(jī)此時并不知道已經(jīng)排好序。所以，還需進(jìn)行一次比較，如果沒有發(fā)生任何數(shù)據(jù)交換，則知道已經(jīng)排好序，可以不干了。因此第三趟比較還需進(jìn)行，第四趟、第五趟比較則不必要。我們設(shè)置一個布爾變量bo來記錄是否有進(jìn)行交換。值為false表示本趟中進(jìn)行了交換，true則沒有。代碼如下:inti=1;do{bo=true;for(intj=1;j<=n-i;j++)if(a[j]<a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;bo=false; }

i++;}while(!bo);3.桶排序桶排序的思想是若待排序的記錄的關(guān)鍵字在一個明顯有限范圍內(nèi)(整型)時，可設(shè)計有限個有序桶，每個桶裝入一個值（當(dāng)然也可以裝入若干個值），順序輸出各桶的值，將得到有序的序列。例：輸入n個0到100之間的不相同整數(shù)，由小到大排序輸出。#include<iostream>#include<cstring>usingnamespacestd;intmain(){intb[101],k,i,n;memset(b,0,sizeof(b));//初始化

cin>>n;for(i=1;i<=n;i++){cin>>k;b[k]++;//將關(guān)鍵字等于k的值全部裝入第k桶

}for(i=0;i<=100;i++)while(b[i]>0){cout<<i<<"";b[i]--;}//輸出排序結(jié)果

cout<<endl;}4.插入排序插入排序是一種簡單的排序方法，其算法的基本思想是：假設(shè)待排序的數(shù)據(jù)存放在數(shù)組R[1..n]中，增加一個哨兵結(jié)點x。(1)R[1]自成1個有序區(qū)，無序區(qū)為R[2..n];

(2)從i=2起直至i=n為止，將R[i]放在恰當(dāng)?shù)奈恢?，使R[1..i]數(shù)據(jù)序列有序;①x:=R[i];②將x與前i-1個數(shù)比較,j:=i-1;whilex<a[j]doj:=j-1;③將R數(shù)組的元素從j位置開始向后移動:fork:=idowntojdoa[k]:=a[k-1];④R[j]=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]25481265432058

第1步:[2536]481265432058

第2步:[253648]1265432058

第3步:[12253648]65432058

第4步:[1225364865]432058

第5步:[122536434865]2058

第6步:[12202536434865]58

第7步:[1220253643485865]該算法的程序簡單，讀者自己完成。其算法的時間復(fù)雜性為O(n2)插入排序適用于原先數(shù)據(jù)已經(jīng)排列好，插入一個新數(shù)據(jù)的情況。voidinsertsort(intr[])//對r[1..n]按遞增序進(jìn)行插入排序，x是監(jiān)視哨{for(i=2;i<=n;i++)//依次插入r[2],...,r[n]{x=r[i];j=i-1;while(x<r[j])//查找r[i]的插入位置//{r[j+1]=r[j];//將大于r[i]的元素后移//j--;}r[j+1]=x;//插入r[I]//}}5.快速排序快速排序是對冒泡排序的一種改進(jìn)。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。假設(shè)待排序的序列為{a[L],a[L+1],a[L+2],……,a[R]}，首先任意選取一個記錄（通常可選中間一個記作為樞軸或支點），然后重新排列其余記錄，將所有關(guān)鍵字小于它的記錄都放在左子序列中，所有關(guān)鍵字大于它的記錄都放在右子序列中。由此可以將該“支點”記錄所在的位置mid作分界線，將序列分割成兩個子序列和。這個過程稱作一趟快速排序（或一次劃分）。一趟快速排序的具體做法是：附設(shè)兩個指針i和j，它們的初值分別為L和R，設(shè)樞軸記錄取mid，則首先從j所指位置起向前搜索找到第一個關(guān)鍵字小于的mid的記錄，然后從i所指位置起向后搜索，找到第一個關(guān)鍵字大于mid的記錄，將它們互相交換，重復(fù)這兩步直至i>j為止?？焖倥判虻臅r間的復(fù)雜性是O(nlog2n)，速度快,但它是不穩(wěn)定的排序方法。就平均時間而言，快速排序是目前被認(rèn)為是最好的一種內(nèi)部排序方法由以上討論可知，從時間上看，快速排序的平均性能優(yōu)于前面討論過的各種排序方法，但快速排序需一個?？臻g來實現(xiàn)遞歸。若每一趟排序都將記錄序列均勻地分割成長度相接近的兩個子序列，則棧的最大深度為log(n+1)?？焖倥判蛩惴╲oidqsort(intl,intr){ inti,j,mid,p;i=l;j=r;mid=a[(l+r)/2];//將當(dāng)前序列在中間位置的數(shù)定義為分隔數(shù)

do{ while(a[i]<mid)i++;//在左半部分尋找比中間數(shù)大的數(shù)

while(a[j]>mid)j--;//在右半部分尋找比中間數(shù)小的數(shù)

if(i<=j){//若找到一組與排序目標(biāo)不一致的數(shù)對則交換它們

p=a[i];a[i]=a[j];a[j]=p;i++;j--;//繼續(xù)找

}}while(i<=j);//注意這里不能有等號

if(l<j)qsort(l,j);//若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間

if(i<r)qsort(i,r);}6.歸并排序?qū)蓚€或兩個以上有序的數(shù)列(或有序表)，合并成一個仍然有序的數(shù)列(有序表)，這種操作稱為歸并操作。這樣的方法經(jīng)常用于多個有序的數(shù)據(jù)文件歸并成一個有序的數(shù)據(jù)文件。若將兩個有序表合并成一個有序表則稱為二路歸并，同理，有三路歸并、四路歸并等。二路歸并比較簡單，所以我們只討論二路歸并。例如有兩個有序表:(7，10，13，15)和(4，8，19，20)，歸并后得到的有序表為:(4，7，8，10，13，15，19，20)。歸并過程為:比較A[i]和A[j]的大小，若A[i]≤A[j]，則將第一個有序表中的元素A[i]復(fù)制到R[k]中，并令i和k分別加1，即使之分別指問后一單元，否則將第二個有序表中的元素A[j]復(fù)制到R[k]中，并令j和k分別加1;如此循環(huán)下去，直到其中的一個有序表取完,然后再將另一個有序表中剩余的元素復(fù)制到R中從下標(biāo)k到下標(biāo)t的單元.二路歸并算法描述為(A[s,t]中的數(shù)據(jù)由小到大合并到R[s,t]中):voidmerge(ints,intm,intt)//兩個有序表A[s,m]和A[m+1,t]合并成一個有序表R[s,t]{//s是第一個有序表起點位置，m+1是第二個有序表的起點

i=s; j=m+1; k=s;//i和j分別指向二個有序表的頭部

while(i<=m&&j<=t)if(A[i]<=A[j]){R[k]=A[i];i++;k++;}else{R[k]=A[j];j++;k++;}while(i<=m){R[k]=A[i];i++;k++;}//復(fù)制第一路剩余

while(j<=t){R[k]=A[j];j++;k++;}//復(fù)制第二路剩余}

歸并排序(Mergesort)就是利用歸并操作把一個無序表排列成一個有序表的過程。二路歸并排序的過程是首先把待排序區(qū)間（即無序表）中的每一個元素都看作為一個有序表，則n個元素構(gòu)成n個有序表，接著兩兩歸并（即第一個表同第二個表歸并，第三個表同第四個表歸并，…），得到[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ū)間大小不一樣。歸并排序程序如下：programex_2;#include<iostream>usingnamespacestd;inta[10001],r[10001],n,i; //a是待排序數(shù)組，r是臨時數(shù)組voidmergesort(ints,intt) //對[s,t]區(qū)間的無序數(shù)據(jù)進(jìn)行歸并排序{intm,i,j,k;if(s==t)return; //若區(qū)間只有一個數(shù)據(jù)就不用排了

m=(s+t)/2; //取區(qū)間的中點

mergesort(s,m); //以中點二分，對左邊了區(qū)間進(jìn)行排序

mergesort(m+1,t); //以中點二分，對右邊了區(qū)間進(jìn)行排序

i=s; //以下是一次歸并（合并）操作j=m+1;k=s;while(i<=m&&j<=t)do//二個子序列從小大到合并，直到有一列結(jié)束

{ if(a[i]<=a[j]){r[k]=a[i];i++;k++;}else{r[k]=a[j];j++;k++;} }while(i<=m) //*把左邊子序列剩余的元素接入進(jìn)來*

{r[k]=a[i];i++; k++;}

while(j<=t) //把右邊子序列剩余的元素接入進(jìn)來

{r[k]=a[j];j++;k++;}for(i=s;i<=t;i++) //把合并后的有序數(shù)據(jù)重新放回a數(shù)組

a[i]=r[i];}intmain(){ cin>>n;for(i=1;i<=n;i++) //讀入n個待排序數(shù)據(jù)

cin>>a[i];mergesort(1,n); //對[1,n]區(qū)間的無序數(shù)據(jù)進(jìn)行歸并排序

for(i=1;i<=n;i++) //輸出n個有序的數(shù)據(jù)

cout<<a[i]<<"";cout<<endl;}7.各種排序算法的比較1.穩(wěn)定性比較

插入排序、冒泡排序、二叉樹排序、二路歸并排序及其他線形排序是穩(wěn)定的。

選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的。2.時間復(fù)雜性比較

插入排序、冒泡排序、選擇排序的時間復(fù)雜性為O(n2)；快速排序、堆排序、歸并排序的時間復(fù)雜性為O(nlog2n)；桶排序的時間復(fù)雜性為O(n);

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

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

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

在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉(zhuǎn)。一個車站的職工發(fā)現(xiàn)橋的長度最多能容納兩節(jié)車廂，如果將橋旋轉(zhuǎn)180度，則可以把相鄰兩節(jié)車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負(fù)責(zé)用這座橋?qū)⑦M(jìn)站的車廂按車廂號從小到大排列。他退休后，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序?！据斎胛募?/p>

輸入文件有兩行數(shù)據(jù)，第一行是車廂總數(shù)N（不大于10000），第二行是N個不同的數(shù)表示初始的車廂順序。【輸出文件】

一個數(shù)據(jù)，是最少的旋轉(zhuǎn)次數(shù)。【輸入樣例】carry.in44321【輸出樣例】carry.out63、眾數(shù)(masses.pas)【問題描述】

由文件給出N個1到30000間無序數(shù)正整數(shù)，其中1≤N≤10000，同一個正整數(shù)可能會出現(xiàn)多次，出現(xiàn)次數(shù)最多的整數(shù)稱為眾數(shù)。求出它的眾數(shù)及它出現(xiàn)的次數(shù)?！据斎敫袷健?/p>

輸入文件第一行是正整數(shù)的個數(shù)N，第二行開始為N個正整數(shù)?！据敵龈袷健?/p>

輸出文件有若干行，每行兩個數(shù)，第1個是眾數(shù)，第2個是眾數(shù)出現(xiàn)的次數(shù)。【輸入樣例】masses.in12242325372343【輸出樣例】masses.out24345、軍事機(jī)密(Secret.pas)【問題描述】

軍方截獲的信息由n（n<=30000）個數(shù)字組成，因為是敵國的高端秘密，所以一時不能破獲。最原始的想法就是對這n個數(shù)進(jìn)行小到大排序，每個數(shù)都對應(yīng)一個序號，然后對第i個是什么數(shù)感興趣，現(xiàn)在要求編程完成?！据斎敫袷健?/p>

第一行n，接著是n個截獲的數(shù)字，接著一行是數(shù)字k，接著是k行要輸出數(shù)的序號?！据敵龈袷健縦行序號對應(yīng)的數(shù)字?！据斎霕永縎ecret.in5121112612373243【輸出樣例】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門課的成績計算總分，然后按上述規(guī)則排序，最后按排名順序輸出前5名學(xué)生的學(xué)號和總分。注意，在前5名同學(xué)中，每個人的獎學(xué)金都不相同，因此，你必須嚴(yán)格按上述規(guī)則排序。例如，在某個正確答案中，如果前兩行的輸出數(shù)據(jù)（每行輸出兩個數(shù)：學(xué)號、總分）是：

72795279

這兩行數(shù)據(jù)的含義是：總分最高的兩個同學(xué)的學(xué)號依次是7號、5號。這兩名同學(xué)的總分都是279（總分等于輸入的語文、數(shù)學(xué)、英語三科成績之和），但學(xué)號為7的學(xué)生語文成績更高一些。如果你的前兩名的輸出數(shù)據(jù)是：

52797279

則按輸出錯誤處理，不能得分。0【輸入格式】輸入文件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é)號按照輸入順序編號為1~n（恰好是輸入數(shù)據(jù)的行號減1）。所給的數(shù)據(jù)都是正確的，不必檢驗?！据敵龈袷健枯敵鑫募cholar.out共有5行，每行是兩個用空格隔開的正整數(shù),依次表示前5名學(xué)生的學(xué)號和總分。【輸入輸出樣例1】scholar.in6906780876691788991889977678964788998

scholar.out62654264325822441237【輸入輸出樣例2】scholar.in8808989889878906780876691788991889977678964788998scholar.out

82652264626412585258【限制】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ù)從小到大的順序輸出統(tǒng)計結(jié)果?！据斎敫袷健?/p>

輸入文件count.in