第10章 排序习题
10.1以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态： (1)直接插入排序
(2)希尔排序(步长取5、3、1) (3)冒泡排序 (4)快速排序 (5)简单选择排序 (6)堆排序 (7)归并排序 (8)基数排序
上述方法中，哪些是稳定的排序?哪些是不稳定的排序? 【分析与解答】 （1）直接插入排序
(2)希尔排序
(3)冒泡排序
(4)快速排序
说明：根据快速排序的思想，当基准关键字将关键字序列划分成左右两部分后，先对左半部分进行快速排序。只有当左半部分排序好后，才开始对右半部分排序。每一趟中所划分成的左右两部分都如此进行。
(5) 简单选择排序
(6)堆排序
若要从小到大排序，则建大根堆；反之，建小根堆。下面按从小到大排序，每一趟排序的结果就是将堆项元素与堆底元素交换所得的结果。堆顶位置总是①；堆底位置是变化的，初始堆的堆底是⑩．以后是⑨、⑧、⑦、 、②．
(7)归并排序
(8)基数排序
在这些排序中(1)(3)(7)(8)是稳定的排序。 不稳定的排序有(2)(4)(5)(6)。
10.2判别下列序列是否为堆，若不是，则将其调整为堆。 (1)(100，86，48，73，35，39，42，57，66，21) (2)(12，70，33，65，24，56，48，92，86，30)
(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)不是堆。可把它调整为下面的小根堆：
(3)是大根堆。
(4)不是堆。可把它调整为下面的小根堆：