第10章 综合练习
1. 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?
2. 设待排序的关键字序列为(15, 21, 6, 30, 23, 6′, 20, 17), 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。
(1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 起泡排序
(4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序
(7) 堆排序 (8) 二路归并排序 (9) 基数排序
3. 在起泡排序过程中，什么情况下关键字会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？
4. 快速排序在什么情况下所需关键字的比较次数最多？此时关键字比较次数应为多少？
【解答】 在待排序关键字有序的情况下，快速排序的关键字的比较次数最多，为n(n-1)/2次。
5. 用直接插入排序方法对序列(94,32,40,90,80,46,21,69)进行排序（由小到大），试写出排序的过程。
【解答】 初始状态： 监视哨【94】 32 40 90 80 46 21 69
第1趟插入排序：【32】【32 94】 40 90 80 46 21 69
第2趟插入排序：【40】【32 40 94】 90 80 46 21 69
第3趟插入排序：【90】【32 40 90 94】 80 46 21 69
第4趟插入排序：【80】【32 40 80 90 94】 46 21 69
第5趟插入排序：【46】【32 40 46 80 90 94】 21 69
第6趟插入排序：【21】【21 32 40 46 80 90 94】 69
第7趟插入排序：【69】【21 32 40 46 69 80 90 94】
6. 已知初始序列为(125 ，11， 22， 34， 15， 44， 76， 66， 100， 8 ，14， 20， 2， 5， 1)，写出采用希尔排序算法排序的每一趟的结果（增量为5，3，1）。
7. 写出对初始序列(50,72,43,85,75,20,35，45，65，30)进行直接选择排序的过程。
8. 若用冒泡排序对关键字序列(18,16,14,12,10,8),进行从小到大的排序，所需进行的关键字比较次数是多少。
9. 给出关键字序列(27，18，21，77，26，45，66，34)，试写出快速排序过程。
10. 无序序列为(10，2，13，15，12，14)，用堆排序方法从小到大排序，画出堆排序的初态、建堆和重建堆的过程。
11. 写出对序列(28，16，32，12，60，2，5，72)进行2路归并排序的过程。
12. 给出如下关键字序列(321，156，057，046，028，007，331，033，034，063)，试按链式基数排序方法，列出每一趟分配和收集的过程。
13. 若参加锦标赛排序的关键字有11个，为了完成排序，至少需要多少次关键字比较？
14. 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键字后堆的变化。 (1) 按字母顺序排序：this,that, am, is, are, she, her, he, him (2) 按数值递增顺序排序：23, 35, 15,31, 19, 2, 20 (3) 同样7个数字，换一个初始排列，再按数值的递增顺序排序：2, 19, 23, 20, 15, 35, 31
15. 如果只想在一个有n个元素的任意序列中得到其中最小的第k (k<<n) 个元素之前的部分排序序列, 那么最好采用什么排序方法? 为什么? 例如有这样一个序列：(503, 017, 512, 908, 170, 897, 275, 653, 612, 154, 509, 612′, 677, 765, 094)，要得到其第4个元素之前的部分有序序列：(017, 094, 154, 170)， 用所选择的算法实现时，要执行多少次比较?
16. 设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其进行排序（按递增顺序），哪种排序最省时间，哪种排序最费时间。
17. 如果某个文件经内排序得到80个初始归并段，试问：
(1) 若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？
(2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？
18. 假设文件有4500个记录，在磁盘上每个页块可放75个记录。计算机中用于排序的内存区可容纳450个记录。试问：
(1) 可以建立多少个初始归并段？每个初始归并段有多少个记录？存放于多少个页块中？
(2) 应采用几路归并？请写出归并过程及每趟需要读写磁盘的页块数。
19. 设输入文件包含以下记录：14, 22, 7, 24, 15, 16, 11, 100, 10, 9, 20, 12, 90, 17, 13, 19, 26, 38, 30, 25, 50, 28, 110, 21, 40。现采用败者树生成初始归并段，请画出选择的过程。
20. 给出12个初始归并段，其长度分别为30, 44, 8, 6, 3, 20, 60, 18, 9, 62, 68, 85。现要做4路外部归并排序，画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。
【解答】因为(12-1)%(4-1)=2，所以，第一次用3个归并段归并。
17
21. 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。
(1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。
(3) 当待排序的关键字序列的初始排列是从小到大有序，从大到小有序时，在奇偶交换排序过程中的关键字比较次数是多少？
void SwapSort( rectype A[],int n)
//对A[1..n]进行奇偶交换排序
{ exchange=false;
while(! Exchange)
{exchange=true; i=1; //奇数项排序
while( i<n)
(if( A[i]>A[i+1]) { A[i]ß>A[i+1]; exchange=false ;}
i:=i+2;
}
i:=2;
while( i<n) // 偶数项排序
{if( A[i]>A[i+1]) { [A[i]ß>A[i+1]; exchange=false ; ]
i:=i+2;
}
}
讨论：1 排序结束的条件是一趟排序中无交换
2 正序时需n-1次比较；
3 正序时需n(n-1)/2次比较和交换
22. 请编写一个算法，在基于单链表表示的关键字序列上进行简单选择排序。
void LinkedListSelectSort(LinkedList head)
//本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下
//当前结点和最小结点的前驱指针
p=head->next;
while(p!=null)
{q=p->next; r=p; //设r是指向关键字最小的结点的指针
while (q!=null)
{if(q->data<r->data)
r=q;
q:=q->next;
}
if(r!=p) r->data<-->p->data;
p=p->next;
}
23. 设单链表头结点指针为L，结点数据值为整型。试写出对链表L按“插入方法”排序的算法：LINSORT(L)。
void
linkedinsert(LinkedList la)
//对带头结点的单链表la进行直接插入排序
{p=la->next; //p指向待插入结点
la->next=null; //初始化成空表
while(p!=null) 逐个结点按序插入
{r=p->next; // 保留后继
pre=la;
q=la->next;
while(q && q->data<p->data) //查找结点的插入位置
{pre=q; q=q->next;}
pre->next=p; //链入
p->next=q;
p=r; //p指向待插入结点
}
}
24. 试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的关键字排在所有取正值(非负值)的关键字之前。