if( exchange ==0)break; m当 exchange为0则停止排序 ++ 9-5如果待排序的关键码序列已经按非递减次序有序排列,试证明函数 QuickSort()的计算时 间将下降到On2)。 9-6在实现快速排序的非递归算法时,可根据基准对象,将待排序关键码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序,试证明在此做法下,快速排序所需要的栈的 深度为Olog2n)。 9-7在实现快速排序算法时,可先检查位于两端及中点的关键码,取三者之中的数值不是最 大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法,并证明对于已 排序的关键码序列,该算法的计算时间为 O(nlog2n) 9-8在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈?为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中,通过一趟划分,可以把一个待排序区间分 为两个子区间,然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时, 保存另一个子区间的上界和下界,待该区间处理完成后再从栈中取出另一子区间的边界,对 其进行处理。这个功能利用队列也可以实现,只不过是处理子区间的顺序有所变动而已 9-9试设计一个算法使得在O(n)的时间内重排数组将所有取负值的关键码排在所有取正 值(非负值)的关键码之前。 【解答】 9-10奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描,第二趟 对序列中的所有偶数项i扫描。若A[>A[计+1],则交换它们。第三趟有对所有的奇数项, 第四趟对所有的偶数项 如此反复,直到整个序列全部排好序为止 (1)这种排序方法结束的条件是什么? (2)写出奇偶交换排序的算法 ,(3)当待排序关键码序列的初始排列是从小到大有序,或从大到小有序时,在奇偶交换 序过程中的关键码比较次数是多少 【解答】 9-11请编写一个算法,在基于单链表表示的待排序关键码序列上进行简单选择排序 【解答】 9-12若参加锦标赛排序的关键码有11个,为了完成排序,至少需要多少次关键码比较? 【解答】 9-13试给出适用于锦标赛排序的胜者树的类型声明。并写一个函数,对n个参加排序的对 象,构造胜者树。设n是2的幂。 【解答】 跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键码后堆if ( exchange == 0 ) break; ////当 exchange 为 0 则停止排序 i++; } } 9-5 如果待排序的关键码序列已经按非递减次序有序排列，试证明函数 QuickSort( )的计算时 间将下降到 O(n 2 )。 9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序关键码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的 深度为 O(log2n)。 9-7 在实现快速排序算法时，可先检查位于两端及中点的关键码，取三者之中的数值不是最 大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已 排序的关键码序列，该算法的计算时间为 O(nlog2n)。 9-8 在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈? 为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分 为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时， 保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对 其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。 9-9 试设计一个算法, 使得在 O(n)的时间内重排数组, 将所有取负值的关键码排在所有取正 值(非负值)的关键码之前。 【解答】 9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项 i 扫描，第二趟 对序列中的所有偶数项 i 扫描。若 A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项， 第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。 (1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。 (3) 当待排序关键码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换 排序过程中的关键码比较次数是多少？ 【解答】 9-11 请编写一个算法，在基于单链表表示的待排序关键码序列上进行简单选择排序。 【解答】 9-12 若参加锦标赛排序的关键码有 11 个，为了完成排序，至少需要多少次关键码比较？ 【解答】 9-13 试给出适用于锦标赛排序的胜者树的类型声明。并写一个函数，对 n 个参加排序的对 象，构造胜者树。设 n 是 2 的幂。 【解答】 9-14 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键码后堆