9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?
【解答】
9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次关键码比较。
(1) 直接插入排序
(2) 希尔排序(增量为5,2,1)
(3) 起泡排序
(4) 快速排序
(5) 直接选择排序
(6) 锦标赛排序
(7) 堆排序
(8) 二路归并排序
(9) 基数排序
【解答】
9-3 在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？
【解答】
如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关键码可能向与最终它应移向的位置相反的方向移动。例如，
57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动
6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动
6 7 57 40 38 11 13 34 48 75 9 19
如9向最终方向移动
6 7 9
57 40 38 11 13 34 48 75 19
如13向相反方向移动
6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动
6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动
6 7 9 11 13 19 57 40 38 34 48 75
6 7 9 11 13 19 34 57 40 38 48 75
6 7 9 11 13 19 34
9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象放到序列的最后，第二趟把关键码最小的对象放到序列的最前面。如此反复进行。
【解答】
template
void dataList :: shake_Sort ( ) {
//奇数趟对
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
Vector从前向后, 比较相邻的关键码, 遇到逆序即交换, 直到把参加比较关键码序列
//中最大的关键码移到序列尾部。偶数趟从后向前, 比较相邻的关键码, 遇到逆序即交换, 直到把
//参加比较关键码序列中最小的关键码移到序列前端。
int i = 1, j; int exchange;
while ( i < CurrentSize ) {
//起泡排序趟数不超过n-1
exchange = 0;
//假定元素未交换
for ( j = CurrentSize-i; j >= i; j-- )
//逆向起泡
if ( Vector[j-1] > Vector[j] ) {
//发生逆序
Swap ( Vector[j-1], Vector[j] );
//交换, 最小关键码放在Vector[i-1]处
exchange = 1;
//做“发生了交换”标志
}
if ( exchange == 0 ) break;
////当exchange为0则停止排序
for ( j = i; j <= CurrentSize-i-1; j++ )
//正向起泡
if ( Vector[j] > Vector[j+1] ) {
//发生逆序
Swap ( Vector[j], Vector[j+1] );
//交换, 最大关键码放在Vector[n-i]处
exchange = 1;
//做“发生了交换”标志
}
if ( exchange == 0 ) break;
////当exchange为0则停止排序
i++;
}
}
9-5 如果待排序的关键码序列已经按非递减次序有序排列，试证明函数QuickSort( )的计算时间将下降到O(n2)。
9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序关键码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。
9-7 在实现快速排序算法时，可先检查位于两端及中点的关键码，取三者之中的数值不是最大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已排序的关键码序列，该算法的计算时间为O(nlog2n)。
9-8在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?
【解答】
可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。
9-9 试
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的关键码排在所有取正值(非负值)的关键码之前。
【解答】
9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。
(1) 这种排序方法结束的条件是什么？
(2) 写出奇偶交换排序的算法。
(3) 当待排序关键码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的关键码比较次数是多少？
【解答】
9-11 请编写一个算法，在基于单链表表示的待排序关键码序列上进行简单选择排序。
【解答】
9-12 若参加锦标赛排序的关键码有11个，为了完成排序，至少需要多少次关键码比较？
【解答】
9-13 试给出适用于锦标赛排序的胜者树的类型声明。并写一个函数，对n个参加排序的对象，构造胜者树。设n是2的幂。
【解答】
9-14 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键码后堆的变化。
(1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, guy, Ann, Jim, Kay, Ron, Jan
(2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22
(3) 同样7个数字，换一个初始排列，再按数值的递增
顺序排序：12, 19, 33, 26, 29, 35, 22
【解答】
9-15 如果只想在一个有n个元素的任意序列中得到其中最小的第k (k< nil ) and ( pb <> nil ) do
if pa↑.data <= pb↑.data
then begin
pc↑.next := pa; pc := pa; pa := pa↑.next;
end
else begin
pc↑.next := pb; pc := pb; pb := pb↑.next;
end;
if pa <> nil then pc↑.next := pa
else pc↑.next := pb;
end;
(2) 归并排序主程序
procedure mergesort( var r : pointer );
var s, t : pointer; var Q : Queue;
begin
if r = nil then return;
SetEmpty ( Q ); s := r; Enqueue( Q, r );
while s <> nil do
begin
t := s↑.next;
while ( t <> nil ) and ( s↑.data <= t↑.data ) do
begin s := t; t := t↑.next; end;
if t <> nil then
begin s↑.next := nil; s := t; EnQueue( Q, s ); end;
end;
while not IsEmpty( Q ) do
begin
r := DlQueue( Q );
if IsEmpty( Q ) then break;
s := DlQueue( Q );
merge( r, s, t ); EnQueue( Q, t );
end
end;
9-18 若设待排序关键码序列有n个关键码，n是一个完全平方数。将它们划分为
块，每块有
个关键码。这些块分属于两个有序表。下面给出一种O(1)空间的非递归归并算法：
step1: 在两个待归并的有序表中从右向左总共选出
个具有最大值的关键码；
step2: 若设在step1选出的第2个有序表中的关键码有s个，则从第1个有序表选出的关键码有
- s个。将第2个有序表选出的s个关键码与第1个有序表选出的关键码左边的同样数目的关键码对调；
step3: 交换具有最大
个关键码的块与最左块(除非最左块就是具有最大
个关键码的块)。对最右块进行排序；
step4: 除去具有最大
个关键码的块以外，对其它的块根据其最后的关键码按非递减顺序排序；
step5: 设置3个指针，分别位于第1块、第2块和第3块的起始位置，执行多次substep，直到3个指针都走到第
块为止。此时前
块已经排好序。
( subStep所做的工作是比较第2个指针与第3个指针所指关键码，将值小的与第1个指针所指关键码对调，相应指针前进1个关键码位置。
step6: 对最后第
块中最大的
个关键码进行排序。
(1) 设有16个关键码，分别存放于两个有序表{10, 12, 14, 16, 18, 20, 22, 25}和{11, 13, 15, 17, 19, 21, 23, 24}中，试根据上面的描述，写出排序的全过程，并说明它具有时间复杂度O(n)和空间复杂度O(1)。
(2) 编写相应的算法。要求两个待排序有序表的长度可以不同，但每一个表的长度都是
的倍数。
(3) 假设两个有序表分别为(x1, …, xm)和(xm+1, …, xn)，编写一个算法归并这两个有序表，得到(x1, …, xn)。设s =
。
9-19 试编写一个算法，将对象序列(x1, x2, …, xn)循环右移p个位置，0 ( p ( n。要求该算法的时间复杂度为O(n)而空间复杂度为O(1)。
【解答】
9-20 在什么条件下，MSD基数排序比LSD基数排序效率更高？
【解答】
9-21 在已排好序的序列中，一个对象所处的位置取决于具有更小关键码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域count，用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n(n-1)/2次关键码比较。
【解答】
0
0
0
0
初始状态
2
1
0
0
第1趟排序结果
3
0
0
第2趟排序结果
0
1
第3趟排序结果
template void datalist :: count_sort ( ) {
//initList是待排序表，resultList是结果表
int i, j;
int *c = new datalist ;
// c是存放计数排序结果的临时表
for ( i = 0; i < CurrentSize; i++ ) Vector[i].count = 0;
//初始化，计数值都为0
for ( i = 0; i < CurrentSize-1; i++ )
for ( j = i+1; j < CurrentSize; j++ )
if ( Vector[j].key < Vector[i].key ) Vector[i].count++;
else Vector[j].count++;
//统计
for ( i = 0; i < CurrentSize; i++ )
//在c->Vector[ ]中各就各位
c->Vector[ Vector[i].count ] = Vector[i];
for ( i = 0; i < CurrentSize; i++ ) Vector[i] = c->Vector[i];
//结果复制回当前表对象中
delete c;
}
9-22 试证明对一个有n个对象的序列进行基于比较的排序，最少需要执行nlog2n次关键码比较。
【解答】
9-23 如果某个文件经内排序得到80个初始归并段，试问
(1) 若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？
(2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？
【解答】
(1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = (logkm( = (logk80( = 3得：k3≥80。由此解得k≥3，即应取的归并路数至少为3。
(2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = (logkm( = (log1480( = 2。即至少需2趟归并可完成排序。
若限定这个趟数，由S = (logk80( = 2，有80≤k2，可取的最低路数为9。即要在2趟内完成排序，进行9路排序即可。
9-24 假设文件有4500个
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
，在磁盘上每个页块可放75个记录。计算机中用于排序的内存区可容纳450个记录。试问：
(1) 可以建立多少个初始归并段？每个初始归并段有多少个记录？存放于多少个页块中？
(2) 应采用几路归并？请写出归并过程及每趟需要读写磁盘的页块数。
【解答】
(1) 文件有4500个记录，计算机中用于排序的内存区可容纳450个记录，可建立的初始归并段有4500∕450 = 10个。每个初始归并段中有450个记录，存于450∕75 = 6个页块中。
(2) 内存区可容纳6个页块，可建立6个缓冲区，其中5个缓冲区用于输入，1个缓冲区用于输出，因此，可采用5路归并。归并过程如下：
共做了2趟归并，每趟需要读60个磁盘页块，写出60个磁盘页块。
9-25 设初始归并段为(10, 15, 31, (), (9, 20, (), (22, 34, 37, (), (6, 15, 42, (), (12, 37, (), (84, 95, () , 试利用败者树进行k路归并，手工执行选择最小的5个关键码的过程。
【解答】做6路归并排序，选择最小的5个关键码的败者树如下图所示。
9-26 设输入文件包含以下记录：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。现采用败者树生成初始归并段，请画出选择的过程。
9-27 给出12个初始归并段，其长度分别为30, 44, 8, 6, 3, 20, 60, 18, 9, 62, 68, 85。现要做4路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。
13
9.6 9.9 9.14 9.19
9.11 9.17
9.8 9.12 9.15
14
9.23 9.25 9.27
9.19 9.21
9.24 9.26
存放结果的表
4500
待排序的表
450 450 450 450 450 450 450 450 450 450
14 28 35 66
9
2250 2250
35 66 14 28
10
0
1
22
3
6
4
12
84
5
6
6
3
5
0
1
4
输出6 (4号段)
1
5
0
4
3
6
5
12
15
22
9
0
5
1
4
3
6
5
12
15
22
20
4
1
0
5
3
6
5
12
6
22
9
5
0
1
4
3
6
5
12
15
22
20
4
0
1
5
3
6
5
37
15
22
20
6
84
4
3
1
0
6
84
4
3
1
0
6
84
4
3
1
0
6
84
4
3
1
0
15递补
10
输出9 (1号段)
20递补
10
输出10 (0号段)
15递补
15
输出12 (5号段)
37递补
15
输出15 (4号段)
42递补
_973585389.unknown
_973586427.unknown
_973586555.unknown
_973587719.unknown
_1003779126.doc
_973617958.unknown
_973586602.unknown
_973586481.unknown
_973585734.unknown
_973585834.unknown
_973585622.unknown
_973584709.unknown
_973584987.unknown
_973584625.unknown
浙公网安备 33021202002483