第九章 排序

_______排序。

13. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有_______。

14. 在快速排序、堆排序、归并排序中，_______排序是稳定的。

三、判断题

1. 直接选择排序是一种稳定的排序方法。 （ ） 2. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ） 3. 希尔排序算法的时间复杂度为O(n2)。 （ ） 4. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ） 5. 一组关键码已完全有序时，最快的排序方法是快速排序。 （ ） 6. 快速排序是排序算法中平均性能最好的一种排序。 （ ） 7. 堆是完全二叉树，完全二叉树不一定是堆。 （ ） 8. 层次遍历初始堆可以得到一个有序的序列。 （ ） 9. 从平均性能而言，快速排序最佳，其所需时间最省。 （ ）

四、算法设计题

1.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。

2.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。

3.对给定的j（1<=j<=n），要求在无序的记录区R［1…n］中找到按关键字自小到大排在第j个位置上的记录（即在无序集合中找到第j个最小元），试利用快速排序的划分思想编写算法实现上述的查找操作。

4.改写快速排序算法，要求采用前、中、后三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。