數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 實(shí)驗(yàn)10 快速排序

《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 實(shí)驗(yàn)10 快速排序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、實(shí)驗(yàn)五排序的操作(2)一、實(shí)驗(yàn)?zāi)康?．深刻理解排序的定義和各種排序方法的特點(diǎn)；2．掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法。二、實(shí)現(xiàn)提示起泡排序的排序過程：將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被放在最后。對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被放在第n-1個(gè)位置。重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行

2、過交換記錄的操作”為止?？焖倥判虻幕舅枷耄和ㄟ^一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序?？焖倥判虻呐判蜻^程：對(duì)r[s……t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，設(shè)rp=r[s]，x=rp.key。初始時(shí)令i=s,j=t。首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并和rp交換。再?gòu)膇所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄，和rp交換。重復(fù)上述兩步，直至i=j為止。再分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直

3、到每個(gè)子序列只含有一個(gè)記錄為止。三、實(shí)驗(yàn)內(nèi)容起泡排序與快速排序的實(shí)現(xiàn)，并統(tǒng)計(jì)每一種排序算法所耗費(fèi)的時(shí)間。四、程序填空與調(diào)試#include#include#include#defineN10intE[N]={213,111,222,77,400,300,987,1024,632,555};voidmerge_step(inte[],inta[],ints,intm,intn)/*兩個(gè)相鄰有序段的合并*/{inti,j,k;k=i=s;j=m+1;while(i<=m&

4、&j<=n)/*當(dāng)兩個(gè)有序都未結(jié)束時(shí)循環(huán)*/if(e[i]<=e[j])/*取其中小的元素復(fù)制*/a[k++]=e[i++];elsea[k++]=e[j++];while(i<=m)/*復(fù)制還未合并完的剩余部分*/a[k++]=e[i++];while(j<=n)/*復(fù)制還未合并完的剩余部分*/a[k++]=e[j++];}voidmerge_pass(inte[],inta[],intn,intlen)/*完成一趟完整的合并*/{intf_s,s_end;f_s=0;while(f_s+len

5、段*/s_end=f_s+f_s+2*len-1;if(s_end>=n)/*最后一段可能不足len個(gè)結(jié)點(diǎn)*/s_end=n-1;merge_step(e,a,f_s,f_s+len-1,s_end);/*相鄰有序段合并*/f_s=s_end+1;/*下一對(duì)有序段中左段的開始下標(biāo)為上一對(duì)末尾+1*/}if(f_s

6、=0;p=(int*)malloc(n*sizeof(int));while(len

7、序列為:");for(i=000;i