快速排序與簡(jiǎn)單排序性能比較

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

2、交換次數(shù)。在簡(jiǎn)單排序過程中，用變量SwapTime記錄交換次數(shù),用變量CompareTime記錄比較次數(shù)，每次進(jìn)行比較或交換,相應(yīng)變量自增。在快速排序過程中，由于用到遞歸算法，SwapTime和CompareTime均定義為靜態(tài)變量?！境绦虼a】1主函數(shù)(作業(yè)部分)voidmain()intn;cout“輸入數(shù)列的項(xiàng)數(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)/*要排序的元素起止下標(biāo)，保證小的放在左邊，大的放在右邊。這里以下標(biāo)為low的元素為基準(zhǔn)點(diǎn)*/i=low;j=high;t=*(p+low);/*暫存基準(zhǔn)點(diǎn)的數(shù)*/while(ij)/*循環(huán)掃描*/while(it)/*在右

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

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

6、/*前移一個(gè)位置*/CompareTime+;if(ij)*(p+i)二*(p+j);/*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)小的數(shù),替換基準(zhǔn)點(diǎn)的數(shù)*/i+;/*后移一個(gè)位置，并以此為基準(zhǔn)點(diǎn)*/while(ij&*(p+i)二t)/*在左邊的只要小于等于基準(zhǔn)點(diǎn)仍放在左邊*/i+;/*后移一個(gè)位置*/CompareTime+;if(ij)*(p+j)二*(p+i);/*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)大的數(shù),放到右邊*/j-;/*前移一個(gè)位置*/*(p+i)=t;/*一遍掃描完后，放到適當(dāng)位置*/quickSort2(p,low,i-l);/*對(duì)基準(zhǔn)點(diǎn)左邊的數(shù)再執(zhí)行快速排序*/quickSort2(p,i+l,high);/*對(duì)基準(zhǔn)點(diǎn)右邊的數(shù)再執(zhí)行快速排序*/returnCompareTime;3簡(jiǎn)單選擇排序函數(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(“簡(jiǎn)單排序比較的次數(shù)：%dprintf(n);printf(簡(jiǎn)單排序交換的次數(shù)：%dprintf(n);j+),Com