第10章 排序习题(带答案)

第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)不是堆。可把它调整为下面的小根堆：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第10章 排序习题(带答案)在线全文阅读。