10内部排序

第10章内部排序10.1以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：(1)直接插入排序(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}比较6次（4与每个元素比较一次）,交换1次（4与2交换）第二次的两个序列枢轴分别为2和6,此时划分序列得{1},2,{3},4,{5},6,{7}比较4次（两个序列各比较两次）,交换两次（1和2,6和5）第三次由于各个序列的元素都为1,因此排序完成得1,2,3,4,5,6,710.12判别以下序列是否为堆（大顶堆或小顶堆）。如果不是，则把它调整为堆（要求记录交换的次数最少）。（1）（100,86,48,73,35,39,42,57,66,21）；（2）（12,70,33,65,24,56,48,92,86,33）；（3）（103,97,56,38,66,23,42,12,30,52,06,20）；（4）（05,56,20,23,40,38,29,61,35,76,28,100）。（1）大顶堆；（2）否。调整为小顶堆如下：（12，24，33，65，33，56，48，92，86，70）（3）大顶堆；（4）否。调整为小顶堆如下：（05，23，20，35，28，38，29，61，56，76，40，100）10.23试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且KMAXSIZE。voidInsert_Sort1(SqList&L)//监视哨设在高下标端的插入排序算法{k=L.length;for(i=k-1;i;--i)//从后向前逐个插入排序if(L.r[i].keyL.r[i+1].key){L.r[k+1].key=L.r[i].key;//监视哨for(j=i+1;L.r[j].keyL.r[i].key;++j)L.r[j-1].key=L.r[j].key;//前移L.r[j-1].key=L.r[k+1].key;//插入}}//Insert_Sort110.26如下述改写教科书10.3节中所述起泡排序算法：将1.4.3节的算法中用以起控制作用的布尔变量change改写为一个整型变量，指示每一趟排序进行交换的最后一个记录的位置，并以它作为下一趟起泡排序循环终止的控制值。voidBubble_Sort1(inta[],intn)//对包含n个元素的数组a进行改进的冒泡排序{change=n-1;//change指示上一趟冒泡中最后发生交换的元素while(change){for(c=0,i=0;ichange;i++)if(a[i]a[i+1]){a[i]-a[i+1];c=i;//c指示这一趟冒泡中发生交换的元素}change=c;}//while}//Bubble_Sort110.31编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求:(1)采用顺序存储结构,至多使用一个记录的辅助存储空间(2)算法的时间复杂度(3)讨论算法中记录的最大移动次数.voidDivide(inta[],intn)//把数组a中所有值为负的记录调到非负的记录之前{low=0;high=n-1;while(lowhigh){while(lowhigh&&a[high]=0)high--;//以0作为虚拟的枢轴记录a[low]-a[high];while(lowhigh&&a[low]0)low++;a[low]-a[high];}}//Divide时间复杂度为O（n）最大移动次数为n/210.33试以单链表为存储结构实现简单排序的算法。voidLinkedList_Select_Sort(LinkedList&L)//单链表上的简单选择排序算法{for(p=L;p-next-next;p=p-next){q=p-next;x=q-data;for(r=q,s=q;r-next;r=r-next)//在q后面寻找元素值最小的结点if(r-next-datax){x=r-next-data;s=r;}if(s!=q)//找到了值比q-data更小的最小结点s-next{p-next=s-next;s-next=q;q-next=p-next-next;t=s-next;t-next=s-next-next;}//交换q和s-next两个结点}//for}//LinkedList_Select_Sort