文檔10內(nèi)部排序

內(nèi)部排序10.1以關(guān)鍵碼序列(503,087,512,061,908,170,897,275,653,426)為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時(shí)的關(guān)鍵碼狀態(tài)：直接插入排序(2)希爾排序(d[1]=5,d[2]=3,d[3]=1)(3)快速排序(第一個(gè)記錄為基準(zhǔn)記錄)(4)堆排序(5)歸并排序(6)基數(shù)排序解答：（1）直接插入排序：第一趟：087,503,512,061,908,170,897,275,653,426第二趟：087,503,512,061,908,170,897,275,653,426第三趟：061,087,503,512,908,170,897,275,653,426第四趟：061,087,503,512,908,170,897,275,653,426第五趟：061,087,170,503,512,908,897,275,653,426第六趟：061,087,170,275,503,512,897,908,653,426第八趟：061,087,170,275,503,512,653,897,908,426第九趟：061,087,170,275,426,503,512,653,897,908（2）希爾排序(d[1]=5,d[2]=3,d[3]=1)第一趟：170,087,275,061,426,503,897,512,653,908第二趟：061,087,275,170,426,503,897,512,653,908第三趟：061,087,170,275,426,503,512,653,897,908(3)快速排序(第一個(gè)記錄為基準(zhǔn)記錄)第一趟：(426,087,275,061,170)503(897,908,653,512)第二趟：(170,087,275,061)426,503(512,653)897(908)第三趟：(061,087)170(275)426,503,512(653)897,908第四趟：061,087,170,275,426,503,512,653,897,908(4)堆排序（小根堆為例）建堆：061,087,170,275,426,512,897,503,653,908第一趟：（輸出061）087,275,170,503,426,512,897,653第二趟：（輸出087）170,275,512,503,426,653,897,908第三趟：（輸出170）275,406,512,503,908,653,897第四趟：（輸出275）406,503,512,897,908,653第五趟：（輸出406）503,653,512,897,908第六趟：（輸出503）512,653,908,897第七趟：（輸出512）653,897,908第八趟：（輸出653）897,908第九趟：（輸出897）908(5)歸并排序第一趟：(087,503)(061,512)(170,908)(275,897)(426,653)第二趟：(061,087,503,512)(170,275,897,908)(426,653)第三趟：(061,087,170,275,503,512,897,908)(426,653)第四趟：061,087,170,275,426,503,512,653,897,908(6)簡(jiǎn)單選擇排序第一趟：061,087,512,503,908,170,897,275,653,426第二趟：061,087,512,503,908,170,897,275,653,426第三趟：061,087,170,503,908,512,897,275,653,426第四趟061,087,170,275,908,512,897,503,653,426第五趟061,087,170,275,426,512,897,503,653,908第六趟061,087,170,275,426,503,897,512,653,908第七趟061,087,170,275,426,503,512,653,897,90810.7不難看出，對(duì)長(zhǎng)度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依賴于這n個(gè)元素的初始排列。

（1）n=7時(shí)在最好情況下需進(jìn)行多少次比較？請(qǐng)說(shuō)明理由。

（2）對(duì)n=7給出一個(gè)最好情況的初始排列實(shí)例。解：最好的情況是每次都能均勻的劃分序列.

例如4,1,3,2,6,5,7,每次使用序列的第一個(gè)元素做樞軸.比較總次數(shù)為10次,交換3次,具體如下：

第一次樞軸為4,序列劃分為{2,1,3},4,{6,5,7}

x=r->next->data;

s=r;

}

if(s!=q)//找到了值比q->data更小的最小結(jié)點(diǎn)s->next

{

p->next=s->next;s->next=q;