上傳人：j***

認證信息

認證類型：個人認證

認證主體：張**（實名認證）

IP屬地：天津

IP屬地：天津 上傳時間：2021-08-01 格式：DOC 頁數(shù)：10 大小：112.50KB 積分：20 舉報 版權(quán)申訴

1、南京郵電大學通達學院實驗報告實驗名稱：快速排序算法課程名稱：微型計算機原理與接口技術姓名班級學號：錢煜中14250114250120實驗時間：快速排序原理一、實驗原理：快速排序算法 quick sort 主要是利用分治遞歸的思想進行排序的方法。它的原理是首先從待排序的原始序列ap,r中選取一個元素 aq 作為分界點( pivot )，然后將序列分為兩個子序列，左邊子序 列ap,q-1元素的值都小于分界點 m ,右邊子序列aq+1,r元 素值都大于分界點的值，此時得到的序列命名為a ，而aq應該處于其排好序后的正確位置。 然后利用遞歸的思想， 對左右兩個子序列 ap,q-1和aq+1,r再分別進

2、行排序，直到子序列的長度為 1 結(jié)束，序列有序。其中， 選取 a 中的基準分界點的方式有多種， 或者選擇序列的首 元素 ap ，或者選擇序列的尾元素 ar ，或者選擇序列中間位置的元 素 a(p+r)/2 ，或者取這三個元素按照大小排序后的中間值。例子：a = 38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72，取(left+right)/2 處的元素作為分界點( pivot )的值。具體第一次分 區(qū)過程如下：iohi “ ht69|E|22 | 48 113 | 38 | 93 14 卩叭內(nèi)沖In 衍- to Iohi| 69 | 5622* 48*

3、13*38-93*14 45 81 |1972*hilo ” * to| 69 5822 4813384514”93-81 |7972f牛因此，第一次分區(qū)，以69為分界點，結(jié)果為：a = 14, 58, 22, 48, 13, 38, 45, 69, 93, 81,79, 72二、實驗代碼#i nclude int fast_sort(int*a,int i,int j,int *p,int *b)int k,temp,f,g;g=*P；g=(12*g)-12;g=%dn,g);/in tf(成功進入快速排序 k=i;i+；for(;iak&ij;)j-;for(;aiak &i j;)i+;

4、/in tf(i=%dn,i);if(i=j)break;if(i*z)*z=*p;/prin tf(z=%dnp=%d,*z,*p);void main() int a=38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72;int b1012;int y=0,k,x=0,z=0;prin tf(初始序列為);for(k=0;k12;k+)prin tf(%3d,ak);prin tf(n);digui(a,0,11, &x,b, &z);for(y=1;yz+1;y+)printf(第%2d次后的數(shù)組為,y);prin tf(%3d,by-1k); p

5、rin tf(n);三、實驗數(shù)據(jù)（給出實驗結(jié)果）對序列 a = 38, 81,22, 48, 13, 69, 93, 14, 45, 58, 79, 7238 81 22 48 13 69 93 14 45 58 79 7238 14 22 48 13 69 9381 45 58 79 7238 14 2213 48 69 93 81 45 58 79 72址】吃后賞垃淤吋 第7次后的額為 卻3汰年m：匙圣勺 X q底石的刪為t_es h any kn to1491 45 碣 79時 60 58 ?991 網(wǎng) 58 795$ 72 8L 7969 7? 79 81進行快速排序，其中，以序列的首

6、元素作為排序的分界點。輸出結(jié)果 要求：輸出每一次分區(qū)后的結(jié)果以及最終排序結(jié)果。13 14 2213 14 2213 14 22 CDCitime,38 4833 45刖4o38 4530 45 忙地im吐理中DMktofi囲山童快1樟弓瑰墾中- X四、實驗總結(jié)（問題、解決方法、心得體會等） 這次實驗我做了很久， 重新編寫了算法很多次。 最開始我對算法的理 解不夠深，在遞歸自調(diào)用的時候沒有想通上下界其實在遞歸下一層的 時候下一層是知道上一層的上下界的， 只要排序算法里返還一個最好 作為比較值的位置就可以了。 一開始排序算法寫完就把每次數(shù)輸出出 來，知道后來和同學討論正確答案是排序了多少次， 才想想到我是把 每個區(qū)排完后的情況， 而其實我想輸出的是每次排序后數(shù)組情況。 可 是一開始進入的就是左半?yún)^(qū)的左半?yún)^(qū)的左半?yún)^(qū)。反正一次是無法 輸出全部的，因為右半?yún)^(qū)還沒有算。思考了很久，我決定建立一個二 維數(shù)組，第一行是第一次后的數(shù)組，第二行是第二次后的數(shù)組?？墒?如何確定現(xiàn)在是第幾次？我建立了一個指針， 每次進入遞歸一層就會 +