静态数据表类定义
#include <iostream.h>
const int DefaultSize = 100;
template <class Type> class dataList //数据表的前视声明
template <class Type> class Element { //数据表元素类的定义
friend class dataList <Type>;
private:
Type key; //排序码
field otherdata; //其它数据成员
public:
Type getKey ( ) { return key; } //取当前结点的排序码
void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为x
Element<Type>& operator = ( Element<Type>& x ) //结点x的值赋给this
{ key = x->key; otherdata = x->otherdata; }
int operator == ( Type& x ) { return key == x->key; } //判this与x相等
int operator <= ( Type& x ) { return key <= x->key; } //判this小于或等于x
int operator > ( Type& x ) { return key > x->key; } //判this大于x
int operator < ( Type& x ) { return key > x->key; } //判this小于x
}
template <class Type> class dataList {
//用顺序表来存储待排序的元素，这些元素的类型是Type
private:
Element <Type> * Vector; //存储待排序元素的向量
int MaxSize,CurrentSize; //最大元素个数与当前元素个数
int Partition ( const int low,const int high ) //用于快速排序的一次划分算法
public:
datalist ( int MaxSz = DefaultSize ), MaxSize ( Maxsz ),CurrentSize (0)
{ Vector = new Element <Type> [MaxSize]; } //构造函数
int length ( ) { return CurrentSize; }
Element<Type>& operator [ ] ( int i ) { return Vector[i]; }
void swap ( Element <Type>& x,Element <Type>& y ) //交换x,y
{ Element <Type> temp = x; x = y; y = temp; }
void Sort ( ); //排序
}
静态链表类定义
template <class Type> class staticlinkList; //静态链表类的前视声明
template <class Type> class Element { //静态链表元素类的定义
friend class staticlinkList<Type>;
private:
Type key; //排序码，其它信息略
int link; //结点的链接指针
public:
Type getKey ( ) { return key; } //取当前结点的排序码
void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为x
int getLink ( ) { return link; } //取当前结点的链接指针
void setLink ( const int ptr ) { link = ptr; } //将当前结点的链接指针置为ptr
}
template <class Type> class staticlinkList { //静态链表的类定义
private:
Element <Type> *Vector; //存储待排序元素的向量
int MaxSize,CurrentSize; //向量中最大元素个数和当前元素个数
public:
dstaticlinkList ( int Maxsz = DefaultSize ), MaxSize ( Maxsz ),CurrentSize (0)
{ Vector = new Element <Type> [Maxsz]; }
}
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) 二路归并排序
【解答】
(1) 直接插入排序
初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
i = 1
[ 12 ]
2
16
30
28
10
16*
20
6
18
1
i = 2
[ 2
12 ]
16
30
28
10
16*
20
6
18
1
i = 3
[ 2
12
16 ]
30
28
10
16*
20
6
18
1
i = 4
[ 2
12
16
30 ]
28
10
16*
20
6
18
2
i = 5
[ 2
12
16
28
30 ]
10
16*
20
6
18
5
i = 6
[ 2
10
12
16
28
30 ]
16*
20
6
18
3
i = 7
[ 2
10
12
16
16*
28
30 ]
20
6
18
3
i = 8
[ 2
10
12
16
16*
20
28
30 ]
6
18
3
i = 9
[ 2
6
10
12
16
16*
20
28
30 ]
18
8
[ 2
6
10
12
16
16*
18
20
28
30 ]
(2) 希尔排序(增量为5,2,1)
初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
12
2
16
30
28
10
16*
20
6
18
1+1+1+1+1 = 5
d = 5
10
2
16
6
18
12
16*
20
30
28
(1+1+2+1) + (1+1
d = 2
+1+1) = 9
10
2
16
6
16*
12
18
20
30
28
1+1+3+1+3+1+1
d = 1
+1+2 = 14
2
6
10
12
16
16*
18
20
28
30
希尔(shell)本人采取的增量序列为 (n/2(,((n/2(/2(,((n/2(/2(/2(,…,1。一般地，增量序列可采用(nα(,((nα(α(,((nα(α(α(,…,1。大量实验表明，取α=0.45454的增量序列比取其他的增量序列的优越性更显著。计算 (0.45454n( 的一个简单方法是用整数算术计算(5*n-1)/11。需要注意，当(< 1/2时，增量序列可能不以1结束，需要加以判断和调整。
(3) 起泡排序初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
i = 0
[ 12
2
16
30
28
10
16*
20
6
18 ]
9
i = 1
2
[ 12
6
16
30
28
10
16*
20
18 ]
8
i = 2
2
6
[ 12
10
16
30
28
16*
18
20 ]
7
i = 3
2
6
10
[ 12
16
16*
30
28
18
20 ]
6
i = 4
2
6
10
12
[ 16
16*
18
30
28
20 ]
5
i = 5
2
6
10
12
16
[ 16*
18
20
30
28 ]
4
i = 6
2
6
10
12
16
16*
[ 18
20
28
30 ]
3
2
6
10
12
16
16*
18
20
28
30
(4) 快速排序
Pivot
Pvtpos
0
1
2
3
4
5
6
7
8
9
排序码比较次数
12
0,1,2,3
[ 12
2
16
30
28
10
16*
20
6
18 ]
9
6
0,1
[ 6
2
10 ]
12
[ 28
16
16*
20
30
18 ]
2
28
4,5,6,7,8
[ 2 ]
6
[ 10 ]
12
[ 28
16
16*
20
30
18 ]
5
18
4,5,6
2
6
10
12
[ 18
16
16*
20 ]
28
[ 30 ]
3
16*
4
2
6
10
12
[ 16*
16 ]
18
[ 20 ]
28
30
1
2
6
10
12
16*
[ 16 ]
18
20
28
30
左子序列递归深度为1，右子序列递归深度为3。
(5) 直接选择排序初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
i = 0
[ 12
2
16
30
28
10
16*
20
6
18 ]
9
i = 1
2
[ 12
16
30
28
10
16*
20
6
18 ]
8
i = 2
2
6
[ 16
30
28
10
16*
20
12
18 ]
7
i = 3
2
6
10
[ 30
28
16
16*
20
12
18 ]
6
i = 4
2
6
10
12
[ 28
16
16*
20
30
18 ]
5
i = 5
2
6
10
12
16
[ 28
16*
20
30
18 ]
4
i = 6
2
6
10
12
16
16*
[ 28
20
30
18 ]
3
i = 7
2
6
10
12
16
16*
18
[ 20
30
28 ]
2
i = 8
2
6
10
12
16
16*
16
20
[ 30
28 ]
1
2
6
10
12
16
16*
16
20
28
[ 30 ]
(6)基数排序
收集
按最高位分配
收集
(7) 堆排序第一步，形成初始的最大堆 (略)，第二步，做堆排序。
初始排列，不是最大堆 形成初始最大堆 交换0# 与9# 对象
从0# 到8# 重新形成堆 交换0# 与8# 对象 从0# 到 7# 重新形成堆
交换0# 与7# 对象 从0# 到6# 重新形成堆 交换0# 与6# 对象
从0# 到5# 重新形成堆 交换0# 与5# 对象 从0# 到4# 重新形成堆
交换0# 与4# 对象 从0# 到3# 重新形成堆 交换0# 与3# 对象
从0# 到2# 重新形成堆 交换0# 与2# 对象 从0# 到1# 重新形成堆
交换0# 与1# 对象 从0# 到1# 重新形成堆，得到结果
(8) 二路归并排序
采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去，最后得到长度为n的归并结果。
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
9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把排序码最大的对象放到序列的最后，第二趟把排序码最小的对象放到序列的最前面。如此反复进行。
【解答1】
template <class Type> void dataList<Type>,,shaker_Sort ( ) {
//奇数趟对表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++;
}
}
【解答2】
template <class Type> void dataList<Type>,,shaker_Sort ( ) {
int low = 1,high = CurrentSize-1,i,j; int exchange;
while ( low < high ) { //当比较范围多于一个对象时排序
j = low; //记忆元素交换位置
for ( i = low; i < high; i++ ) //正向起泡
if ( Vector[i] > Vector[i+1] ) { //发生逆序
Swap ( Vector[i],Vector[i+1] ); //交换
j = i; //记忆右边最后发生交换的位置j
}
high = j; //比较范围上界缩小到j
for ( i = high; i > low; i-- ) //反向起泡
if ( Vector[i-1] > Vector[i] ) { //发生逆序
Swap ( Vector[i-1],Vector[i] ); //交换
j = i; //记忆左边最后发生交换的位置j
}
low = j; //比较范围下界缩小到j
}
}
9-5 如果待排序的排序码序列已经按非递减次序有序排列，试证明函数QuickSort( )的计算时间将下降到O(n2)。
【证明】
若待排序的n个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为T(n)。当以第一个对象作为基准对象时，应用一次划分算法Partition，通过n-1次排序码比较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有n-1个对象的非递减有序序列。对于这样的递归QuickSort( )算法，其时间代价为
T(n) = (n-1) + T(n-1)
= (n-1) + {( n-2) + T(n-2) }
= (n-1) + (n-2) + {(n-3) + T(n-3) }
= ……
= (n-1) + (n-2) + (n-3) + … + { 2 + T(1) }
= (n-1) + (n-2) + (n-3) + … + 2 + 1
= n(n-1)/2 = O(n2)
9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。
【解答】
由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两个子序列的长度相等，则所需栈的深度为
S(n) = 1 + S(n/2) =
= 1 + { 1 + S(n/4) } = 2 + S(n/4)
= 2 + { 1 + S(n/8) } = 3 + S(n/8)
= ……
= log2n + S(1) = log2n (假设1个对象的序列所用递归栈的深度为0)
如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递归栈中，再对较短的子序列进行排序，可用表示最坏情况的大O表示法表示。此时其递归栈的深度不一定正好是log2n，其最坏情况为O(log2n)。
9-7 在实现快速排序算法时，可先检查位于两端及中点的排序码，取三者之中的数值不是最大也不是最小的排序码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已排序的排序码序列，该算法的计算时间为O(nlog2n)。
【解答】参看教科书
9-8在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?
【解答】
可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。
9-9 试设计一个算法,使得在O(n)的时间内重排数组,将所有取负值的排序码排在所有取正值(非负值)的排序码之前。
【解答】
template<class Type> void reArrange ( dataList<Type>& L ) {
//数组元素类型Type只可能取int或float
int i = 0,j = L.length () – 1;
while ( i != j ) {
while ( L[i].getKey( ) < 0 ) i++;
while ( L[j].getKey( ) >= 0 ) j--;
swap ( L[i],L[j] );
i++; j--;
}
}
9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。
(1) 这种排序方法结束的条件是什么？
(2) 写出奇偶交换排序的算法。
(3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？
【解答】
(1) 设有一个布尔变量exchange，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描后是否有过交换。若exchange = 1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；若exchange = 0，表示刚才没有交换，可以结束排序。
(2) 奇偶排序的算法
template<Type> void dataList<Type>,,odd-evenSort ( ) {
int i,exchange;
do {
exchange = 0;
for ( i = 1; i < CurrentSize; i += 2 ) //扫描所有奇数项
if ( Vector[i] > Vector[i+1] ) { //相邻两项比较,发生逆序
exchange = 1; //作交换标记
swap ( Vector[i],Vector[i+1] ); //交换
}
for ( i = 0; i < CurrentSize; i += 2 ) //扫描所有偶数项
if ( Vector[i] > Vector[i+1] ) { //相邻两项比较,发生逆序
exchange = 1; //作交换标记
swap ( Vector[i],Vector[i+1] ); //交换
}
} while ( exchange != 0 );
}
(3) 设待排序对象序列中总共有n个对象。序列中各个对象的序号从0开始。则当所有待排序对象序列中的对象按排序码从大到小初始排列时，执行m = ((n+1)/2( 趟奇偶排序。当所有待排序对象序列中的对象按排序码从小到大初始排列时，执行1趟奇偶排序。
在一趟奇偶排序过程中，对所有奇数项扫描一遍，排序码比较 ((n-1)/2( 次；对所有偶数项扫描一遍，排序码比较 (n/2( 次。所以每趟奇偶排序两遍扫描的结果，排序码总比较次数为 ((n-1)/2( + (n/2( = n-1。
9-11 请编写一个算法，在基于单链表表示的待排序排序码序列上进行简单选择排序。
【解答】
采用静态单链表作为存储表示。用Vector[0]作为表头结点，各待排序数据对象从Vector[1]开始存放。算法的思想是每趟在原始链表中摘下排序码最大的结点(几个排序码相等时为最前面的结点)，把它插入到结果链表的最前端。由于在原始链表中摘下的排序码越来越小，在结果链表前端插入的排序码也越来越小，最后形成的结果链表中的结点将按排序码非递减的顺序有序链接。
Template<class Type> void staticlinkList<Type>,,selectSort ( ) {
int h = Vector[0].link,p,q,r,s;
Vector[0].link = 0;
while ( h != 0 ) { //原始链表未扫描完
p = s = h; q = r = 0;
while ( p != 0 ) { //扫描原始链表,寻找排序码最大的结点s
if ( Vector[p].data > Vector[s].data ) //记忆当前找到的排序码最大结点
{ s = p; r = q; }
q = p; p = Vector[p].link;
}
if ( s == h ) h = Vector[h]; //排序码最大的结点是原始链表前端结点,摘下
else Vector[r].link = Vector[s].link; //排序码最大的结点是原始链表表中结点,摘下
Vector[s].link = Vector[0].link; //结点s插入到结果链表的前端
Vector[0].link = s;
}
}
9-12 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。
(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
【解答】 为节省篇幅，将用数组方式给出形成初始堆和进行堆排序的变化结果。阴影部分表示参与比较的排序码。请读者按照完全二叉树的顺序存储表示画出堆的树形表示。
(1) 按字母顺序排序
形成初始堆（按最大堆）
0
1
2
3
4
5
6
7
8
9
10
Tim
Dot
Eva
Rom
Kim
Guy
Ann
Jim
Kay
Ron
Jan
i=4
Tim
Dot
Eva
Rom
[ Ron
Guy
Ann
Jim
Kay
Kim
Jan ]
i=3
Tim
Dot
Eva
[ Rom
Ron
Guy
Ann
Jim
Kay
Kim
Jan ]
i=2
Tim
Dot
[ Guy
Rom
Ron
Eva
Ann
Jim
Kay
Kim
Jan ]
i=1
Tim
[ Ron
Guy
Rom
Kim
Eva
Ann
Jim
Kay
Dot
Jan ]
i=0
[ Tim
Ron
Guy
Rom
Kim
Eva
Ann
Jim
Kay
Dot
Jan ]
堆排序
0
1
2
3
4
5
6
7
8
9
10
j=10
[ Jan
Ron
Guy
Rom
Kim
Eva
Ann
Jim
Kay
Dot
Tim ]
交换
[ Ron
Rom
Guy
Kay
Kim
Eva
Ann
Jim
Jan
Dot ]
Tim
调整
j=9
[ Dot
Rom
Guy
Kay
Kim
Eva
Ann
Jim
Jan
Ron ]
Tim
交换
[ Rom
Kim
Guy
Kay
Dot
Eva
Ann
Jim
Jan ]
Ron
Tim
调整
j=8
[ Jan
Kim
Guy
Kay
Dot
Eva
Ann
Jim
Rom ]
Ron
Tim
交换
[ Kim
Kay
Guy
Jim
Dot
Eva
Ann
Jan ]
Rom
Ron
Tim
调整
j=7
[ Jan
Kay
Guy
Jim
Dot
Eva
Ann
Kim ]
Rom
Ron
Tim
交换
[ Kay
Jim
Guy
Jan
Dot
Eva
Ann ]
Kim
Rom
Ron
Tim
调整
j=6
[ Ann
Jim
Guy
Jan
Dot
Eva
Kay ]
Kim
Rom
Ron
Tim
交换
[ Jim
Jan
Guy
Ann
Dot
Eva ]
Kay
Kim
Rom
Ron
Tim
调整
j=5
[ Eva
Jan
Guy
Ann
Dot
Jim ]
Kay
Kim
Rom
Ron
Tim
交换
[ Jan
Eva
Guy
Ann
Dot ]
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=4
[ Dot
Eva
Guy
Ann
Jan ]
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Guy
Eva
Dot
Ann ]
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=3
[ Ann
Eva
Dot
Guy ]
Jan
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Eva
Ann
Dot ]
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=2
[ Dot
Ann
Eva ]
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Dot
Ann ]
Eva
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=1
[ Dot
Ann ]
Eva
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Ann ]
Dot
Eva
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
(2) 按数值递增顺序排序
形成初始堆 (按最大堆)
0
1
2
3
4
5
6
26
33
35
29
19
12
22
i=2
26
33
[ 35
29
19
12
22 ]
i=0
26
[ 33
35
29
19
12
22 ]
i=1
[ 35
33
26
29
19
12
22 ]
堆排序
0
1
2
3
4
5
6
j=6
[ 22
33
26
29
19
12
35 ]
交换
[ 33
29
26
22
19
12 ]
35
调整为堆
j=5
[ 12
29
26
22
19
33 ]
35
交换
[ 29
22
26
12
19 ]
33
35
调整为堆
j=4
[ 19
22
26
12
29 ]
33
35
交换
[ 26
22
19
12 ]
29
33
35
调整为堆
j=3
[ 12
22
19
26 ]
29
33
35
交换
[ 22
12
19 ]
26
29
33
35
调整为堆
j=2
[ 19
12
22 ]
26
29
33
35
交换
[ 19
12 ]
22
26
29
33
35
调整为堆
j=1
[ 12
19 ]
22
26
29
33
35
交换
[ 12 ]
19
22
26
29
33
35
调整为堆
(3) 同样7个数字，换一个初始排列，再按数值的递增顺序排序形成初始堆 (按最大堆)
0
1
2
3
4
5
6
12
19
33
26
29
35
22
i=2
12
19
[ 35
26
29
33
22 ]
i=0
12
[ 29
35
26
19
33
22 ]
i=1
[ 35
29
33
26
19
12
22 ]
堆排序
0
1
2
3
4
5
6
j=6
[ 22
29
33
26
19
12
35 ]
交换
[ 33
29
22
26
19
12 ]
35
调整为堆
j=5
[ 12
29
22
26
19
33 ]
35
交换
[ 29
26
22
12
19 ]
33
35
调整为堆
j=4
[ 19
26
22
12
29 ]
33
35
交换
[ 26
19
22
12 ]
29
33
35
调整为堆
j=3
[ 12
19
22
26 ]
29
33
35
交换
[ 22
19
12 ]
26
29
33
35
调整为堆
j=2
[ 12
19
22 ]
26
29
33
35
交换
[ 19
12 ]
22
26
29
33
35
调整为堆
j=1
[ 12
19 ]
22
26
29
33
35
交换
[ 12 ]
19
22
26
29
33
35
调整为堆
9-13 如果只想在一个有n个元素的任意序列中得到其中最小的第k (k<<n) 个元素之前的部分排序序列,那么最好采用什么排序方法? 为什么? 例如有这样一个序列,{503,017,512,908,170,897,275,653,612,154,509,612*,677,765,094},要得到其第4个元素之前的部分有序序列,{017,094,154,170},用所选择的算法实现时,要执行多少次比较?
【解答】
一般来讲，当n比较大且要选的数据k << n时,采用堆排序方法中的调整算法FilterDown( )最好。但当n比较小时，采用锦标赛排序方法更好。
例如，对于序列{ 57,40,38,11,13,34,48,75,6,19,9,7 }，选最小的数据6，需形成初始堆，进行18次数据比较；选次小数据7时，需进行4次数据比较；再选数据9时，需进行6次数据比较；选数据11时，需进行4次数据比较。
但如果选用锦标赛排序，对于有n(n>0)个数据的序列，选最小数据需进行n-1次数据比较，以后每选一个数据，进行数据比较的次数，均需 (log2n( -1次。例如，同样12个数据，第一次选最小的数据6，需进行11次数据比较，以后选7、9、11时，都是 (log212( -1 = 2次数据比较。
9-14 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。
【解答】
(1) 希尔排序 { 512 275 275* 061 } 增量为2
{ 275* 061 512 275 } 增量为1
{ 061 275* 275 512 }
(2) 直接选择排序 { 275 275* 512 061 } i = 1
{ 061 275* 512 275 } i = 2
{ 061 275* 512 275 } i = 3
{ 061 275* 275 512 }
(3) 快速排序 { 512 275 275* }
{ 275* 275 512 }
(4) 堆排序 { 275 275* 061 170 } 已经是最大堆，交换275与170
{ 170 275* 061 275 } 对前3个调整
{ 275* 170 061 275 } 前3个最大堆，交换275*与061
{ 061 170 275* 275 } 对前2个调整
{ 170 061 275* 275 } 前2个最大堆，交换170与061
{ 061 170 275* 275 }
9-15 设有n个待排序元素存放在一个不带表头结点的单链表中,每个链表结点只存放一个元素,头指针为r。试设计一个算法,对其进行二路归并排序,要求不移动结点中的元素,只改各链结点中的指针,排序后r仍指示结果链表的第一个结点。（提示：先对待排序的单链表进行一次扫描,将它划分为若干有序的子链表,其表头指针存放在一个指针队列中。当队列不空时重复执行,从队列中退出两个有序子链表,对它们进行二路归并,结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列,则算法结束。这个有序子链表即为所求。)
【解答】
(1) 两路归并算法
template<Type> void staticlinkList<Type>,,merge ( int ha; int hb; int& hc ) {
//合并两个以ha和hb为表头指针的有序链表，结果链表的表头由hc返回
int pa,pb,pc;
if ( Vector[ha].data <= Vector[hb].data ) //确定结果链的表头
{ hc = ha; pa = Vector[ha].link; pb = hb; }
else { hc = hb; pb = Vector[hb].link; pa = ha; }
pc = hc; //结果链的链尾指针
while ( pa != 0 ) and ( pb != 0 ) //两两比较,小者进结果链
if ( Vector[pa].data <= Vector[pb].data )
{ Vector[pc].link = pa; pc = pa; pa = Vector[pa].link; }
else { Vector[pc].link = pb; pc = pb; pb = Vector[pb].link; }
if ( pa != 0 ) Vector[pc].link = pa; // pb链处理完,pa链链入结果链
else Vector[pc].link = pb; // pa链处理完,pb链链入结果链
}
(2) 归并排序主程序
template<class type> void staticlinkList<Type>,,merge_sort ( ) {
int r,s,t; Queue <int> Q;
if ( Vector[0].link == 0 ) return;
s = Vector[0].link; Q.Enqueue( s ); //链表第一个结点进队列
while ( 1 ) {
t = Vector[s].link; //结点t是结点s的下一个链中结点
while ( t != 0 && Vector[s].data <= Vector[t].data )
{ s = t; t = Vector[t].link; } //在链表中寻找一段有序链表
Vector[s].link = 0; s = t;
if ( t != 0 ) Q.EnQueue( s ); //存在一段有序链表，截取下来进队列
else break; //到链尾
}
while ( ! Q.IsEmpty( ) ) {
r = Q.getFront( ); Q.DlQueue( ); //从队列退出一个有序链表的表头r
if ( Q.IsEmpty( ) ) break; //队列空，表示排序处理完成，退出
s = Q.getFront( ); Q.DlQueue( ); //从队列再退出一个有序链表的表头s
merge( r,s,t ); Q.EnQueue( t ); //归并两个有序链表后结果链表进队列
}
Vector[0].link = r;
}
9-16 在什么条件下，MSD基数排序比LSD基数排序效率更高？
【解答】由于高位优先的MSD方法是递归的方法，就一般情况来说，不像低位优先的LSD方法那样直观自然，而且实现的效率较低。但如果待排序的排序码的大小只取决于高位的少数几位而与大多数低位无关时，采用MSD方法比LSD方法的效率要高。
9-17 在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域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 <class Type> void datalist<Type>,,count_sort ( ) {
//initList是待排序表，resultList是结果表
int i,j;
int *c = new datalist <Type>; // 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-18 如果某个文件经内排序得到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-19 假设文件有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-20 给出12个初始归并段，其长度分别为30,44,8,6,3,20,60,18,9,62,68,85。现要做4路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。
【解答】设初始归并段个数n = 12，外归并路数k = 4，计算(n-1) % (k-1) = 11 % 3 = 2 ≠ 0，必须补k-2-1 = 1个长度为0的空归并段，才能构造k路归并树。此时，归并树的内结点应有(n-1+1)/(k-1) = 12/3 = 4个。
WPL = (3+6+8)*3 + (9+18+20+30+44+60+62)*2 + (68+85)*1 = 51 + 486 + 153 = 690
#include <iostream.h>
const int DefaultSize = 100;
template <class Type> class dataList //数据表的前视声明
template <class Type> class Element { //数据表元素类的定义
friend class dataList <Type>;
private:
Type key; //排序码
field otherdata; //其它数据成员
public:
Type getKey ( ) { return key; } //取当前结点的排序码
void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为x
Element<Type>& operator = ( Element<Type>& x ) //结点x的值赋给this
{ key = x->key; otherdata = x->otherdata; }
int operator == ( Type& x ) { return key == x->key; } //判this与x相等
int operator <= ( Type& x ) { return key <= x->key; } //判this小于或等于x
int operator > ( Type& x ) { return key > x->key; } //判this大于x
int operator < ( Type& x ) { return key > x->key; } //判this小于x
}
template <class Type> class dataList {
//用顺序表来存储待排序的元素，这些元素的类型是Type
private:
Element <Type> * Vector; //存储待排序元素的向量
int MaxSize,CurrentSize; //最大元素个数与当前元素个数
int Partition ( const int low,const int high ) //用于快速排序的一次划分算法
public:
datalist ( int MaxSz = DefaultSize ), MaxSize ( Maxsz ),CurrentSize (0)
{ Vector = new Element <Type> [MaxSize]; } //构造函数
int length ( ) { return CurrentSize; }
Element<Type>& operator [ ] ( int i ) { return Vector[i]; }
void swap ( Element <Type>& x,Element <Type>& y ) //交换x,y
{ Element <Type> temp = x; x = y; y = temp; }
void Sort ( ); //排序
}
静态链表类定义
template <class Type> class staticlinkList; //静态链表类的前视声明
template <class Type> class Element { //静态链表元素类的定义
friend class staticlinkList<Type>;
private:
Type key; //排序码，其它信息略
int link; //结点的链接指针
public:
Type getKey ( ) { return key; } //取当前结点的排序码
void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为x
int getLink ( ) { return link; } //取当前结点的链接指针
void setLink ( const int ptr ) { link = ptr; } //将当前结点的链接指针置为ptr
}
template <class Type> class staticlinkList { //静态链表的类定义
private:
Element <Type> *Vector; //存储待排序元素的向量
int MaxSize,CurrentSize; //向量中最大元素个数和当前元素个数
public:
dstaticlinkList ( int Maxsz = DefaultSize ), MaxSize ( Maxsz ),CurrentSize (0)
{ Vector = new Element <Type> [Maxsz]; }
}
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) 二路归并排序
【解答】
(1) 直接插入排序
初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
i = 1
[ 12 ]
2
16
30
28
10
16*
20
6
18
1
i = 2
[ 2
12 ]
16
30
28
10
16*
20
6
18
1
i = 3
[ 2
12
16 ]
30
28
10
16*
20
6
18
1
i = 4
[ 2
12
16
30 ]
28
10
16*
20
6
18
2
i = 5
[ 2
12
16
28
30 ]
10
16*
20
6
18
5
i = 6
[ 2
10
12
16
28
30 ]
16*
20
6
18
3
i = 7
[ 2
10
12
16
16*
28
30 ]
20
6
18
3
i = 8
[ 2
10
12
16
16*
20
28
30 ]
6
18
3
i = 9
[ 2
6
10
12
16
16*
20
28
30 ]
18
8
[ 2
6
10
12
16
16*
18
20
28
30 ]
(2) 希尔排序(增量为5,2,1)
初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
12
2
16
30
28
10
16*
20
6
18
1+1+1+1+1 = 5
d = 5
10
2
16
6
18
12
16*
20
30
28
(1+1+2+1) + (1+1
d = 2
+1+1) = 9
10
2
16
6
16*
12
18
20
30
28
1+1+3+1+3+1+1
d = 1
+1+2 = 14
2
6
10
12
16
16*
18
20
28
30
希尔(shell)本人采取的增量序列为 (n/2(,((n/2(/2(,((n/2(/2(/2(,…,1。一般地，增量序列可采用(nα(,((nα(α(,((nα(α(α(,…,1。大量实验表明，取α=0.45454的增量序列比取其他的增量序列的优越性更显著。计算 (0.45454n( 的一个简单方法是用整数算术计算(5*n-1)/11。需要注意，当(< 1/2时，增量序列可能不以1结束，需要加以判断和调整。
(3) 起泡排序初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
i = 0
[ 12
2
16
30
28
10
16*
20
6
18 ]
9
i = 1
2
[ 12
6
16
30
28
10
16*
20
18 ]
8
i = 2
2
6
[ 12
10
16
30
28
16*
18
20 ]
7
i = 3
2
6
10
[ 12
16
16*
30
28
18
20 ]
6
i = 4
2
6
10
12
[ 16
16*
18
30
28
20 ]
5
i = 5
2
6
10
12
16
[ 16*
18
20
30
28 ]
4
i = 6
2
6
10
12
16
16*
[ 18
20
28
30 ]
3
2
6
10
12
16
16*
18
20
28
30
(4) 快速排序
Pivot
Pvtpos
0
1
2
3
4
5
6
7
8
9
排序码比较次数
12
0,1,2,3
[ 12
2
16
30
28
10
16*
20
6
18 ]
9
6
0,1
[ 6
2
10 ]
12
[ 28
16
16*
20
30
18 ]
2
28
4,5,6,7,8
[ 2 ]
6
[ 10 ]
12
[ 28
16
16*
20
30
18 ]
5
18
4,5,6
2
6
10
12
[ 18
16
16*
20 ]
28
[ 30 ]
3
16*
4
2
6
10
12
[ 16*
16 ]
18
[ 20 ]
28
30
1
2
6
10
12
16*
[ 16 ]
18
20
28
30
左子序列递归深度为1，右子序列递归深度为3。
(5) 直接选择排序初始排列
0
1
2
3
4
5
6
7
8
9
排序码比较次数
i = 0
[ 12
2
16
30
28
10
16*
20
6
18 ]
9
i = 1
2
[ 12
16
30
28
10
16*
20
6
18 ]
8
i = 2
2
6
[ 16
30
28
10
16*
20
12
18 ]
7
i = 3
2
6
10
[ 30
28
16
16*
20
12
18 ]
6
i = 4
2
6
10
12
[ 28
16
16*
20
30
18 ]
5
i = 5
2
6
10
12
16
[ 28
16*
20
30
18 ]
4
i = 6
2
6
10
12
16
16*
[ 28
20
30
18 ]
3
i = 7
2
6
10
12
16
16*
18
[ 20
30
28 ]
2
i = 8
2
6
10
12
16
16*
16
20
[ 30
28 ]
1
2
6
10
12
16
16*
16
20
28
[ 30 ]
(6)基数排序
收集
按最高位分配
收集
(7) 堆排序第一步，形成初始的最大堆 (略)，第二步，做堆排序。
初始排列，不是最大堆 形成初始最大堆 交换0# 与9# 对象
从0# 到8# 重新形成堆 交换0# 与8# 对象 从0# 到 7# 重新形成堆
交换0# 与7# 对象 从0# 到6# 重新形成堆 交换0# 与6# 对象
从0# 到5# 重新形成堆 交换0# 与5# 对象 从0# 到4# 重新形成堆
交换0# 与4# 对象 从0# 到3# 重新形成堆 交换0# 与3# 对象
从0# 到2# 重新形成堆 交换0# 与2# 对象 从0# 到1# 重新形成堆
交换0# 与1# 对象 从0# 到1# 重新形成堆，得到结果
(8) 二路归并排序
采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去，最后得到长度为n的归并结果。
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
9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把排序码最大的对象放到序列的最后，第二趟把排序码最小的对象放到序列的最前面。如此反复进行。
【解答1】
template <class Type> void dataList<Type>,,shaker_Sort ( ) {
//奇数趟对表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++;
}
}
【解答2】
template <class Type> void dataList<Type>,,shaker_Sort ( ) {
int low = 1,high = CurrentSize-1,i,j; int exchange;
while ( low < high ) { //当比较范围多于一个对象时排序
j = low; //记忆元素交换位置
for ( i = low; i < high; i++ ) //正向起泡
if ( Vector[i] > Vector[i+1] ) { //发生逆序
Swap ( Vector[i],Vector[i+1] ); //交换
j = i; //记忆右边最后发生交换的位置j
}
high = j; //比较范围上界缩小到j
for ( i = high; i > low; i-- ) //反向起泡
if ( Vector[i-1] > Vector[i] ) { //发生逆序
Swap ( Vector[i-1],Vector[i] ); //交换
j = i; //记忆左边最后发生交换的位置j
}
low = j; //比较范围下界缩小到j
}
}
9-5 如果待排序的排序码序列已经按非递减次序有序排列，试证明函数QuickSort( )的计算时间将下降到O(n2)。
【证明】
若待排序的n个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为T(n)。当以第一个对象作为基准对象时，应用一次划分算法Partition，通过n-1次排序码比较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有n-1个对象的非递减有序序列。对于这样的递归QuickSort( )算法，其时间代价为
T(n) = (n-1) + T(n-1)
= (n-1) + {( n-2) + T(n-2) }
= (n-1) + (n-2) + {(n-3) + T(n-3) }
= ……
= (n-1) + (n-2) + (n-3) + … + { 2 + T(1) }
= (n-1) + (n-2) + (n-3) + … + 2 + 1
= n(n-1)/2 = O(n2)
9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。
【解答】
由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两个子序列的长度相等，则所需栈的深度为
S(n) = 1 + S(n/2) =
= 1 + { 1 + S(n/4) } = 2 + S(n/4)
= 2 + { 1 + S(n/8) } = 3 + S(n/8)
= ……
= log2n + S(1) = log2n (假设1个对象的序列所用递归栈的深度为0)
如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递归栈中，再对较短的子序列进行排序，可用表示最坏情况的大O表示法表示。此时其递归栈的深度不一定正好是log2n，其最坏情况为O(log2n)。
9-7 在实现快速排序算法时，可先检查位于两端及中点的排序码，取三者之中的数值不是最大也不是最小的排序码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已排序的排序码序列，该算法的计算时间为O(nlog2n)。
【解答】参看教科书
9-8在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?
【解答】
可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。
9-9 试设计一个算法,使得在O(n)的时间内重排数组,将所有取负值的排序码排在所有取正值(非负值)的排序码之前。
【解答】
template<class Type> void reArrange ( dataList<Type>& L ) {
//数组元素类型Type只可能取int或float
int i = 0,j = L.length () – 1;
while ( i != j ) {
while ( L[i].getKey( ) < 0 ) i++;
while ( L[j].getKey( ) >= 0 ) j--;
swap ( L[i],L[j] );
i++; j--;
}
}
9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。
(1) 这种排序方法结束的条件是什么？
(2) 写出奇偶交换排序的算法。
(3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？
【解答】
(1) 设有一个布尔变量exchange，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描后是否有过交换。若exchange = 1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；若exchange = 0，表示刚才没有交换，可以结束排序。
(2) 奇偶排序的算法
template<Type> void dataList<Type>,,odd-evenSort ( ) {
int i,exchange;
do {
exchange = 0;
for ( i = 1; i < CurrentSize; i += 2 ) //扫描所有奇数项
if ( Vector[i] > Vector[i+1] ) { //相邻两项比较,发生逆序
exchange = 1; //作交换标记
swap ( Vector[i],Vector[i+1] ); //交换
}
for ( i = 0; i < CurrentSize; i += 2 ) //扫描所有偶数项
if ( Vector[i] > Vector[i+1] ) { //相邻两项比较,发生逆序
exchange = 1; //作交换标记
swap ( Vector[i],Vector[i+1] ); //交换
}
} while ( exchange != 0 );
}
(3) 设待排序对象序列中总共有n个对象。序列中各个对象的序号从0开始。则当所有待排序对象序列中的对象按排序码从大到小初始排列时，执行m = ((n+1)/2( 趟奇偶排序。当所有待排序对象序列中的对象按排序码从小到大初始排列时，执行1趟奇偶排序。
在一趟奇偶排序过程中，对所有奇数项扫描一遍，排序码比较 ((n-1)/2( 次；对所有偶数项扫描一遍，排序码比较 (n/2( 次。所以每趟奇偶排序两遍扫描的结果，排序码总比较次数为 ((n-1)/2( + (n/2( = n-1。
9-11 请编写一个算法，在基于单链表表示的待排序排序码序列上进行简单选择排序。
【解答】
采用静态单链表作为存储表示。用Vector[0]作为表头结点，各待排序数据对象从Vector[1]开始存放。算法的思想是每趟在原始链表中摘下排序码最大的结点(几个排序码相等时为最前面的结点)，把它插入到结果链表的最前端。由于在原始链表中摘下的排序码越来越小，在结果链表前端插入的排序码也越来越小，最后形成的结果链表中的结点将按排序码非递减的顺序有序链接。
Template<class Type> void staticlinkList<Type>,,selectSort ( ) {
int h = Vector[0].link,p,q,r,s;
Vector[0].link = 0;
while ( h != 0 ) { //原始链表未扫描完
p = s = h; q = r = 0;
while ( p != 0 ) { //扫描原始链表,寻找排序码最大的结点s
if ( Vector[p].data > Vector[s].data ) //记忆当前找到的排序码最大结点
{ s = p; r = q; }
q = p; p = Vector[p].link;
}
if ( s == h ) h = Vector[h]; //排序码最大的结点是原始链表前端结点,摘下
else Vector[r].link = Vector[s].link; //排序码最大的结点是原始链表表中结点,摘下
Vector[s].link = Vector[0].link; //结点s插入到结果链表的前端
Vector[0].link = s;
}
}
9-12 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。
(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
【解答】 为节省篇幅，将用数组方式给出形成初始堆和进行堆排序的变化结果。阴影部分表示参与比较的排序码。请读者按照完全二叉树的顺序存储表示画出堆的树形表示。
(1) 按字母顺序排序
形成初始堆（按最大堆）
0
1
2
3
4
5
6
7
8
9
10
Tim
Dot
Eva
Rom
Kim
Guy
Ann
Jim
Kay
Ron
Jan
i=4
Tim
Dot
Eva
Rom
[ Ron
Guy
Ann
Jim
Kay
Kim
Jan ]
i=3
Tim
Dot
Eva
[ Rom
Ron
Guy
Ann
Jim
Kay
Kim
Jan ]
i=2
Tim
Dot
[ Guy
Rom
Ron
Eva
Ann
Jim
Kay
Kim
Jan ]
i=1
Tim
[ Ron
Guy
Rom
Kim
Eva
Ann
Jim
Kay
Dot
Jan ]
i=0
[ Tim
Ron
Guy
Rom
Kim
Eva
Ann
Jim
Kay
Dot
Jan ]
堆排序
0
1
2
3
4
5
6
7
8
9
10
j=10
[ Jan
Ron
Guy
Rom
Kim
Eva
Ann
Jim
Kay
Dot
Tim ]
交换
[ Ron
Rom
Guy
Kay
Kim
Eva
Ann
Jim
Jan
Dot ]
Tim
调整
j=9
[ Dot
Rom
Guy
Kay
Kim
Eva
Ann
Jim
Jan
Ron ]
Tim
交换
[ Rom
Kim
Guy
Kay
Dot
Eva
Ann
Jim
Jan ]
Ron
Tim
调整
j=8
[ Jan
Kim
Guy
Kay
Dot
Eva
Ann
Jim
Rom ]
Ron
Tim
交换
[ Kim
Kay
Guy
Jim
Dot
Eva
Ann
Jan ]
Rom
Ron
Tim
调整
j=7
[ Jan
Kay
Guy
Jim
Dot
Eva
Ann
Kim ]
Rom
Ron
Tim
交换
[ Kay
Jim
Guy
Jan
Dot
Eva
Ann ]
Kim
Rom
Ron
Tim
调整
j=6
[ Ann
Jim
Guy
Jan
Dot
Eva
Kay ]
Kim
Rom
Ron
Tim
交换
[ Jim
Jan
Guy
Ann
Dot
Eva ]
Kay
Kim
Rom
Ron
Tim
调整
j=5
[ Eva
Jan
Guy
Ann
Dot
Jim ]
Kay
Kim
Rom
Ron
Tim
交换
[ Jan
Eva
Guy
Ann
Dot ]
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=4
[ Dot
Eva
Guy
Ann
Jan ]
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Guy
Eva
Dot
Ann ]
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=3
[ Ann
Eva
Dot
Guy ]
Jan
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Eva
Ann
Dot ]
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=2
[ Dot
Ann
Eva ]
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Dot
Ann ]
Eva
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
j=1
[ Dot
Ann ]
Eva
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
交换
[ Ann ]
Dot
Eva
Guy
Jan
Jim
Kay
Kim
Rom
Ron
Tim
调整
(2) 按数值递增顺序排序
形成初始堆 (按最大堆)
0
1
2
3
4
5
6
26
33
35
29
19
12
22
i=2
26
33
[ 35
29
19
12
22 ]
i=0
26
[ 33
35
29
19
12
22 ]
i=1
[ 35
33
26
29
19
12
22 ]
堆排序
0
1
2
3
4
5
6
j=6
[ 22
33
26
29
19
12
35 ]
交换
[ 33
29
26
22
19
12 ]
35
调整为堆
j=5
[ 12
29
26
22
19
33 ]
35
交换
[ 29
22
26
12
19 ]
33
35
调整为堆
j=4
[ 19
22
26
12
29 ]
33
35
交换
[ 26
22
19
12 ]
29
33
35
调整为堆
j=3
[ 12
22
19
26 ]
29
33
35
交换
[ 22
12
19 ]
26
29
33
35
调整为堆
j=2
[ 19
12
22 ]
26
29
33
35
交换
[ 19
12 ]
22
26
29
33
35
调整为堆
j=1
[ 12
19 ]
22
26
29
33
35
交换
[ 12 ]
19
22
26
29
33
35
调整为堆
(3) 同样7个数字，换一个初始排列，再按数值的递增顺序排序形成初始堆 (按最大堆)
0
1
2
3
4
5
6
12
19
33
26
29
35
22
i=2
12
19
[ 35
26
29
33
22 ]
i=0
12
[ 29
35
26
19
33
22 ]
i=1
[ 35
29
33
26
19
12
22 ]
堆排序
0
1
2
3
4
5
6
j=6
[ 22
29
33
26
19
12
35 ]
交换
[ 33
29
22
26
19
12 ]
35
调整为堆
j=5
[ 12
29
22
26
19
33 ]
35
交换
[ 29
26
22
12
19 ]
33
35
调整为堆
j=4
[ 19
26
22
12
29 ]
33
35
交换
[ 26
19
22
12 ]
29
33
35
调整为堆
j=3
[ 12
19
22
26 ]
29
33
35
交换
[ 22
19
12 ]
26
29
33
35
调整为堆
j=2
[ 12
19
22 ]
26
29
33
35
交换
[ 19
12 ]
22
26
29
33
35
调整为堆
j=1
[ 12
19 ]
22
26
29
33
35
交换
[ 12 ]
19
22
26
29
33
35
调整为堆
9-13 如果只想在一个有n个元素的任意序列中得到其中最小的第k (k<<n) 个元素之前的部分排序序列,那么最好采用什么排序方法? 为什么? 例如有这样一个序列,{503,017,512,908,170,897,275,653,612,154,509,612*,677,765,094},要得到其第4个元素之前的部分有序序列,{017,094,154,170},用所选择的算法实现时,要执行多少次比较?
【解答】
一般来讲，当n比较大且要选的数据k << n时,采用堆排序方法中的调整算法FilterDown( )最好。但当n比较小时，采用锦标赛排序方法更好。
例如，对于序列{ 57,40,38,11,13,34,48,75,6,19,9,7 }，选最小的数据6，需形成初始堆，进行18次数据比较；选次小数据7时，需进行4次数据比较；再选数据9时，需进行6次数据比较；选数据11时，需进行4次数据比较。
但如果选用锦标赛排序，对于有n(n>0)个数据的序列，选最小数据需进行n-1次数据比较，以后每选一个数据，进行数据比较的次数，均需 (log2n( -1次。例如，同样12个数据，第一次选最小的数据6，需进行11次数据比较，以后选7、9、11时，都是 (log212( -1 = 2次数据比较。
9-14 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。
【解答】
(1) 希尔排序 { 512 275 275* 061 } 增量为2
{ 275* 061 512 275 } 增量为1
{ 061 275* 275 512 }
(2) 直接选择排序 { 275 275* 512 061 } i = 1
{ 061 275* 512 275 } i = 2
{ 061 275* 512 275 } i = 3
{ 061 275* 275 512 }
(3) 快速排序 { 512 275 275* }
{ 275* 275 512 }
(4) 堆排序 { 275 275* 061 170 } 已经是最大堆，交换275与170
{ 170 275* 061 275 } 对前3个调整
{ 275* 170 061 275 } 前3个最大堆，交换275*与061
{ 061 170 275* 275 } 对前2个调整
{ 170 061 275* 275 } 前2个最大堆，交换170与061
{ 061 170 275* 275 }
9-15 设有n个待排序元素存放在一个不带表头结点的单链表中,每个链表结点只存放一个元素,头指针为r。试设计一个算法,对其进行二路归并排序,要求不移动结点中的元素,只改各链结点中的指针,排序后r仍指示结果链表的第一个结点。（提示：先对待排序的单链表进行一次扫描,将它划分为若干有序的子链表,其表头指针存放在一个指针队列中。当队列不空时重复执行,从队列中退出两个有序子链表,对它们进行二路归并,结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列,则算法结束。这个有序子链表即为所求。)
【解答】
(1) 两路归并算法
template<Type> void staticlinkList<Type>,,merge ( int ha; int hb; int& hc ) {
//合并两个以ha和hb为表头指针的有序链表，结果链表的表头由hc返回
int pa,pb,pc;
if ( Vector[ha].data <= Vector[hb].data ) //确定结果链的表头
{ hc = ha; pa = Vector[ha].link; pb = hb; }
else { hc = hb; pb = Vector[hb].link; pa = ha; }
pc = hc; //结果链的链尾指针
while ( pa != 0 ) and ( pb != 0 ) //两两比较,小者进结果链
if ( Vector[pa].data <= Vector[pb].data )
{ Vector[pc].link = pa; pc = pa; pa = Vector[pa].link; }
else { Vector[pc].link = pb; pc = pb; pb = Vector[pb].link; }
if ( pa != 0 ) Vector[pc].link = pa; // pb链处理完,pa链链入结果链
else Vector[pc].link = pb; // pa链处理完,pb链链入结果链
}
(2) 归并排序主程序
template<class type> void staticlinkList<Type>,,merge_sort ( ) {
int r,s,t; Queue <int> Q;
if ( Vector[0].link == 0 ) return;
s = Vector[0].link; Q.Enqueue( s ); //链表第一个结点进队列
while ( 1 ) {
t = Vector[s].link; //结点t是结点s的下一个链中结点
while ( t != 0 && Vector[s].data <= Vector[t].data )
{ s = t; t = Vector[t].link; } //在链表中寻找一段有序链表
Vector[s].link = 0; s = t;
if ( t != 0 ) Q.EnQueue( s ); //存在一段有序链表，截取下来进队列
else break; //到链尾
}
while ( ! Q.IsEmpty( ) ) {
r = Q.getFront( ); Q.DlQueue( ); //从队列退出一个有序链表的表头r
if ( Q.IsEmpty( ) ) break; //队列空，表示排序处理完成，退出
s = Q.getFront( ); Q.DlQueue( ); //从队列再退出一个有序链表的表头s
merge( r,s,t ); Q.EnQueue( t ); //归并两个有序链表后结果链表进队列
}
Vector[0].link = r;
}
9-16 在什么条件下，MSD基数排序比LSD基数排序效率更高？
【解答】由于高位优先的MSD方法是递归的方法，就一般情况来说，不像低位优先的LSD方法那样直观自然，而且实现的效率较低。但如果待排序的排序码的大小只取决于高位的少数几位而与大多数低位无关时，采用MSD方法比LSD方法的效率要高。
9-17 在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域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 <class Type> void datalist<Type>,,count_sort ( ) {
//initList是待排序表，resultList是结果表
int i,j;
int *c = new datalist <Type>; // 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-18 如果某个文件经内排序得到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-19 假设文件有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-20 给出12个初始归并段，其长度分别为30,44,8,6,3,20,60,18,9,62,68,85。现要做4路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。
【解答】设初始归并段个数n = 12，外归并路数k = 4，计算(n-1) % (k-1) = 11 % 3 = 2 ≠ 0，必须补k-2-1 = 1个长度为0的空归并段，才能构造k路归并树。此时，归并树的内结点应有(n-1+1)/(k-1) = 12/3 = 4个。
WPL = (3+6+8)*3 + (9+18+20+30+44+60+62)*2 + (68+85)*1 = 51 + 486 + 153 = 690
