李云清数据结构第十张内排序

第10 章 内排序
10.1 选择题。
（1）下列序列中，（ A ）是执行第一趟快速排序后得到的序列。
A．[da,ax,eb,de,bb]ff[ha,gc] B．[cd,eb,ax,da]ff[ha,gc,bb]
C．[gc,ax,eb,cd,bb]ff[da,ha] D．[ax,bb,cd,da]ff[eb,gc,ha]
（2）下列说法错误的是（ D ）
A．冒泡排序在数据有序的情况下具有最少的比较次数。
B．直接插入排序在数据有序的情况下具有最少的比较次数。
C．二路归并排序需要借助O（n）的存储空间。
D．基数排序适合于实型数据的排序。
（3）下面的序列中初始序列构成最小堆（小根堆）的是（ D ）__________。
A．10、60、20、50、30、26、35、40
B．70、40、36、30、20、16、28、10
C．20、60、50、40、30、10、8、72
D．10、30、20、50、40、26、35、60
（4）在下列算法中，（ C ）算法可能出现下列情况：在最后一趟开始之前，所有的
元素都不在其最终的位置上。
A．堆排序 B．插入排序 C．冒泡排序 D．快速排序
（5）若需在O（nlogn）的时间内完成对数组的排序，且要求排序算法是稳定的，则可选
择的排序方法是（ A ）。
A．归并排序 B．堆排序 C．快速排序 D．直接插入排序
（6）以下排序方法中，不稳定的排序方法是（ AC ）。
A．直接选择排序 B．二分法插入排序
C．堆排序 D．基数排序
（7）一个序列中有10000 个元素，若只想得到其中前10 个最小元素，最好采用（ B ）
方法。
A．快速排序 B．堆排序 C．插入排序 D．二路归并排序
（8）若要求尽可能快地对实数数组进行稳定的排序，则应选（ C ）
A．快速排序 B．堆排序 C．归并排序 D．基数排序
（9）排序的趟数与待排序元素的原始状态有关的排序方法是（ A ）。
A．冒泡排序 B．快速排序 C．插入排序 D．选择排序
（10）直接插入排序在最好情况下的时间复杂度为（ A ）。
A．O（n） B．O（log n） C．O（nlog n） D．O（n2）
10.2 给出初始待排序码{27，46，5，18，16，51，32，26}使用下面各种排序算法的状
态变化示意图：
（1）直接插入排序；
【答】：
101
[27] 46 5 18 16 51 32 26
[27 46] 5 18 16 51 32 26
[5 27 46] 18 16 51 32 26
[5 18 27 46] 16 51 32 26
[5 16 18 27 46] 51 32 26
[5 16 18 27 46 51] 32 26
[5 16 18 27 32 46 51] 26
[5 16 18 26 27 32 46 51]
（2）表插入排序；
【答】：
key 27 46 5 18 16 51 32 26
link
0 1 2 3 4 5 6 7 8
（a）初始存储状态
（b）
（c）
（d）
（e）
（f）
key 27 46 5 18 16 51 32 26
link 1 0
0 1 2 3 4 5 6 7 8
key 27 46 5 18 16 51 32 26
link 1 2 0
0 1 2 3 4 5 6 7 8
key 27 46 5 18 16 51 32 26
link 3 2 0 1
0 1 2 3 4 5 6 7 8
key 27 46 5 18 16 51 32 26
link 3 2 0 4 1
0 1 2 3 4 5 6 7 8
key 27 46 5 18 16 51 32 26
link 3 2 0 5 1 4
0 1 2 3 4 5 6 7 8
key 27 46 5 18 16 51 32 26
link 3 2 6 5 1 4 0
0 1 2 3 4 5 6 7 8
102
（g）
(h)
(i)
（3）二分法插入排序；
【答】：这里只给出最后一趟将26 二分插入前面的有序序列的过程。
26<27,将high=mid-1;
26>16,将low=mid+1;
26>16，将low=mid+1;
此时，high<low,二分定位结束，将4…7 的所有元素后移一位，将26 插入到low 指定的位
置。
最终排序结果为：
key 27 46 5 18 16 51 32 26
link 3 7 6 5 1 4 0 2
0 1 2 3 4 5 6 7 8
key 27 46 5 18 16 51 32 26
link 3 7 6 5 8 4 0 2 1
0 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
5 16 18 27 32 46 51 26
low mid high
1 2 3 4 5 6 7 8
5 16 18 27 32 46 51 26
low mid high
1 2 3 4 5 6 7 8
5 16 18 27 32 46 51 26
low,high
1 2 3 4 5 6 7 8
5 16 18 27 32 46 51 26
high low
1 2 3 4 5 6 7 8
5 16 18 27 32 46 51 26
high low
103
（4）直接选择排序；
【答】：
（5）冒泡排序；
1 2 3 4 5 6 7 8
5 16 18 26 27 32 46 51
1 2 3 4 5 6 7 8
27 46 5 18 16 51 32 26
i=1 k=3
1 2 3 4 5 6 7 8
5 46 27 18 16 51 32 26
i=2 k=5
1 2 3 4 5 6 7 8
5 16 27 18 46 51 32 26
i=3 k=4
1 2 3 4 5 6 7 8
5 16 18 27 46 51 32 26
i=4 k=8
1 2 3 4 5 6 7 8
5 16 18 26 46 51 32 27
i=5 k=8
1 2 3 4 5 6 7 8
5 16 18 26 27 51 32 46
i=6 k=7
1 2 3 4 5 6 7 8
5 16 18 26 27 32 51 46
i=7 k=8
1 2 3 4 5 6 7 8
5 16 18 26 27 32 46 51
i=8
104
【答】：
27 46 5 18 16 51 32 26
27 5 18 16 46 32 26 [51]
5 18 16 27 32 26 [46 51]
5 16 18 27 26 [32 46 51]
5 16 18 26 [27 32 46 51]
5 16 18 [26 27 32 46 51]
（6）快速排序；
【答】：
27 46 5 18 16 51 32 26
[26 16 5 18] 27 [51 32 46]
[18 16 5] 26 27 [51 32 46]
[5 16] 18 26 27 [51 32 46]
5 [16] 18 26 27 [51 32 46]
5 16 18 26 27 [46 32] 51
5 16 18 26 27 [32] 46 51
5 16 18 26 27 32 46 51
（7）二路归并排序；
【答】：
[27] [46] [5] [18] [16] [51] [32] [26]
[27 46] [5 18] [16 51] [26 32]
[5 18 27 46] [16 26 32 51]
[5 16 18 26 27 32 46 51]
（8）基数排序。
【答】：
10.3 在冒泡排序过程中，有的排序码在某一次起泡中可能朝着与最终排序相反的方向移
动，试举例说明。在快速排序过程中是否也会出现这种现象？
【答】：
例如，80 ，70，40，50 在第一趟冒泡后序列变为70，40，50，80，70 朝着与最终排序相
反的方向移动了。
在快速排序中也会出现这种情况，例如，对序列[90，32，25，50，60]以90 划分时，序
列变为[60，32，25，50]，90，其中60 也朝与最终排序相反的方向移动了。
10.4 修改冒泡排序算法，使第一趟把排序序码最大的记录放到最末尾，第二趟把排序码
最小的记录在最前面，如此反复进行，达到排序的目的。
【答】：
#include “table.h”
/冒泡排序/
105
void bubblesort(table *L)
{ int i,j,k,done;
i=1;j=L->length;done=1;
while (done)
{
done=0;
for (k=i;k<=j;k++)
if (L->r[k+1].keyr[k].key)
{
L->r[0]=L->r[k];
L->r[k]=L->r[k+1];
L->r[k+1]=L->r[0];
done=1;
}
j–;
done=0;
for (k=j;k>=i;k–)
if (L->r[k].keyr[k-1].key)
{
L->r[0]=L->r[k];
L->r[k]=L->r[k-1];
L->r[k-1]=L->r[0];
done=1;
}
i++;
}
}
int main()
{ table L; /定义表L/
input(&L,“in.txt”); /从文件in.txt 中读入排序数据/
print(L); /输出原表/
bubblesort(&L);
print(L); /输出排序后的表/
}
10.5 对习题10.2 中给出的初始数列，给出堆排序中建堆过程示意图。
10.6 ［计数排序］一个记录在已排序的文件中的位置，可由此文件中比该记录排序码小
的记录的个数而定，由此得到一个简单的排序方法，对于每一个记录，增加一个count 字段确
106
定在已排序的文件中位于该记录之前的记录的个数，写一个算法，确定一个无序文件中的每
个记录的count 的值，并证明若文件有n 个记录，则至多进行n(n − 1)/2 次排序码比较，即
可确定所有记录的count 值。
10.7 设计一个算法，重新排列一组整数位置，使所有负值的整数位于正值的整数之前（不
要对这一组整数进行排序，要求尽量减少算法中的交换次数）。
10.8 对本章中的各种排序算法，说明哪些是稳定的？哪些是不稳定的？对不稳定的排序
算法举例说明。
10.9 总结本章中各种排序算法的特点，分析比较各算法的时间、空间复杂度及附加存储
空间情况。
10.10 一油田欲建设一条连接油田内n 口油井的主输油管道，管道由东向西，从每一口
油井都有一条支输油管道和主输油管道相连。如果知道每口油井的具体位置，应该如何确定主
输油管道的建设位置，使得所有支输油管道的长度之和最小。
10.11 某大学一、二、三年级的学生报名参加一知识竞赛，报名信息包括年级和姓名，
已知这3 个年级都有学生报名，报名信息中的年级用1、2、3 表示，设计一个算法对所有报名
参赛学生按年级排序，要求排序算法的时间复杂度是线性的。____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________