數(shù)據(jù)排序C++版素材

第二章數(shù)據(jù)排序1精選課件

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

〔2〕排序過程：【例如】：初始關鍵字[4938659776132749]

第一趟排序后13［38659776492749］

第二趟排序后1327［659776493849］

第三趟排序后132738[9776496549]

第四趟排序后13273849[76976549]

第五趟排序后1327384949[976576]

第六趟排序后132738494965[9776]

第七趟排序后13273849496576[97]

最后排序結果13273849496576973精選課件voidSelectSort(intR[]) //對R[1..N]進行直接選擇排序{for(inti=1;i<=n-1;i++)//做N-1趟選擇排序

{K=I;For(intj=i+1;j<=n;j++)//在當前無序區(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;}}}//SelectSort4精選課件2.冒泡排序〔1〕根本的冒泡排序①根本思想依次比較相鄰的兩個數(shù)，把大的放前面，小的放后面。即首先比較第1個數(shù)和第2個數(shù)，大數(shù)放前,小數(shù)放后。然后比較第2個數(shù)和第3個數(shù)......直到比較最后兩個數(shù)。第一趟結束，最小的一定沉到最后。重復上過程,仍從第1個數(shù)開始,到最后第2個數(shù)，然后......由于在排序過程中總是大數(shù)往前，小數(shù)往后，相當氣泡上升，所以叫冒泡排序。下面是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

┗━━┛

第一趟結束5精選課件

5

7

4

2

3

①

┗━━┛

7

5

4

2

3

1

┗━━┛

7

5

4

2

3

1

┗━━┛

7

5

4

2

3

1

┗━━┛

第二趟結束

7

5

4

3

②

1┗━━┛

7

5

4

3

2

1

┗━━┛

7

5

4

3

2

1

┗━━┛

第三趟結束

7

5

4

③

2

1

┗━━┛7

5

4

3

2

1

┗━━┛

第四趟結束

7

5

④

3

2

1

┗━━┛

第五趟結束

⑦

⑤

4

3

2

16精選課件②算法實現(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〕改進上例中，可以發(fā)現(xiàn)，第二趟結束已經(jīng)排好序。但是計算機此時并不知道已經(jīng)排好序。所以，還需進行一次比較，如果沒有發(fā)生任何數(shù)據(jù)交換，那么知道已經(jīng)排好序，可以不干了。因此第三趟比較還需進行，第四趟、第五趟比較那么不必要。我們設置一個布爾變量bo來記錄是否有進行交換。值為false表示本趟中進行了交換，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);7精選課件3.桶排序桶排序的思想是假設待排序的記錄的關鍵字在一個明顯有限范圍內(整型)時，可設計有限個有序桶，每個桶裝入一個值〔當然也可以裝入假設干個值〕，順序輸出各桶的值，將得到有序的序列。例：輸入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]++;//將關鍵字等于k的值全部裝入第k桶}for(i=0;i<=100;i++)while(b[i]>0){cout<<i<<"";b[i]--;}//輸出排序結果cout<<endl;}8精選課件4.插入排序插入排序是一種簡單的排序方法，其算法的根本思想是：假設待排序的數(shù)據(jù)存放在數(shù)組R[1..n]中，增加一個哨兵結點x。(1)R[1]自成1個有序區(qū)，無序區(qū)為R[2..n];

(2)從i=2起直至i=n為止，將R[i]放在恰當?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ū)。.例如:設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]9精選課件該算法的程序簡單，讀者自己完成。其算法的時間復雜性為O(n2)插入排序適用于原先數(shù)據(jù)已經(jīng)排列好，插入一個新數(shù)據(jù)的情況。voidinsertsort(intr[])//對r[1..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]//}}10精選課件5.快速排序快速排序是對冒泡排序的一種改進。它的根本思想是，通過一趟排序將待排記錄分割成獨立的兩局部，其中一局部記錄的關鍵字均比另一局部記錄的關鍵字小，那么可分別對這兩局部記錄繼續(xù)進行排序，以到達整個序列有序。假設待排序的序列為{a[L],a[L+1],a[L+2],……,a[R]}，首先任意選取一個記錄〔通?？蛇x中間一個記作為樞軸或支點〕，然后重新排列其余記錄，將所有關鍵字小于它的記錄都放在左子序列中，所有關鍵字大于它的記錄都放在右子序列中。由此可以將該“支點〞記錄所在的位置mid作分界線，將序列分割成兩個子序列和。這個過程稱作一趟快速排序〔或一次劃分〕。一趟快速排序的具體做法是：附設兩個指針i和j，它們的初值分別為L和R，設樞軸記錄取mid，那么首先從j所指位置起向前搜索找到第一個關鍵字小于的mid的記錄，然后從i所指位置起向后搜索，找到第一個關鍵字大于mid的記錄，將它們互相交換，重復這兩步直至i>j為止?？焖倥判虻臅r間的復雜性是O(nlog2n)，速度快,但它是不穩(wěn)定的排序方法。就平均時間而言，快速排序是目前被認為是最好的一種內部排序方法由以上討論可知，從時間上看，快速排序的平均性能優(yōu)于前面討論過的各種排序方法，但快速排序需一個?？臻g來實現(xiàn)遞歸。假設每一趟排序都將記錄序列均勻地分割成長度相接近的兩個子序列，那么棧的最大深度為log(n+1)。11精選課件快速排序算法voidqsort(intl,intr){ inti,j,mid,p;i=l;j=r;mid=a[(l+r)/2];//將當前序列在中間位置的數(shù)定義為分隔數(shù)do{ while(a[i]<mid)i++;//在左半局部尋找比中間數(shù)大的數(shù) while(a[j]>mid)j--;//在右半局部尋找比中間數(shù)小的數(shù) if(i<=j){//假設找到一組與排序目標不一致的數(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);}12精選課件6.歸并排序將兩個或兩個以上有序的數(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]復制到R[k]中，并令i和k分別加1，即使之分別指問后一單元，否那么將第二個有序表中的元素A[j]復制到R[k]中，并令j和k分別加1;如此循環(huán)下去，直到其中的一個有序表取完,然后再將另一個有序表中剩余的元素復制到R中從下標k到下標t的單元.13精選課件二路歸并算法描述為(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++;}//復制第一路剩余

