文档10内部排序

内部排序10.1以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：直接插入排序(2)希尔排序(d[1]=5,d[2]=3,d[3]=1)(3)快速排序(第一个记录为基准记录)(4)堆排序(5)归并排序(6)基数排序解答：（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)快速排序(第一个记录为基准记录)第一趟：(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)简单选择排序第一趟：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不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。

（1）n=7时在最好情况下需进行多少次比较？请说明理由。

（2）对n=7给出一个最好情况的初始排列实例。解：最好的情况是每次都能均匀的划分序列.

例如4,1,3,2,6,5,7,每次使用序列的第一个元素做枢轴.比较总次数为10次,交换3次,具体如下：

第一次枢轴为4,序列划分为{2,1,3},4,{6,5,7}

x=r->next->data;

s=r;

}

if(s!=q)//找到了值比q->data更小的最小结点s->next

{

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