循環(huán)賽日程表算法分析

本文格式為Word版，下載可任意編輯——循環(huán)賽日程表算法分析南京郵電大學(xué)通達(dá)學(xué)院測驗(yàn)報(bào)告測驗(yàn)名稱：

快速排序算法課程名稱：微型計(jì)算機(jī)原理與接口技術(shù)姓名班級(jí)學(xué)號(hào)：

錢煜中14250114250120測驗(yàn)時(shí)間：

2022.12.2快速排序原理一、測驗(yàn)原理：

快速排序算法quicksort主要是利用分治遞歸的思想舉行排序的方法。它的原理是首先從待排序的原始序列a[p,…,r]中選取一個(gè)元素a[q]作為分界點(diǎn)（pivot），然后將序列分為兩個(gè)子序列，左邊子序列a[p,…,q-1]元素的值都小于分界點(diǎn)m，右邊子序列a[q+1,…,r]元素值都大于分界點(diǎn)的值，此時(shí)得到的序列命名為a’，而a[q]理應(yīng)處于其排好序后的正確位置。然后利用遞歸的思想，對(duì)左右兩個(gè)子序列a[p,…,q-1]和a[q+1,…,r]再分別舉行排序，直到子序列的長度為1終止，序列有序。

其中，選取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）的值。概括第一次分區(qū)過程如下：

因此，第一次分區(qū)，以69為分界點(diǎn)，結(jié)果為:a’=[14,58,22,48,13,38,45,69,93,81,79,72]。

二、測驗(yàn)代碼#includeintfast_sort(int*a,inti,intj,int*p,int**b){intk,temp,f,g;g=*p;g=(12*g)-12;//intf(“告成進(jìn)入快速排序g=%d\n“,g);k=i;i++;for(;ia[k]a[k]=a[j];a[j]=temp;}//r(f=0;f*z)*z=*p;//printf(“z=%d\np=%d“,*z,*p);*p=*p-1;}}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(“%3d“,a[k]);}printf(“\n“);digui(a,0,11,for(y=1;y<z+1;y++){printf(“第%2d次后的數(shù)組為“,y);for(k=0;k<12;k++)printf(“%3d“,b[y-1][k]);printf(“\n“);}}三、測驗(yàn)數(shù)據(jù)（給出測驗(yàn)結(jié)果）對(duì)序列a=[38,81,22,48,13,69,93,14,45,58,79,72]388122481369931445587972381422481369938145587972381422134869938145587972舉行快速排序，其中，以序列的首元素作為排序的分界點(diǎn)。輸出結(jié)果要求：輸出每一次分區(qū)后的結(jié)果以及最終排序結(jié)果。

四、測驗(yàn)總結(jié)（問題、解決方法、心得體會(huì)等）這次測驗(yàn)我做了很久，重新編寫了算法好多次。最開頭我對(duì)算法的理解不夠深，在遞歸自調(diào)用的時(shí)候沒有想通上下界其實(shí)在遞歸下一層的時(shí)候下一層是知道上一層的上下界的，只要排序算法里返還一個(gè)最好作為對(duì)比值的位置就可以了。一開頭排序算法寫完就把每次數(shù)輸出出來，知道后來和同學(xué)議論正確答案是排序了多少次，才想想到我是把每個(gè)區(qū)排完后的處境，而其實(shí)我想輸出的是每次排序后數(shù)組處境。可是一開頭進(jìn)入的就是左半?yún)^(qū)的左半?yún)^(qū)的左半?yún)^(qū)。。。反正一次是無法輸出全部的，由于右半?yún)^(qū)還沒有算。斟酌了很久，我抉擇建立一個(gè)二維數(shù)組，第一行是第一次后的數(shù)組，其次行是其次次后的數(shù)組?？墒侨绾未_定現(xiàn)在是第幾次？我建立了一個(gè)指針，每次進(jìn)入遞歸一層就會(huì)+1，每次出遞歸就