while(j<=t){R[k]=A[j];j++;k++;}//復制第二路剩余}14精選課件歸并排序(Mergesort)就是利用歸并操作把一個無序表排列成一個有序表的過程。二路歸并排序的過程是首先把待排序區(qū)間〔即無序表〕中的每一個元素都看作為一個有序表，那么n個元素構成n個有序表，接著兩兩歸并〔即第一個表同第二個表歸并，第三個表同第四個表歸并，…〕，得到[n/2]個長度為2的有序表〔最后一個表的長度可能小于2〕，稱此為一趟歸并，然后再兩兩有序表歸并，得到[[n/2]/2]個長度為4的有序表〔最后一個表的長度可能小于4〕，如此進行下去，直到歸并第[log2n]趟后得到一個長度為n的有序表為止。歸并排序算法我們用遞歸實現(xiàn)，先把待排序區(qū)間[s,t]以中點二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。對左右子區(qū)間的排序與原問題一樣，所以我們可以調用同樣的子程序，只是區(qū)間大小不一樣。歸并排序程序如下：programex_2;#include<iostream>usingnamespacestd;inta[10001],r[10001],n,i; //a是待排序數(shù)組，r是臨時數(shù)組voidmergesort(ints,intt) //對[s,t]區(qū)間的無序數(shù)據(jù)進行歸并排序{intm,i,j,k;if(s==t)return; //假設區(qū)間只有一個數(shù)據(jù)就不用排了m=(s+t)/2; //取區(qū)間的中點mergesort(s,m); //以中點二分，對左邊了區(qū)間進行排序mergesort(m+1,t); //以中點二分，對右邊了區(qū)間進行排序i=s; //以下是一次歸并〔合并〕操作15精選課件j=m+1;k=s;while(i<=m&&j<=t)do//二個子序列從小大到合并，直到有一列結束

{ 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++;}

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

{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ù)進行歸并排序

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

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

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

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

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

