第八章 排序（基础知识） 


8.1 【答案】以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。

　(1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序
　(5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序
　　上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。

8.2 【答案】上题的排序方法中，哪些易于在链表(包括各种单、双、循环链表)上实现? 

8.3 【答案】当R[low..high]中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)? 

8.4 【答案】若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好? 

8.5 【答案】若文件初态是反序的，且要求输入稳定，则在直接插入、直接选择、冒泡和快速排序中就选选哪种方法为宜?

8.6 【答案】有序数组是堆吗?

8.7 【答案】高度为h的堆中，最多有多少个元素?最少有多少个元素?在大根堆中，关键字最小的元素可能存放在堆的哪些地方? 

8.8 【答案】判别下列序列是否为堆(小根堆或大根堆)，若不是，则将其调整为堆：
　(1) (100,86,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).

8.9 【答案】将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n次，最多需要比较2n-1次，请说明这两种情况发生时，两个被归并的表有何特征? 

8.10 【答案】设关键字序列为(0.79，0.13，0.16，0.64，0.39，0.20，0.89，0.53，0.71，0.42)，给出桶排序的结果。

8.11 【答案】若关键字是非负整数、快速排序、归并、堆和基数排序啊一个最快?若要求辅助空间为O(1)，则应选择谁? 若要求排序是稳定的，且关键字是实数，则应选择谁?

8.12 【答案】对于8.7节的表8.2，解释下述问题：
　(1)当待排序的关键字序列的初始态分别为正序和反序时，为什么直接选择排序的时间基本相同?若采用本书8.4.1节的算法，这两种情况下的排序时间是否基本相同?
  (2)为什么数组的初态为正序时，冒泡和直接插入排序的执行时间最少?
  (3)若采用8.3.2节的快速排序，则数组初态为正序和反序时，能得到与表8.2类似的结果吗?