快速排序?qū)嶒?yàn)報(bào)告

《快速排序?qū)嶒?yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、南京郵電大學(xué)通達(dá)學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱課程名稱快速排序算法微型計(jì)算槪屋理與接口技術(shù)姓名班級(jí)學(xué)號(hào)：錢煜中14250114250120實(shí)驗(yàn)時(shí)間：2016.12.2快速排序原理一、實(shí)驗(yàn)原理：快速排序算法quicksort主要是利用分治遞歸的思想進(jìn)行排序的方法。它的原理是首先從待排序的原始序列a[p，…，r]中選取一個(gè)元素a[q]作為分界點(diǎn)(pivot),然后將序列分為兩個(gè)子序列，左邊子序列a[p，…，q_l]元素的值都小于分界點(diǎn)m,右邊子序列a[q+l,…，r]元素值都大于分界點(diǎn)的值，此時(shí)得到的序列命名為a’，而a[q]

2、應(yīng)該處于其排好序后的正確位置。然后利用遞歸的思想，對(duì)左右兩個(gè)子序列a[p，…，q-1]和a[q+l，…，r]再分別進(jìn)行排序，直到子序列的長(zhǎng)度為1結(jié)束，序列右序。其中，選取a中的基準(zhǔn)分界點(diǎn)的方式有多種，或者選擇序列的首元素a[p]，或者選擇序列的尾元素a[r]，或者選擇序列中間位置的元素a[(p+r)/2]，或者取這三個(gè)元素按照大小排序后的中間值。例子：a=[38，81，22,48，13,69，93,14,45，58，79，72]，取[(left+right)/2]處的元素作為分界點(diǎn)(pivot)的值。具體第一次分

3、區(qū)過(guò)程如下：left獻(xiàn)十1

4、1right

5、38

6、81221369

7、冋問(wèn)問(wèn)587972ttIohi-hi礞一M

8、69

9、81*

10、22

11、48

12、13l38M卜

13、45!(58J79*[72*]傘Io-?Io一.Io^lohi[69]5822*[48*13*38.93*14

14、45*817972今hilo?lo

15、69]5822

16、48

17、13

18、38

19、45

20、j14“l(fā)

21、93*

22、8179

23、

24、72

25、T今hi

26、1458224813384569

27、l93l817972因此，第一次分區(qū)，以69為分界點(diǎn)，結(jié)果為：a,=[14，58，22，48，1

28、3，38，45，69,93，81，79,72]。二、實(shí)驗(yàn)代碼#includeintfastsort(int^a,inti,intj,int氺p,int氺氺b){intk,temp,f,g;g=*P;g=(12*g)-12;//intf("成功進(jìn)入快速排序g=%dg);k:i;for(;ia[k]&&i

29、p=a[i];a[i]=a[j];a[j]=temp;}}if(a[k]>a[j]){temp=a[k];a[k]=a[j];a[j]=tcmp;}//r(f=0;f<12;f++)////intf("%3d〃,a[f]);////printf("排序成功");for(f=0;f<12;f++)*(b+g+f)=a[f];}returnj;}voiddigui(int本a,inti,intj,int氺p,int氺氺b,int氺z){intk;{//intf(〃成功進(jìn)入遞歸p=%d〃,*p);氺p二氺p+1

30、;k=fast_sort(a,i,j,p,b);digui(a,i,k-1,p,b,z);digui(a,k+1,j,p,b,z);if(*p>*z)氺氺p;//printf("z=%dp=%d",*z,*p);氺p=*p_l;}}voidmain(){inta[]={38,81,22,48,13,69,93,14,45,58,79,72};intb[10][12];inty=0,k,x=0,z=0;printf(〃初始序列為〃)；for(k=0;k<12;k++)}printf("");digui(a,

31、0,11,&x,b,&z);for(y=l;y

32、的分界點(diǎn)。輸出結(jié)果要求：輸出每一次分區(qū)后的結(jié)果以及最終排序結(jié)果。四、實(shí)驗(yàn)總結(jié)（問(wèn)題、解決方法、心得體會(huì)等）這次實(shí)驗(yàn)我做了很久，重新編寫了算法很多次。最開始我對(duì)算法的理解不夠深，在遞歸自調(diào)用的時(shí)候沒(méi)有想通上下界其實(shí)在遞歸下一層的時(shí)候下一層是知道上一層的上下界的，只要排序算法里返還一個(gè)最好作為比較值的位置就可以了。一開始排序算法寫完就把每次數(shù)輸出出來(lái)，知道后來(lái)和同學(xué)討論正確答