资源描述：
《清华大学课程讲义-数据结构答案9》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、9-1什么是内排序？什么是外排序？什么排序方法是稳定的？什么排序方法是不稳定的?【解答】9-2设待排序的关键码序列为{12,2,16,30,28,10,16*,20,6,18},试分别写出使用以F排序方法每趟排序后的结杲。(1)直接插入排序(4)快速排序(7)堆排序并说明做了多少次关键码比较。⑶起泡排序(6)锦标赛排序(9)基数排序(2)希尔排序(增量为5,2,1)(5)直接选择排序(8)二路归并排序【解答】9-3在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？【解答】如來
2、在待排序序列的厉而的若干关键码比前而的关键码小，则在起泡排序的过程中，关键码可能向与最终它应移向的位置相反的方向移动。例如，57.40、.38.13、34、48、.75、69、7如9向相反方向移动性657、o、”38、AXA、7%"9如19向相反方向移动67”5738VXJ1、、1334、48xa75、9"19如9向最终方向移动679“5740^3813n、34*48“75、19如13向相反方向移动67911X57、40、1319•34*4875如13向最终方向移动6791113U5740、話、19344875如34向相反
3、方向移动679111319°、40、38、34487567911131934”57A40384875679111319349-4试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最人的对象放到序列的最后，第二趟把关键码最小的对象放到序列的最前面。如此反复进行。【解答】templatevclassType>voiddataList::shake_Sort(){〃奇数趟对MVector从前向后，比较和邻的关键码，遇到逆序即交换，直到把参加比较关键码序列〃中最人的关键码移到序列尾部。偶数趟从后向前，比较和邻
4、的关键码，遇到逆序即交换，直到把〃参加比较关键码序列中最小的关键码移到序列丽端。inti=1J;intexchange;while(i=i;j一一)if(Vector[]-]>Vector[j]){Swap(Vector[j-],Vector[j]);exchange=1;}if(exchange==0)break;for(j=i;j<=CurrentSize^};j++)if(Vector[j]>Vector[j+1]){Swap
5、(Vector[j],Vector[j+]);exchange=1;〃起泡排序趟数不超过n-1〃假定元素未交换〃逆向起泡〃发生逆序〃交换，最小关键码放在Vector[i-}]处〃做“发生了交换”标志////当exchange为0则停止排序〃正向起泡〃发生逆序〃交换，最人关键码放在Vector[n~i]处〃做“发生了交换”标志////当exchange为0则停止排序if(exchange==0)break;i++；9-5如果待排序的关键码序列已经按非递减次序有序排列，试证明函数Quicksort^)的计算时间将下降到0(,)。9
6、-6在实现快速排序的非递归算法时，可根据基准对象，将待排序关键码序列划分为两个了序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)o9-7在实现快速排序算法时，可先检査位于两端及中点的关键码，取三者Z中的数值不是最大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已排序的关键码序列，该算法的计算时间为O(nlog2n)o9-8在使用非递归方法实现快速排序时，通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列來代替这个栈？为什么？【解答】可以用队
7、列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区问，然后分别对这两个子区问施行同样的划分。栈的作用是在处理一个子区间时,保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也町以实现，只不过是处理子区间的顺序有所变动而己。9-9试设计一个算法，使得在0⑺的时间内重排数组，将所有取负值的关键码排在所有取正值(非负值)的关键码Z前。【解答】9-10奇偶交换排序是另一种交换排序。它的笫一趟对序列中的所有奇数项i扫描，笫二趟对序列中的所有偶数项i扫描。
8、若A[i>A[i+],则交换它们。笫三趟有対所有的奇数项，第四趟对所有的偶数项，・・・，如此反复，直到整个序列全部排好序为止。(1)这种排序方法结束的条件是什么？(2)写出奇偶交换排序的算法。(3)当待排序关键码序列的初始排列是从小到大有序，或从大到小有序时
