快速排序與簡單排序性能比較

1、實驗四：快速排序與簡單排序性能比較學(xué)生姓名：班級：12學(xué)號：完成時間：2015.06.26本人鄭重聲明：本實驗的程序代碼編寫與調(diào)試、實驗報告的撰寫均由本人獨立完成，如被發(fā)現(xiàn)抄襲或與其他同學(xué)作業(yè)雷同，同意取消該實驗成績！聲明人：2015.06.26【實驗內(nèi)容】比較快速排序與簡單選擇排序算法的性能。學(xué)生須自行實現(xiàn)簡單選擇排序算法，并在不同輸入情況下，給出兩種排序算法的比較次數(shù)和移動次數(shù)?！揪幊趟悸贰渴紫龋骱瘮?shù)中要求輸入數(shù)組長度n，然后申請三個長度為n的動態(tài)數(shù)組，然后輸入數(shù)組元素，分別賦給三個數(shù)組。數(shù)組p用于快速排序輸出比較次數(shù)，數(shù)組pa用于快速排序輸出交換次數(shù)，數(shù)組pb用于簡單選擇排序輸出比較和

2、交換次數(shù)。在簡單排序過程中，用變量SwapTime記錄交換次數(shù),用變量CompareTime記錄比較次數(shù)，每次進行比較或交換,相應(yīng)變量自增。在快速排序過程中，由于用到遞歸算法，SwapTime和CompareTime均定義為靜態(tài)變量?！境绦虼a】1主函數(shù)(作業(yè)部分)voidmain()intn;cout“輸入數(shù)列的項數(shù)：n;int*p二newintn,pa二newintn,pb二newintn;cout輸入要排序的數(shù)列：endl;for(intj=O;jpj;paj=pj;pbj=pj;cout快速排序比較的次數(shù):quickSort2(p,0,n-l)endl;cout快速排序交換的次數(shù)：qu

3、ickSortl(pa,O,nT)endl;Easysort(pb,n);deletep;deletepa;deletepb;p二NULL;pa二NULL;pb二NULL;2快速排序函數(shù)(老師提供)intquickSort1(int*p,intlow,inthigh)/返回交換的次數(shù)inti,j,t;staticintSwapTime=0;/交換的次數(shù)if(lowhigh)/*要排序的元素起止下標，保證小的放在左邊，大的放在右邊。這里以下標為low的元素為基準點*/i=low;j=high;t=*(p+low);/*暫存基準點的數(shù)*/while(ij)/*循環(huán)掃描*/while(it)/*在右

4、邊的只要比基準點大仍放在右邊*/j-；/*前移一個位置*/if(ij)*(p+i)二*(p+j)；/*上面的循環(huán)退出：即出現(xiàn)比基準點小的數(shù),替換基準點的數(shù)*/i+；/*后移一個位置，并以此為基準點*/SwapTime+;while(ij&*(p+i)二t)/*在左邊的只要小于等于基準點仍放在左邊*/i+；if(ij)*(p+j)二*(p+i)；/*上面的循環(huán)退出：即出現(xiàn)比基準點大的數(shù),放到右邊*/j-；/*前移一個位置*/SwapTime+；*(p+i)=t；/*一遍掃描完后，放到適當位置*/quickSortl(p,low,i-l);/*對基準點左邊的數(shù)再執(zhí)行快速排序*/quickSortl

5、(p,i+l,high);/*對基準點右邊的數(shù)再執(zhí)行快速排序*/returnSwapTime;intquickSort2(int*p,intlow,inthigh)/返回比較的次數(shù)inti,j,t;staticintCompareTime=0;/比較的次數(shù)if(lowhigh)/*要排序的元素起止下標，保證小的放在左邊，大的放在右邊。這里以下標為low的元素為基準點*/i=low;j=high;t=*(p+low);/*暫存基準點的數(shù)*/for(intk=i;kj;k+)CompareTime+;while(ij)/*循環(huán)掃描*/while(it)/*在右邊的只要比基準點大仍放在右邊*/j-;

6、/*前移一個位置*/CompareTime+;if(ij)*(p+i)二*(p+j);/*上面的循環(huán)退出：即出現(xiàn)比基準點小的數(shù),替換基準點的數(shù)*/i+;/*后移一個位置，并以此為基準點*/while(ij&*(p+i)二t)/*在左邊的只要小于等于基準點仍放在左邊*/i+;/*后移一個位置*/CompareTime+;if(ij)*(p+j)二*(p+i);/*上面的循環(huán)退出：即出現(xiàn)比基準點大的數(shù),放到右邊*/j-;/*前移一個位置*/*(p+i)=t;/*一遍掃描完后，放到適當位置*/quickSort2(p,low,i-l);/*對基準點左邊的數(shù)再執(zhí)行快速排序*/quickSort2(p,i+l,high);/*對基準點右邊的數(shù)再執(zhí)行快速排序*/returnCompareTime;3簡單選擇排序函數(shù)(老師提供)voidEasysort(int*p,intn)intSwapTime=0;/交換的次數(shù)intCompareTime=0;intt二p0;for(inti二0;in1;i+)intk;k=i;for(intj=i+1;jn;CompareTime+;if(pjpk)k=j;if(i!=k)SwapTime+;t二pi;pi=pk;pk=t;printf(“簡單排序比較的次數(shù)：%dprintf(n);printf(簡單排序交換的次數(shù)：%dprintf(n);j+),Com