文档介绍：10-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?
10-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次关键码比较。
(1) 直接插入排序(2) 希尔排序(增量为5,2,1) (3) 起泡排序
(4) 快速排序(5) 直接选择排序(6) 锦标赛排序
(7) 堆排序(8) 二路归并排序(9) 基数排序
【解答】
10-3 在起泡排序过程中,什么情况下关键码会朝向与排序相反的方向移动,试举例说明。在快速排序过程中有这种现象吗?
10-4 试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把关键码最大的对象放到序列的最后,第二趟把关键码最小的对象放到序列的最前面。如此反复进行。
10-5 如果待排序的关键码序列已经按非递减次序有序排列,试证明函数QuickSort( )的计算时间将下降到O(n2)。
10-6 在实现快速排序的非递归算法时,可根据基准对象,将待排序关键码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序,试证明在此做法下,快速排序所需要的栈的深度为O(log2n)。
10-7 在实现快速排序算法时,可先检查位于两端及中点的关键码,取三者之中的数值不是最大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法,并证明对于已排序的关键码序列,该算法的计算时间为O(nlog2n)。
10-8在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?
10-9 试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的关键码排在所有取正值(非负值)的关键码之前。
10-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描,第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1],则交换它们。第三趟有对所有的奇数项,第四趟对所有的偶数项,…,如此反复,直到整个序列全部排好序为止。
(1) 这种排序方法结束的条件是什么?
(2) 写出奇偶交换排序的算法。
(3) 当待排序关键码序列的初始排列是从小到大有序,或从大到小有序时,在奇偶交换排序过程中的关键码比较次数是多少?
10-11 请编写一个算法,在基于单链表表示的待排序关键码序列上进行简单选择排序。
10-12 若参加锦标赛排序的关键码有11个,为了完成排序,至少需要多少次关键码比较?
10-13 试给出适用于锦标赛排序的胜者树的类型声明。并写一个函数,对n个参加排序的对象,构造胜者树。设n是2的幂。
10-14 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键码后堆的变化。
(1) 按字母顺序排序:Tim, Dot, Eva, Rom, Kim, guy, Ann, Jim, Kay, Ron, Jan
(2) 按数值递增顺序排序:26, 33, 35, 29, 19, 12, 22
(3) 同样7个数字,换一个初始排列,再按数值的递增 顺序排序:12, 19, 33, 26, 29, 35, 22
10-15 如果只想在一个有n个元素的