习 题
9．1一、选择题
1、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为( B )。
A、79，46，56，38，40，80 B、84，79，56，38，40，46 C、84，79，56，46，40，38 D、84，56，79，40，46，38 2、排序趟数与序列原始状态(原始排列)有关的排序方法是（ ACD ）方法。
A、插入排序 B、选择排序 C、冒泡排序 D、快速排序 3 、下列排序方法中，（ B ）是稳定的排序方法。
A、直接选择排序 B、二分法插入排序 C、希尔排序 D、快速排序 4、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。
A、选择排序 B、冒泡排序 C、插入排序 D、堆排序
5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（ C ）排序。
A、选择 B、快速 C、希尔 D、冒泡 6 、一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（ C ）。
A、(38,40,46,56,79,84) B、(40,38,46,79,56,84) C、(40,38,46,56,79,84) D、(40,38,46,84,56,79) 7、用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。
A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80 C、21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,40 8、若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（ B ）。
A、10 B、15 C、21 D、34
9、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（ A ）。 A、堆排序<快速排序<归并排序 B、堆排序<归并排序<快速排序 C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序 E、以上答案都不对
10、采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k（ ）。 A、有关 B、无关 9.2 填空题
1、在直接插入排序和直接选择排序中，若初始数据基本有序，则选用（直接插入排序），若初始数据基本反序，则选用（直接选择排序）。
2、在归并排序中，若待排序记录的个数为20，则共需要进行（5）趟归并，在第三趟归并中，是把长度为（4）的有序表归并为长度为（8）的有序表。
3、在内排序中，平均比较次数最多的是（快速排序），要求附加的内存空间最大的是（归并排序），排序时不稳定的有（希尔排序）、（选择排序）、（快速排序）和（堆排序）等几种方法。
4、对n个元素的序列进行冒泡排序，最少的比较次数是（n-1），此时元素的排列情况
（从小到大排列），在（从大到小排列）情况下比较次数最多，其比较次数为（n(n-1)/2）。
5、对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较（3）次。 9.3 应用题
1、在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。
答：稳定的排序算法有直接插入排序、折半插入排序、冒泡排序、归并排序和基数排序。
不稳定的排序算法有希尔排序、直接选择排序、堆排序、快速排序。 例子：讲课是的例子。
2、设待排序的关键码分别为28，13，72，85，39，41，6，20。按折半插入排序已使前七个记录有序，中间结果如下：
6 13 28 39 41 72 85 20
i=1 m=4 r=7 试在此基础上，沿用上述表达方式，给出继续采用折半插入第八条记录的比较过程，并回答以下问题：
(1) 使用折半插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？ (2) 在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？ 答：
插入20的过程：
① 39>20：r=m-1=3;i<=r;m=(i+r)/2=4/2=2
② 13<20: i=m+1=3;i>r;查找过程结束，插入位置为i。 最终结果为：6 13 20 28 39 41 72 85 （1）插入排序所要进行的比较次数与待排序的记录的初始状态有关。若初始状态基本有序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。若每次插入的元素在有序表中的插入位置靠中间，则查找次数最少。
（2）在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话是对的。若初始状态基本有序，则折半插入排序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。直接插入排序则每次只比较一次就找到合适位置。
3、已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。
建立初始堆：_97 87 26 61 70 12 3 45 堆排序过程：
（1）87 70 26 61 45 12 3 97;（2） 70 61 26 3 45 12 87 97; （3）61 45 26 3 12 70 87 97;（4） 45 12 26 3 61 70 87 97; （5）26 12 3 45 61 70 87 97;（6） 12 3 26 45 61 70 87 97; （7）3 12 26 45 61 70 87 97;
4、全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？
答：因排序的元素个数很大，所以需要采用排序速度较快的排序方法。排序速度比较快的排序方法有快速排序、堆排序、归并排序和基数排序等。其中快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。但堆排序则每次输出一个堆顶元素（即最大或最小元素），然后对堆
进行再调整，保证堆顶元素总是剩下元素的最大或最小的，从而可知，若在大量数据的文件中，只选取排序后的前几名，采用堆排序最合适。
5、判断下列序列是否为堆，若不是堆，则把它们调整为堆。 （1）100，85，95，75，80，60，82，40，20，10，65; （2）100，95，85，82，80，75，65，60，40，20，10; （3）100，85，40，75，80，60，65，95，82，10，20; （4）10，20，40，60，65，75，80，82，85，95，100; 答：（1）100，85，95，75，80，60，82，40，20，10，65; 是堆。 （2）100，95，85，82，80，75，65，60，40，20，10; 是堆。 （3）100，85，40，75，80，60，65，95，82，10，20; 不是堆 调整以后的堆为：
100，95，65，85，80，60，40，75，82，10，20
（4）10，20，40，60，65，75，80，82，85，95，100; 是堆。 9.4 算法题
1、假设待排序序列以单链表的形式存储，头指针为head，编写选择排序算法。（作为上机实践题目）
#include
KeyType key; //关键字域 };
struct Lnode {
Elemtype data ;
struct Lnode * next ;
} ;
void selectsort( Lnode *L) {
Lnode *p,*q,*r; Rtype temp;
for (p=L->next;p->next!=NULL;p=p->next) { q=p;
for (r=p->next;r!=NULL;r=r->next) if (q->data>r->data) q=r ; if (p!=q)
{ temp=p->data; p-.data=q->data; q->data=temp; } } }
2、试以L.e[L.len+1]这监视哨，改写直接插入排序算法。
struct Rtype {
KeyType key; //关键字域 ┆ };
# define maxlen maxsize // maxsize为分配的存储单元个数 struct ListSq
{
Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放 int len ; }
void insertsort(ListSq r, int n) //待排序元素r[1]～r[n] {
int i, j;
for (i=n;i<=2;i--) {
r.e[n+1]=r.e[i]; j=i+1;
while (r.e[n+1].key>r.e[j].key) {
r.e[j-1]=r.e[j]; j++; }
r.e[j+1]=r.e[n+1]; } }
3、奇偶交换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较；第二趟对所有的偶数i，将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则将两者交换；第三趟对奇数i；第四趟对偶数i，依次类推，直到整个序列有序为止。试问：这种排序方法的结束条件是什么？编写相应的实现算法。（作为上机实践题目）
struct Rtype
{
KeyType key; //关键字域 ┆ };
# define maxlen maxsize // maxsize为分配的存储单元个数 struct ListSq {
Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放 int len ; }
void qiousort (ListSq r, int n)
{
int flag=1; while(flag) {
flag=0; int i=1; while(i if (r.e[i].key> r.e[i+1].key) { Rtype temp=r.e[i]; r.e[i]=r.e[i+1]; r.e[i+1]=temp; flag=1; } i+=2; } i=2; while(i if (r.e[i].key> r.e[i+1].key) { Rtype temp=r.e[i]; r.e[i]=r.e[i+1]; r.e[i+1]=temp; flag=1; } i+=2; } } } 4 、设计一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。（作为上机实践题目） 算法为： struct Rtype { KeyType key; //关键字域 ┆ }; # define maxlen maxsize // maxsize为分配的存储单元个数 struct ListSq { Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放 int len ; } void dbubblesort(ListSq r, int n) { int i,j,flag; Rtype temp; flag=1; i=0; while(flag) { flag=0; for(j=n-i;j if (r.e[j].key flag=a; temp=r.e[j]; r.e[j]= r.e[j-1];