桶排序、二路歸并排序的輔助空間為O(n)，快速排序的輔助空間為O(log2n)，最壞情況為O(n)，其它排序的輔助空間為O(1);4.其它比較插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能到達較快的速度。反而在這種情況下，快速排序反而慢了。當n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。假設待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許是用桶排序。當n較大時，關鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。當n較大時，關鍵字元素可能出現(xiàn)本身是有序的，對穩(wěn)定性沒有要求時宜用堆排序快速排序是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。18精選課件【上機練習】1、明明的隨機數(shù)〔Noip2006〕【問題描述】明明想在學校中請一些同學一起做一項問卷調查，為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數(shù)〔N≤100〕，對于其中重復的數(shù)字，只保存一個，把其余相同的數(shù)去掉，不同的數(shù)對應著不同的學生的學號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學做調查。請你協(xié)助明明完成“去重〞與“排序〞的工作?！据斎胛募枯斎胛募andom.in有2行，第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ù)。【輸入樣例】102040326740208930040015【輸出樣例】815203240678930040019精選課件2、車廂重組〔carry.pas〕【問題描述】在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉。一個車站的職工發(fā)現(xiàn)橋的長度最多能容納兩節(jié)車廂，如果將橋旋轉180度，那么可以把相鄰兩節(jié)車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負責用這座橋將進站的車廂按車廂號從小到大排列。他退休后，火車站決定將這一工作自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序?！据斎胛募枯斎胛募袃尚袛?shù)據(jù)，第一行是車廂總數(shù)N〔不大于10000〕，第二行是N個不同的數(shù)表示初始的車廂順序。【輸出文件】一個數(shù)據(jù)，是最少的旋轉次數(shù)?！据斎霕永縞arry.in44321【輸出樣例】carry.out620精選課件3、眾數(shù)(masses.pas)【問題描述】由文件給出N個1到30000間無序數(shù)正整數(shù)，其中1≤N≤10000，同一個正整數(shù)可能會出現(xiàn)屢次，出現(xiàn)次數(shù)最多的整數(shù)稱為眾數(shù)。求出它的眾數(shù)及它出現(xiàn)的次數(shù)?！据斎敫袷健枯斎胛募谝恍惺钦麛?shù)的個數(shù)N，第二行開始為N個正整數(shù)?！据敵龈袷健枯敵鑫募屑僭O干行，每行兩個數(shù)，第1個是眾數(shù)，第2個是眾數(shù)出現(xiàn)的次數(shù)?！据斎霕永縨asses.in12242325372343【輸出樣例】masses.out243421精選課件5、軍事機密(Secret.pas)【問題描述】軍方截獲的信息由n〔n<=30000〕個數(shù)字組成，因為是敵國的高端秘密，所以一時不能破獲。最原始的想法就是對這n個數(shù)進行小到大排序，每個數(shù)都對應一個序號，然后對第i個是什么數(shù)感興趣，現(xiàn)在要求編程完成?！据斎敫袷健康谝恍衝，接著是n個截獲的數(shù)字，接著一行是數(shù)字k，接著是k行要輸出數(shù)的序號?！据敵龈袷健縦行序號對應的數(shù)字。【輸入樣例】Secret.in5121112612373243【輸出樣例】Secret.out712312122精選課件6、獎學金(Noip2007)【問題描述】某小學最近得到了一筆贊助，打算拿出其中一局部為學習成績優(yōu)秀的前5名學生發(fā)獎學金。期末，每個學生都有3門課的成績：語文、數(shù)學、英語。先按總分從高到低排序，如果兩個同學總分相同，再按語文成績從高到低排序，如果兩個同學總分和語文成績都相同，那么規(guī)定學號小的同學排在前面，這樣，每個學生的排序是唯一確定的。任務：先根據(jù)輸入的3門課的成績計算總分，然后按上述規(guī)那么排序，最后按排名順序輸出前5名學生的學號和總分。注意，在前5名同學中，每個人的獎學金都不相同，因此，你必須嚴格按上述規(guī)那么排序。例如，在某個正確答案中，如果前兩行的輸出數(shù)據(jù)〔每行輸出兩個數(shù)：學號、總分〕是：72795279這兩行數(shù)據(jù)的含義是：總分最高的兩個同學的學號依次是7號、5號。這兩名同學的總分都是279〔總分等于輸入的語文、數(shù)學、英語三科成績之和〕，但學號為7的學生語文成績更高一些。如果你的前兩名的輸出數(shù)據(jù)是：52797279那么按輸出錯誤處理，不能得分。023精選課件【輸入格式】輸入文件scholar.in包含n+1行：第1行為一個正整數(shù)n，表示該校參加評選的學生人數(shù)。第2到n+1行，每行有3個用空格隔開的數(shù)字，每個數(shù)字都在0到100之間。第j行的3個數(shù)字依次表示學號為j-1的學生的語文、數(shù)學、英語的成績。每個學生的學號按照輸入順序編號為1~n〔恰好是輸入數(shù)據(jù)的行號減1〕。所給的數(shù)據(jù)都是正確的，不必檢驗?！据敵龈袷健枯敵鑫募cholar.out共有5行，每行是兩個用空格隔開的正整數(shù),依次表示前5名學生的學號和總分?！据斎胼敵鰳永?】scholar.in6906780876691788991889977678964788998

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

82652264626412585258【限制】50%的數(shù)據(jù)滿足：各學生的總成績各不相同100%的數(shù)據(jù)滿足：6<=n<=30024精選課件7、統(tǒng)計數(shù)字(Noip2007)【問題描述】某次科研調查時得到了n個自然數(shù)，每個數(shù)均不超過1500000000〔1.5*109〕。不相同的數(shù)不超過10000個，現(xiàn)在需要統(tǒng)計這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計結果?！据斎敫袷健枯斎胛募ount.in包含n+1行：第1行是整數(shù)n，表示自然數(shù)的個數(shù)。第2~n+1行每行一個自然數(shù)?！据敵龈袷健枯敵鑫募ount.out包含m行〔m為n個自然數(shù)中不相同數(shù)的個數(shù)〕，按照自然數(shù)從小到大的順序輸出。每行輸出兩個整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個空格隔開