C-程序設(shè)計(jì)課程設(shè)計(jì)報(bào)告

PAGE淮陰工學(xué)院C++程序設(shè)計(jì)課程設(shè)計(jì)報(bào)告課程：排序系（院）: 計(jì) 算 機(jī) 與 軟 件 工 程 學(xué)院 專業(yè): 計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí):計(jì)算機(jī)1152班 姓名:陸賽龍學(xué)號(hào):1151308216指導(dǎo)教師:許超俊 學(xué)年學(xué)期: 2015 ~2016學(xué)年第2學(xué)期 2016 年7 月3 日

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

目 錄TOC\o"1-4"\h\z\u1課題描述 11.1課題來源 11.2預(yù)期目標(biāo) 12系統(tǒng)分析 22.1總體方案 23系統(tǒng)設(shè)計(jì) 43.1插入排序 43.2選擇排序 53.3交換排序 63.4冒泡排序 83.5希爾排序 93.6二元排序 103.7歸并排序 114程序主要模塊 134.1程序模塊圖 134.2程序代碼 134.3程序運(yùn)行 224.3.1插入排序 224.3.2選擇排序 224.3.3冒泡排序 234.3.4歸并排序 234.3.5希爾排序 234.3.6希爾排序 244.3.7交換排序 24總結(jié) 24《C++程序設(shè)計(jì)課程設(shè)計(jì)報(bào)告》PAGE241，課題描述1.1課題來源排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。由于文件大小不同使排序過程中涉及的儲(chǔ)存器不同，可將排序分成內(nèi)部排序和外部排序兩類。整個(gè)排序過程都在內(nèi)存進(jìn)行的排序，稱為內(nèi)部排序；反之，若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。內(nèi)排序適用于記錄個(gè)數(shù)不是很多的小文件，而外排序則適用于記錄個(gè)數(shù)太多，不能一次性放入內(nèi)存的大文件。排序算法很多，不同的算法有不同的優(yōu)缺點(diǎn)，沒有哪種算法在任何情況下都是最好的。評(píng)價(jià)一種排序算法好壞的標(biāo)準(zhǔn)主要有兩條：（1）執(zhí)行時(shí)間和所需的輔助空間，即時(shí)間復(fù)雜度和空間復(fù)雜度；（2）算法本身的復(fù)雜程度，比如算法是否易讀、是否易于實(shí)現(xiàn)。1.2預(yù)期目標(biāo)本次實(shí)驗(yàn)主要討論了插入排序，選擇排序，交換排序和歸并排序。通過編寫程序來實(shí)現(xiàn)對(duì)數(shù)據(jù)排序的一系列操作。運(yùn)行程序后，顯示下面的參考界面：2，系統(tǒng)分析2.1總體方案（1）插入排序：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的記錄集中，使記錄依然有序，直到所有待排序記錄全部插入完成?？稍跀?shù)組中增加元素A[0]作為關(guān)鍵值存儲(chǔ)器和循環(huán)控制開關(guān)。第i趟排序，即A[i]的插入過程為：存A[i]→A[0]②j=i-1果A[j]<=A[0](即待排序的A[i])，則A[0]→A[j+1]，完成插入；否則，將A[j]后移一個(gè)位置：A[j]→A[j+1]；j=j-1；繼續(xù)執(zhí)行③（2）選擇排序：每一趟從待排序的數(shù)據(jù)中選出最小元素，順序放在已排好序的數(shù)據(jù)最后，直到全部數(shù)據(jù)排序完畢。（3）交換排序：兩兩比較待排序的數(shù)據(jù)，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)的次序相反則進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)為止。最多進(jìn)行n-1趟排序，每趟排序時(shí)，從底部向上掃描，一旦發(fā)現(xiàn)兩個(gè)相鄰的元素不符合規(guī)則，則交換。第一趟排序后，最小值在A[1],第二趟排序后，較小值在A[2],第n-1趟排序完成后，所有元素完全按順序排列。（4）歸并排序：歸并排序是利用“歸并”技術(shù)來進(jìn)行排序。歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件。實(shí)現(xiàn)方法有兩種：自底向上和自底向下。自底向上的基本思想是：第1趟歸并排序時(shí)，將數(shù)列A[1..n]看作是n個(gè)長(zhǎng)度為1的有序序列，將這些序列兩兩歸并，若n為偶數(shù)，則得到[n/2]個(gè)長(zhǎng)度為2的有序序列；若n為奇數(shù)，則最后一個(gè)子序列不參與歸并。第2趟歸并則是將第一趟歸并所得到的有序序列兩兩歸并。如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序文件為止。自頂向下的基本方法：分治法。其三個(gè)步驟：1.分解：將當(dāng)前區(qū)間一分為二；2.求解：遞歸地對(duì)兩個(gè)子區(qū)間進(jìn)行歸并排序；3.組合：將已排序的子區(qū)間歸并為一個(gè)有序區(qū)間（終結(jié)條件：子區(qū)間長(zhǎng)度為1）（5）冒泡最多進(jìn)行n-1趟排序，每趟排序時(shí)，從底部向上掃描，一旦發(fā)現(xiàn)兩個(gè)相鄰的元素不符合規(guī)則，則交換。我們發(fā)現(xiàn)，第一趟排序后，最小值在A[1]，第二趟排序后，較小值在A[2]，第n-1趟排序完成后，所有元素完全按順序排列。（6）希爾排序任取一個(gè)小于n的整數(shù)S1作為增量，把所有元素分成S1個(gè)組。所有間距為S1的元素放在同一個(gè)組中。第一組：{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]，……}先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量S2（<S1）重復(fù)上述的分組和排序，直至所取的增量St=1（St<St-1<St-2<…<S2<S1），即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?，系統(tǒng)設(shè)計(jì)3.1插入排序假設(shè)待排序數(shù)據(jù)存放在數(shù)組A[1..n]中，則A[1]可看作是一個(gè)有序序列，讓i從2開始，依次將A[i]插入到有序序列A[1..i-1]中，A[n]插入完畢則整個(gè)過程結(jié)束，A[1..n]成為有序序列。排序過程示例（用【】表示有序序列）待排序數(shù)據(jù)： 【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】排序結(jié)束算法實(shí)現(xiàn)可在數(shù)組中增加元素A[0]作為關(guān)鍵值存儲(chǔ)器和循環(huán)控制開關(guān)。第i趟排序，即A[i]的插入過程為：①保存A[i]→A[0]②③如果A[j]<=A[0]（即待排序的A[i]），則A[0]→A[j+1]，完成插入；否則，將A[j]后移一個(gè)位置：A[j]→A[j+1]；；繼續(xù)執(zhí)行③對(duì)于上面的數(shù)據(jù)實(shí)例，i從2依次變化到10的過程中，j值分別為{1，0，3，1，0，6，1，7，3}程序編寫：intcharu(intb[],intc)//將第一個(gè)看作有序數(shù)列，后面的數(shù)插入{ 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選擇排序選擇排序的基本思想是：每一趟從待排序的數(shù)據(jù)中選出最小元素，順序放在已排好序的數(shù)據(jù)最后，直到全部數(shù)據(jù)排序完畢。過程模擬待排序數(shù)據(jù)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交換排序交換排序的基本思想是：兩兩比較待排序的數(shù)據(jù)，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)的次序相反則進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)為止。排序思想在A[1..n]中任取一個(gè)數(shù)據(jù)元素作為比較的“基準(zhǔn)”（不妨記為X），將數(shù)據(jù)區(qū)劃分為左右兩個(gè)部分：A[1..i-1]和A[i+1..n]，且A[1..i-1]≤X≤A[i+1..n](1≤i≤n)，當(dāng)A[1..i-1]和A[i+1..n]非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過程，直至所有數(shù)據(jù)元素均已排序?yàn)橹?。算法?shí)現(xiàn)可以使用遞歸函數(shù)實(shí)現(xiàn)這一算法。假定待排序序列的下標(biāo)范圍為low~high。借用兩個(gè)整型變量i、j作為指針，約定初值分別為low、high。排序過程如下：①選定基準(zhǔn)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]④繼續(xù)執(zhí)行②、③，直到i=j。這時(shí)，X恰好在A[i]位置上。⑤對(duì)序列A[low..i-1]及A[i+1..high]按照上述規(guī)律繼續(xù)劃分，直到序列為空。仔細(xì)分析算法，我們發(fā)現(xiàn)，在排序中，我們總是用基準(zhǔn)X與另一數(shù)據(jù)交換，因此，一趟排序結(jié)束后，X就能確切定位其最終位置。排序過程示例待排序數(shù)據(jù)：6767145229990548771X=67ij掃描jij交換5467145229990678771掃描iij交換5467145229967908771j=i，結(jié)束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];//基準(zhǔn)元素while(low<high){//從表的兩端交替地向中間掃描while(low<high&&a[high]>=privotKey) --high;//從high所指位置向前搜索，至多到low+1位置。將比基準(zhǔn)元素小的交換到低端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)//長(zhǎng)度大于k時(shí)遞歸,k為指定的數(shù) {intpivot=partition(r,low,high);//調(diào)用的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);//先調(diào)用改進(jìn)算法Qsort使之基本有序for(inti=1;i<=n;i++)//再用插入排序?qū)居行蛐蛄信判?{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冒泡排序排序思想最多進(jìn)行n-1趟排序，每趟排序時(shí)，從底部向上掃描，一旦發(fā)現(xiàn)兩個(gè)相鄰的元素不符合規(guī)則，則交換。我們發(fā)現(xiàn)，第一趟排序后，最小值在A[1]，第二趟排序后，較小值在A[2]，第n-1趟排序完成后，所有元素完全按順序排列。排序示例待排序數(shù)據(jù)：5333195336382201939第一趟排序：3533319531963822039第二趟排序：3195333195320638239第三趟排序：3191953332053396382第四趟排序：3191920533339536382第五趟排序：沒有反序數(shù)據(jù)，排序結(jié)束程序編寫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希爾排序基本思想任取一個(gè)小于n的整數(shù)S1作為增量，把所有元素分成S1個(gè)組。所有間距為S1的元素放在同一個(gè)組中。第一組：{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]，……}先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量S2（<S1）重復(fù)上述的分組和排序，直至所取的增量St=1（St<St-1<St-2<…<S2<S1），即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。排序示例序?hào)12345678910原始數(shù)據(jù)1289573296375457957S1=5組別①②③④⑤①②③④⑤排序結(jié)果1254532573789577996S2=3組別①②③①②③①②③①排序結(jié)果1254532573789577996S3=2組別①②①②①②①②①②排序結(jié)果5321237575479578996S4=1組別①①①①①①①①①①排序結(jié)果5123237545757798996算法實(shí)現(xiàn)由于在分組內(nèi)部使用的是直接插入排序，因此排序過程只要在直接插入排序的算法上對(duì)j的步長(zhǎng)進(jìn)行修改就可以了。編寫程序voidShellInsertSort(inta[],intn,intdk){for(inti=dk;i<n;++i) {if(a[i]<a[i-dk]) {//若第i個(gè)元素大于i-1元素，直接插入。小于的話，移動(dòng)有序表后插入intj=i-dk;intx=a[i];//復(fù)制為哨兵，即存儲(chǔ)待排序元素a[i]=a[i-dk];//首先后移一個(gè)元素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;//分別記錄最大和最小關(guān)鍵字記錄位置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趟歸并排序時(shí)，將數(shù)列A[1..n]看作是n個(gè)長(zhǎng)度為1的有序序列，將這些序列兩兩歸并，若n為偶數(shù)，則得到[n/2]個(gè)長(zhǎng)度為2的有序序列；若n為奇數(shù)，則最后一個(gè)子序列不參與歸并。第2趟歸并則是將第1趟歸并所得到的有序序列兩兩歸并。如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序文件為止。上述的每次歸并操作，均是將兩個(gè)有序序列合并成一個(gè)有序序列，故稱其為“二路歸并排序”。類似地有k(k>2)路歸并排序。自頂向下的方法采用分治法進(jìn)行自頂向下的算法設(shè)計(jì)，形式更為簡(jiǎn)潔。分治法的三個(gè)步驟：設(shè)歸并排序的當(dāng)前區(qū)間是A[l..h]，分治法的三個(gè)步驟是：分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn)m=(l+h)/2求解：遞歸地對(duì)兩個(gè)子區(qū)間A[l..m]和A[m+1..h]進(jìn)行歸并排序；組合：將已排序的兩個(gè)子區(qū)間A[l..m]和A[m+1..h]歸并為一個(gè)有序的區(qū)間A[l..h]。遞歸的終結(jié)條件：子區(qū)間長(zhǎng)度為1（一個(gè)數(shù)據(jù)組成的區(qū)間必然有序）。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);//數(shù)組r1[]的大小一定要不小于r[]sort(r,0,c-1);cout<<"排序后：";print1(r,c); return1;}4，程序主要模塊4.1程序模塊圖Intmain主函數(shù)完成輸出的主界面以及輸入數(shù)據(jù)的方式Print1()完成輸出的功能intcharu完成插入排序的功能Intxuanze完成選擇排序的功能Intmaopao完成冒泡排序的功能voidmerge1voidsortintguibin三個(gè)程序共同完成歸并排序voidShellInsertSortvoidshellSort兩個(gè)程序共同完成希爾排序voidSelectSort完成二元排序voidswapintpartitionvoidqsort_improvevoidquickSort四個(gè)程序完成交換排序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)//將第一個(gè)看作有序數(shù)列，后面的數(shù)插入{ 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);//數(shù)組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個(gè)元素大于i-1元素，直接插入。小于的話，移動(dòng)有序表后插入intj=i-dk;intx=a[i];//復(fù)制為哨兵，即存儲(chǔ)待排序元素a[i]=a[i-dk];//首先后移一個(gè)元素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;//分別記錄最大和最小關(guān)鍵字記錄位置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];//基準(zhǔn)元素while(low<high){//從表的兩端交替地向中間掃描while(low<high&&a[high]>=privotKey) --high;//從high所指位置向前搜索，至多到low+1位置。將比基準(zhǔn)元素小的交換到低端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)//長(zhǎng)度大于k時(shí)遞歸,k為指定的數(shù) {intpivot=partition(r,low,high);//調(diào)用的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);//先調(diào)用改進(jìn)算法Qsort使之基本有序for(inti=1;i<=n;i++)//再用插入排序?qū)居行蛐蛄信判?{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('')<<"手工輸入請(qǐng)按1(個(gè)數(shù)<10)"<<endl; cout<<setw(8)<<setfill('')<<"隨機(jī)產(chǎn)生請(qǐng)按0(個(gè)數(shù)<10000)"<<endl; cout<<"請(qǐng)輸入:"; cin>>c; do { if(c=='0'||c=='1') break; else { cout<<"輸入格式錯(cuò)誤，請(qǐng)重新輸入:"; cin>>c; } }while(1); if(c=='1') { system("cls"); cout<<"您選擇手工輸入！確認(rèn)(1),返回(0):"; cin>>t; do { if(t=='0'||t=='1') break; else { cout<<"輸入格式錯(cuò)誤，請(qǐng)重新輸入:"; cin>>t; } }while(1); if(t=='0') gotok; system("cls"); cout<<"請(qǐng)輸入手工輸入個(gè)數(shù):"; cin>>s; cout<<"請(qǐng)輸入需排序的數(shù)據(jù)："; for(intk=0;k<s;k++) cin>>a[k]; } else { system("cls"); cout<<"您選擇隨機(jī)輸入！確認(rèn)(1),返回(0):"; cin>>t; do { if(t=='0'||t=='1') break; else { cout<<"輸入格式錯(cuò)誤，請(qǐng)重新輸入:"; cin>>t; } }while(1); if(t=='0') gotok; system("cls"); cout<<"請(qǐng)輸入隨機(jī)產(chǎn)生個(gè)數(shù):"; cin>>s; srand((unsigned)time(NULL)); for(intk=0;k<s;k++) a[k]=rand()%900+100; }system("cls"); //******************************************* cout<<setw(27)<<setfill('')<<"數(shù)據(jù)排序"<<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<<