（1）n-1 （2）从小到大排序 （3）元素从大到小排列 （4）n(n-1)/2 【解析】初始元素正序时，第一趟比较n-1次，并无数据交换，则不再比较，故只比较n-1次。若反序，则比较(n-1)+(n-2)+(n-3)+…..+2+1共n(n-1)/2次。 4．希尔排序是把记录按下标的一定增量分组，对每组记录进行直接插入排序，随着增量_____________，所分成的组包含的记录越来越多，当增量的值为_____________时，整个数组合为一组。 【答案】（1）减少 （2）1
5．直接插入排序需借助的存储单元个数（空间复杂度）为_____________，最好情况下直接插入排序的算法时间复杂度为_____________，最坏情况下该算法的时间复杂度为_____________。 【答案】（1）1 （2）O(n) （3）O(n2)
6．对n个数据进行简单选择排序，所需进行的关键字间的比较次数为_____________，时间复杂度为_____________。 【答案】（1）n(n-1)/2 （2）O(n2)
7．对于关键字序列(12，13，11，18，60，15，7，20，25，100)，用筛选法建堆，必须从键值为_____________的关键字开始。 【答案】60
【解析】建堆必须从n／2结点开始，而10／2=5位置的结点值为60，故填60。 8．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较_____________次。 【答案】3
【解析】当把第7个记录60插入到有序表时，则前6个记录已经有序，此时记录60由后向前与有序表中的元素进行比较，直到遇到值小于60的记录为止，也即在有序表(15，23，38，54，72，96)中共需比较3次，因此填3。
9．若对顺序存储在A[l]～A[9]的记录(76，38，62，53，80，74，83，65，85)进行堆排序，已知除第一个元素76外，以其余元素为根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到A数组下标为_____________的位置上。 【答案】8
【解析】从树结构关键字值看，除根外是小根堆。对第一元素进行筛运算时，得到的数据序列为：38,53,62,65,80,74,83,76,85。
11．在时间复杂度为O(log2n)的排序方法中，_____________排序方法是稳定的；在时间复杂度为O(n)的排序方法中，_____________排序方法是不稳定的。 【答案】（1）归并 （2）直接选择
12．设表中元素的初态是按键值递增的，若分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则_____________最省时间，_____________最费时间。
【答案】（1）冒泡排序 （2）快速排序
【解析】若初始序列已经有序，则冒泡排序仅需一趟(比较n-1次)；而快速排序则需n-1趟，其时间复杂度升至O(n2)。因此填：冒泡排序，快速排序。 13．从一个无序序列建立一个堆的方法是：首先将要排序的n个键值分放到一棵______________的各个结点中，然后从i=_____________的结点Ki开始，逐步把以Ki-1、Ki-2、…、K1为根的子树排成堆，直到以Kl为根的树排成堆，就完成了建堆的过程。
【答案】（1）完全二叉树 （2）n／2下取整。 9.4 应用题
2．冒泡排序算法是否稳定？为什么？
【答案】冒泡排序算法是稳定的。因为依据该排序算法的基本思想，排序过程只比较相邻两个记录的关键字，若交换记录也只在相邻二个记录之间进行，从而可知在交换过程中不会出现跨越多个记录的情形。即使是相邻两个记录关键字相同
时，经过比较也不会产生相邻记录的交换。所以冒泡排序法不会改变相同关键字记录的相对次序，故是稳定的。
3．在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？
【答案】如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如： 初始关键字：59 45 10 90 第一趟排序：45 10 59 90 第二趟排序：10 45 59 90
其中45在第一趟排序中移向了与最终位置相反的方向。但在快速排序中不会出现这种情况，因为在每趟排序中，比基准元素大的都交换到右边，而比基准元素小的都交换到左边。
4．设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。
（1） 直接插入排序 （3） 起泡排序 （5） 基数排序
（2） 希尔排序（增量为5,2,1） （4） 快速排序 （6） 堆排序
【答案】
（1） 直接插入排序
（2） 希尔排序(增量为5,2,1)
（3）起泡排序
（4） 快速排序
（5）基数排序
按最低位分配
收集
按最高位分配
收集