PAGE淮陰工學院C++程序設計課程設計報告課程：排序系（院）: 計 算 機 與 軟 件 工 程 學院 專業: 計算機科學與技術 班級:計算機1152班 姓名:陸賽龍學號:1151308216指導教師:許超俊 學年學期: 2015 ~2016學年第2學期 2016 年7 月3 日

概述：排序是數據處理中經常使用的一種重要運算。設文件由n個記錄{R1，R2，……，Rn}組成，如n個學生記錄，每個學生記錄包括學號、姓名、班級等。n個記錄對應的關鍵字集合為{K1，K2，……，Kn}，如學生的學號。所謂排序就是將這n個記錄按關鍵字大小遞增或遞減重新排列。當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。如果文件中關鍵字相同的記錄經過某種排序方法進行排序之后，仍能保持它們在排序之前的相對次序，則稱這種排序方法是穩定的；否則，稱這種排序方法是不穩定的。幾乎所有的排序都有兩個基本的操作：（1）關鍵字大小的比較。（2）改變記錄的位置。排序方法：插入排序；選擇排序；冒泡排序；歸并排序；希爾排序；二元排序；交換排序。

目 錄TOC\o"1-4"\h\z\u1課題描述 11.1課題來源 11.2預期目標 12系統分析 22.1總體方案 23系統設計 43.1插入排序 43.2選擇排序 53.3交換排序 63.4冒泡排序 83.5希爾排序 93.6二元排序 103.7歸并排序 114程序主要模塊 134.1程序模塊圖 134.2程序代碼 134.3程序運行 224.3.1插入排序 224.3.2選擇排序 224.3.3冒泡排序 234.3.4歸并排序 234.3.5希爾排序 234.3.6希爾排序 244.3.7交換排序 24總結 24《C++程序設計課程設計報告》PAGE241，課題描述1.1課題來源排序是數據處理中經常使用的一種重要運算。由于文件大小不同使排序過程中涉及的儲存器不同，可將排序分成內部排序和外部排序兩類。整個排序過程都在內存進行的排序，稱為內部排序；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。內排序適用于記錄個數不是很多的小文件，而外排序則適用于記錄個數太多，不能一次性放入內存的大文件。排序算法很多，不同的算法有不同的優缺點，沒有哪種算法在任何情況下都是最好的。評價一種排序算法好壞的標準主要有兩條：（1）執行時間和所需的輔助空間，即時間復雜度和空間復雜度；（2）算法本身的復雜程度，比如算法是否易讀、是否易于實現。1.2預期目標本次實驗主要討論了插入排序，選擇排序，交換排序和歸并排序。通過編寫程序來實現對數據排序的一系列操作。運行程序后，顯示下面的參考界面：2，系統分析2.1總體方案（1）插入排序：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的記錄集中，使記錄依然有序，直到所有待排序記錄全部插入完成。可在數組中增加元素A[0]作為關鍵值存儲器和循環控制開關。第i趟排序，即A[i]的插入過程為：存A[i]→A[0]②j=i-1果A[j]<=A[0](即待排序的A[i])，則A[0]→A[j+1]，完成插入；否則，將A[j]后移一個位置：A[j]→A[j+1]；j=j-1；繼續執行③（2）選擇排序：每一趟從待排序的數據中選出最小元素，順序放在已排好序的數據最后，直到全部數據排序完畢。（3）交換排序：兩兩比較待排序的數據，發現兩個數據的次序相反則進行交換，直到沒有反序的數據為止。最多進行n-1趟排序，每趟排序時，從底部向上掃描，一旦發現兩個相鄰的元素不符合規則，則交換。第一趟排序后，最小值在A[1],第二趟排序后，較小值在A[2],第n-1趟排序完成后，所有元素完全按順序排列。（4）歸并排序：歸并排序是利用“歸并”技術來進行排序。歸并是指將若干個已排序的子文件合并成一個有序的文件。實現方法有兩種：自底向上和自底向下。自底向上的基本思想是：第1趟歸并排序時，將數列A[1..n]看作是n個長度為1的有序序列，將這些序列兩兩歸并，若n為偶數，則得到[n/2]個長度為2的有序序列；若n為奇數，則最后一個子序列不參與歸并。第2趟歸并則是將第一趟歸并所得到的有序序列兩兩歸并。如此反復，直到最后得到一個長度為n的有序文件為止。自頂向下的基本方法：分治法。其三個步驟：1.分解：將當前區間一分為二；2.求解：遞歸地對兩個子區間進行歸并排序；3.組合：將已排序的子區間歸并為一個有序區間（終結條件：子區間長度為1）（5）冒泡最多進行n-1趟排序，每趟排序時，從底部向上掃描，一旦發現兩個相鄰的元素不符合規則，則交換。我們發現，第一趟排序后，最小值在A[1]，第二趟排序后，較小值在A[2]，第n-1趟排序完成后，所有元素完全按順序排列。（6）希爾排序任取一個小于n的整數S1作為增量，把所有元素分成S1個組。所有間距為S1的元素放在同一個組中。第一組：{A[1]，A[S1+1]，A[2*S1+1]，……}第二組：{A[2]，A[S1+2]，A[2*S1+2]，……}……第s1組：{A[S1]，A[2*S1]，A[3*S1]，……}先在各組內進行直接插人排序；然后，取第二個增量S2（<S1）重復上述的分組和排序，直至所取的增量St=1（St<St-1<St-2<…<S2<S1），即所有記錄放在同一組中進行直接插入排序為止。3，系統設計3.1插入排序假設待排序數據存放在數組A[1..n]中，則A[1]可看作是一個有序序列，讓i從2開始，依次將A[i]插入到有序序列A[1..i-1]中，A[n]插入完畢則整個過程結束，A[1..n]成為有序序列。排序過程示例（用【】表示有序序列）待排序數據： 【25】548542119727315（n=10）i=2： 【2554】8542119727315i=3： 【82554】542119727315i=4： 【8255454】2119727315i=5： 【821255454】19727315i=6： 【1821255454】9727315i=7： 【182125545497】27315i=8： 【1282125545497】7315i=9： 【128212554547397】15i=10： 【12815212554547397】排序結束算法實現可在數組中增加元素A[0]作為關鍵值存儲器和循環控制開關。第i趟排序，即A[i]的插入過程為：①保存A[i]→A[0]②③如果A[j]<=A[0]（即待排序的A[i]），則A[0]→A[j+1]，完成插入；否則，將A[j]后移一個位置：A[j]→A[j+1]；；繼續執行③對于上面的數據實例，i從2依次變化到10的過程中，j值分別為{1，0，3，1，0，6，1，7，3}程序編寫：intcharu(intb[],intc)//將第一個看作有序數列，后面的數插入{ system("cls"); inti,x,j; cout<<"初始值:"; print1(b,c); for(i=1;i<c;i++) { x=b[i]; j=i-1; while(x<b[j]&&j>=0) { b[j+1]=b[j]; j--; } b[j+1]=x; } cout<<"排序后:"; print1(b,c); return1;}3.2選擇排序選擇排序的基本思想是：每一趟從待排序的數據中選出最小元素，順序放在已排好序的數據最后，直到全部數據排序完畢。過程模擬待排序數據92286284621656873366第一趟排序16286284629256873366第二趟排序16286284629256873366第三趟排序16283384629256876266第四趟排序16283356629284876266第五趟排序16283356629284876266第六趟排序16283356626284879266第七趟排序16283356626266879284第八趟排序16283356626266849287第九趟排序16283356626266848792程序編寫intxuanze(intb[],intc){ system("cls"); inti,j,t,p; cout<<"初始值:"; print1(b,c); for(i=0;i<=c-2;i++) { p=i; for(j=i+1;j<=c-1;j++) if(b[p]>b[j]) p=j; if(p!=i) { t=b[p]; b[p]=b[i]; b[i]=t; } } cout<<"排序后:"; print1(b,c); return1;}3.3交換排序交換排序的基本思想是：兩兩比較待排序的數據，發現兩個數據的次序相反則進行交換，直到沒有反序的數據為止。排序思想在A[1..n]中任取一個數據元素作為比較的“基準”（不妨記為X），將數據區劃分為左右兩個部分：A[1..i-1]和A[i+1..n]，且A[1..i-1]≤X≤A[i+1..n](1≤i≤n)，當A[1..i-1]和A[i+1..n]非空時，分別對它們進行上述的劃分過程，直至所有數據元素均已排序為止。算法實現可以使用遞歸函數實現這一算法。假定待排序序列的下標范圍為low~high。借用兩個整型變量i、j作為指針，約定初值分別為low、high。排序過程如下：①選定基準X（不妨用A[low]）②j向前掃描，直到A[j]<X，交換A[i]與A[j]，i+1。保證了A[low..i-1]≤X③i向后掃描，直到A[i]>X，交換A[i]與A[j]，j-1。保證了X≤A[j..high]④繼續執行②、③，直到i=j。這時，X恰好在A[i]位置上。⑤對序列A[low..i-1]及A[i+1..high]按照上述規律繼續劃分，直到序列為空。仔細分析算法，我們發現，在排序中，我們總是用基準X與另一數據交換，因此，一趟排序結束后，X就能確切定位其最終位置。排序過程示例待排序數據：6767145229990548771X=67ij掃描jij交換5467145229990678771掃描iij交換5467145229967908771j=i，結束ij第一趟排序后：54671452299[67]908771第二趟排序后：9291452[54]67[67]7187[90]第三趟排序后：[9]291452[54676771]87[90]第四趟排序后：[9]14[29]52[546767718790]第五趟排序后：[9142952546767718790]程序編寫voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}intpartition(inta[],intlow,inthigh){intprivotKey=a[low];//基準元素while(low<high){//從表的兩端交替地向中間掃描while(low<high&&a[high]>=privotKey) --high;//從high所指位置向前搜索，至多到low+1位置。將比基準元素小的交換到低端swap(&a[low],&a[high]);while(low<high&&a[low]<=privotKey) ++low;swap(&a[low],&a[high]);}returnlow;}voidqsort_improve(intr[],intlow,inthigh,intk){if(high-low>k)//長度大于k時遞歸,k為指定的數 {intpivot=partition(r,low,high);//調用的Partition算法保持不變qsort_improve(r,low,pivot-1,k);qsort_improve(r,pivot+1,high,k);}}voidquickSort(intr[],intn,intk){ system("cls"); cout<<"初始值：";print1(r,n+1);qsort_improve(r,0,n,k);//先調用改進算法Qsort使之基本有序for(inti=1;i<=n;i++)//再用插入排序對基本有序序列排序 {inttmp=r[i];intj=i-1;while(tmp<r[j]) {r[j+1]=r[j]; j=j-1;}r[j+1]=tmp;}cout<<"排序后:";print1(r,n+1);}3.4冒泡排序排序思想最多進行n-1趟排序，每趟排序時，從底部向上掃描，一旦發現兩個相鄰的元素不符合規則，則交換。我們發現，第一趟排序后，最小值在A[1]，第二趟排序后，較小值在A[2]，第n-1趟排序完成后，所有元素完全按順序排列。排序示例待排序數據：5333195336382201939第一趟排序：3533319531963822039第二趟排序：3195333195320638239第三趟排序：3191953332053396382第四趟排序：3191920533339536382第五趟排序：沒有反序數據，排序結束程序編寫intmaopao(intb[],intc){system("cls"); cout<<"初始值:"; print1(b,c); inti,j,t; for(i=0;i<c-1;i++) { for(j=c-2;j>=i;j--) { if(b[j+1]<b[j]) { t=b[j+1]; b[j+1]=b[j]; b[j]=t; } } } cout<<"排序后:"; print1(b,c); return1;}3.5希爾排序基本思想任取一個小于n的整數S1作為增量，把所有元素分成S1個組。所有間距為S1的元素放在同一個組中。第一組：{A[1]，A[S1+1]，A[2*S1+1]，……}第二組：{A[2]，A[S1+2]，A[2*S1+2]，……}第三組：{A[3]，A[S1+3]，A[2*S1+3]，……}……第s1組：{A[S1]，A[2*S1]，A[3*S1]，……}先在各組內進行直接插人排序；然后，取第二個增量S2（<S1）重復上述的分組和排序，直至所取的增量St=1（St<St-1<St-2<…<S2<S1），即所有記錄放在同一組中進行直接插入排序為止。排序示例序號12345678910原始數據1289573296375457957S1=5組別①②③④⑤①②③④⑤排序結果1254532573789577996S2=3組別①②③①②③①②③①排序結果1254532573789577996S3=2組別①②①②①②①②①②排序結果5321237575479578996S4=1組別①①①①①①①①①①排序結果5123237545757798996算法實現由于在分組內部使用的是直接插入排序，因此排序過程只要在直接插入排序的算法上對j的步長進行修改就可以了。編寫程序voidShellInsertSort(inta[],intn,intdk){for(inti=dk;i<n;++i) {if(a[i]<a[i-dk]) {//若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入intj=i-dk;intx=a[i];//復制為哨兵，即存儲待排序元素a[i]=a[i-dk];//首先后移一個元素while(x<a[j]) {//查找在有序表的插入位置a[j+dk]=a[j];j-=dk;//元素后移}a[j+dk]=x;//插入到正確位置}}}voidshellSort(inta[],intn){ system("cls"); cout<<"初始值:"; print1(a,n);intdk=n/2;while(dk>=1) {ShellInsertSort(a,n,dk);dk=dk/2;} cout<<"排序后:"; print1(a,n);}3.6二元排序程序編寫voidSelectSort(intr[],intn){ system("cls");inti,j,min,max,tmp; cout<<"初始值："; print1(r,n);for(i=1;i<=n/2;i++) {//做不超過n/2趟選擇排序min=i; max=i;//分別記錄最大和最小關鍵字記錄位置for(j=i+1;j<=n-i;j++) {if(r[j]>r[max]) {max=j; continue;}if(r[j]<r[min]) {min=j;}}3.7歸并排序歸并排序方法：自底向上和自頂向下。自底向上的方法自底向上的基本思想是：第1趟歸并排序時，將數列A[1..n]看作是n個長度為1的有序序列，將這些序列兩兩歸并，若n為偶數，則得到[n/2]個長度為2的有序序列；若n為奇數，則最后一個子序列不參與歸并。第2趟歸并則是將第1趟歸并所得到的有序序列兩兩歸并。如此反復，直到最后得到一個長度為n的有序文件為止。上述的每次歸并操作，均是將兩個有序序列合并成一個有序序列，故稱其為“二路歸并排序”。類似地有k(k>2)路歸并排序。自頂向下的方法采用分治法進行自頂向下的算法設計，形式更為簡潔。分治法的三個步驟：設歸并排序的當前區間是A[l..h]，分治法的三個步驟是：分解：將當前區間一分為二，即求分裂點m=(l+h)/2求解：遞歸地對兩個子區間A[l..m]和A[m+1..h]進行歸并排序；組合：將已排序的兩個子區間A[l..m]和A[m+1..h]歸并為一個有序的區間A[l..h]。遞歸的終結條件：子區間長度為1（一個數據組成的區間必然有序）。voidmerge1(int*a,intleft,intmid,intright){ int*t=newint[right-left+1];intm=left,n=mid+1,k=0;while((m<=mid)&&(n<=right)) { if(a[m]<a[n])t[k++]=a[m++];elset[k++]=a[n++]; }while(m<=mid)t[k++]=a[m++];while(n<=right)t[k++]=a[n++];for(m=0,k=left;k<=right;)a[k++]=t[m++];}voidsort(int*a,intleft,intright){ if(left<right) { intm=(left+right)/2;sort(a,left,m);sort(a,m+1,right);merge1(a,left,m,right); }}intguibin(intr[],intc){ system("cls"); cout<<"初始值:"; print1(r,c);//數組r1[]的大小一定要不小于r[]sort(r,0,c-1);cout<<"排序后：";print1(r,c); return1;}4，程序主要模塊4.1程序模塊圖Intmain主函數完成輸出的主界面以及輸入數據的方式Print1()完成輸出的功能intcharu完成插入排序的功能Intxuanze完成選擇排序的功能Intmaopao完成冒泡排序的功能voidmerge1voidsortintguibin三個程序共同完成歸并排序voidShellInsertSortvoidshellSort兩個程序共同完成希爾排序voidSelectSort完成二元排序voidswapintpartitionvoidqsort_improvevoidquickSort四個程序完成交換排序4.2程序代碼#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<time.h>#defineN10000voidprint1(intb[],intc){ for(inti=0;i<c;i++) cout<<b[i]<<""; cout<<endl;}//*********************************插入排序*************************************************intcharu(intb[],intc)//將第一個看作有序數列，后面的數插入{ system("cls"); inti,x,j; cout<<"初始值:"; print1(b,c); for(i=1;i<c;i++) { x=b[i]; j=i-1; while(x<b[j]&&j>=0) { b[j+1]=b[j]; j--; } b[j+1]=x; } cout<<"排序后:"; print1(b,c); return1;}//***選擇排序***intxuanze(intb[],intc){ system("cls"); inti,j,t,p; cout<<"初始值:"; print1(b,c); for(i=0;i<=c-2;i++) { p=i; for(j=i+1;j<=c-1;j++) if(b[p]>b[j]) p=j; if(p!=i) { t=b[p]; b[p]=b[i]; b[i]=t; } } cout<<"排序后:"; print1(b,c); return1;}//***冒泡***intmaopao(intb[],intc){system("cls"); cout<<"初始值:"; print1(b,c); inti,j,t; for(i=0;i<c-1;i++) { for(j=c-2;j>=i;j--) { if(b[j+1]<b[j]) { t=b[j+1]; b[j+1]=b[j]; b[j]=t; } } } cout<<"排序后:"; print1(b,c); return1;}//***歸并排序***voidmerge1(int*a,intleft,intmid,intright){ int*t=newint[right-left+1];intm=left,n=mid+1,k=0;while((m<=mid)&&(n<=right)) { if(a[m]<a[n])t[k++]=a[m++];elset[k++]=a[n++]; }while(m<=mid)t[k++]=a[m++];while(n<=right)t[k++]=a[n++];for(m=0,k=left;k<=right;)a[k++]=t[m++];}voidsort(int*a,intleft,intright){ if(left<right) { intm=(left+right)/2;sort(a,left,m);sort(a,m+1,right);merge1(a,left,m,right); }}intguibin(intr[],intc){ system("cls"); cout<<"初始值:"; print1(r,c);//數組r1[]的大小一定要不小于r[]sort(r,0,c-1);cout<<"排序后：";print1(r,c); return1;}//****希爾排序***voidShellInsertSort(inta[],intn,intdk){for(inti=dk;i<n;++i) {if(a[i]<a[i-dk]) {//若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入intj=i-dk;intx=a[i];//復制為哨兵，即存儲待排序元素a[i]=a[i-dk];//首先后移一個元素while(x<a[j]) {//查找在有序表的插入位置a[j+dk]=a[j];j-=dk;//元素后移}a[j+dk]=x;//插入到正確位置}}}voidshellSort(inta[],intn){ system("cls"); cout<<"初始值:"; print1(a,n);intdk=n/2;while(dk>=1) {ShellInsertSort(a,n,dk);dk=dk/2;} cout<<"排序后:"; print1(a,n);}//*************************二元排序*********************************voidSelectSort(intr[],intn){ system("cls");inti,j,min,max,tmp; cout<<"初始值："; print1(r,n);for(i=1;i<=n/2;i++) {//做不超過n/2趟選擇排序min=i; max=i;//分別記錄最大和最小關鍵字記錄位置for(j=i+1;j<=n-i;j++) {if(r[j]>r[max]) {max=j; continue;}if(r[j]<r[min]) {min=j;}}//該交換操作還可分情況討論以提高效率tmp=r[i-1]; r[i-1]=r[min]; r[min]=tmp;tmp=r[n-i]; r[n-i]=r[max]; r[max]=tmp;} cout<<"排序后:"; print1(r,n);}//***************************交換排序*******************************voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}intpartition(inta[],intlow,inthigh){intprivotKey=a[low];//基準元素while(low<high){//從表的兩端交替地向中間掃描while(low<high&&a[high]>=privotKey) --high;//從high所指位置向前搜索，至多到low+1位置。將比基準元素小的交換到低端swap(&a[low],&a[high]);while(low<high&&a[low]<=privotKey) ++low;swap(&a[low],&a[high]);}returnlow;}voidqsort_improve(intr[],intlow,inthigh,intk){if(high-low>k)//長度大于k時遞歸,k為指定的數 {intpivot=partition(r,low,high);//調用的Partition算法保持不變qsort_improve(r,low,pivot-1,k);qsort_improve(r,pivot+1,high,k);}}voidquickSort(intr[],intn,intk){ system("cls"); cout<<"初始值：";print1(r,n+1);qsort_improve(r,0,n,k);//先調用改進算法Qsort使之基本有序for(inti=1;i<=n;i++)//再用插入排序對基本有序序列排序 {inttmp=r[i];intj=i-1;while(tmp<r[j]) {r[j+1]=r[j]; j=j-1;}r[j+1]=tmp;}cout<<"排序后:";print1(r,n+1);}//*****主程序段*****intmain(){ inta[N]; ints,p; charj,c,t,i; while(1) { if(p)//切回主界面 {k:system("cls");cout<<setw(8)<<setfill('')<<"手工輸入請按1(個數<10)"<<endl; cout<<setw(8)<<setfill('')<<"隨機產生請按0(個數<10000)"<<endl; cout<<"請輸入:"; cin>>c; do { if(c=='0'||c=='1') break; else { cout<<"輸入格式錯誤，請重新輸入:"; cin>>c; } }while(1); if(c=='1') { system("cls"); cout<<"您選擇手工輸入！確認(1),返回(0):"; cin>>t; do { if(t=='0'||t=='1') break; else { cout<<"輸入格式錯誤，請重新輸入:"; cin>>t; } }while(1); if(t=='0') gotok; system("cls"); cout<<"請輸入手工輸入個數:"; cin>>s; cout<<"請輸入需排序的數據："; for(intk=0;k<s;k++) cin>>a[k]; } else { system("cls"); cout<<"您選擇隨機輸入！確認(1),返回(0):"; cin>>t; do { if(t=='0'||t=='1') break; else { cout<<"輸入格式錯誤，請重新輸入:"; cin>>t; } }while(1); if(t=='0') gotok; system("cls"); cout<<"請輸入隨機產生個數:"; cin>>s; srand((unsigned)time(NULL)); for(intk=0;k<s;k++) a[k]=rand()%900+100; }system("cls"); //******************************************* cout<<setw(27)<<setfill('')<<"數據排序"<<endl; cout<<setw(50)<<setfill('=')<<endl; cout<<setw(27)<<setfill('')<<"1.插入排序"<<endl; cout<<setw(27)<<setfill('')<<"2.選擇排序"<<endl; cout<<setw(27)<<setfill('')<<"3.冒泡排序"<<endl; cout<<