? 概述
? 插入排序
? 交换排序
? 选择排序
? 归并排序
? 基数排序
? 外排序
概述
? 排序, 将一组杂乱无章的数据按一定的规律
顺次排列起来 。
? 数据表 (datalist),它是待排序数据对象的有限
集合 。
? 排序码 (key),通常数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可
用来区分对象,作为排序依据 。 该域即为 排
序码 。 每个数据表用哪个属性域作为排序码,
要视具体的应用需要而定 。
? 排序算法的稳定性,如果在对象序列中有两
个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],且
在排序之前,对象 r[i]排在 r[j]前面。如果在排
序之后,对象 r[i]仍在对象 r[j]的前面,则称这
个排序方法是稳定的,否则称这个排序方法
是不稳定的。
? 内排序与外排序, 内排序是指在排序期间
数据对象全部存放在内存的排序；外排序
是指在排序期间全部对象个数太多，不能
同时存放在内存，必须根据排序过程的要
求，不断在内、外存之间移动的排序。
? 排序的时间开销, 排序的时间开销是衡量
算法好坏的最重要的标志。 排序的时间开销
可用算法执行中的 数据比较次数 与 数据移动
次数 来衡量 。
? 算法运行时间代价的大略估算一般都 按平均
情况 进行估算。对于那些 受对象排序码序列
初始排列及对象个数影响较大的, 需要 按最
好情况 和 最坏情况 进行估算 。
? 算法执行时所需的附加存储, 评价算法好
坏的另一标准。
待排序数据表的类定义
#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:
Element ( ), key(0),otherdata(NULL) { }
Type getKey ( ) { return key; } //提取排序码
void setKey ( const Type x ) { key = x; } //修改
Element<Type> & operator = //赋值
( Element<Type>& x ) { key = x->key;
otherdata = x->otherdata; }
int operator == (Element<Type>& x )
{ return key == x->key; } //判 this == x
int operator <= (Element<Type>& x )
{ return key <= x->key; } //判 this ? x
int operator < (Element<Type>& x )
{ return key < x->key; } //判 this < x
int operator > (Element<Type>& x )
{ return key > x->key; } //判 this > x
}
template <class Type> class dataList {
private:
Element <Type> * Vector; //存储向量
int MaxSize,CurrentSize; //最大与当前个数
public:
datalist ( int MaxSz = DefaultSize ),
MaxSize ( Maxsz ),CurrentSize (0)
{ Vector = new Element <Type> [MaxSz]; }
void sort ( ); //排序
void swap ( Element <Type> & x,//对换
Element <Type> & y ) {
Element<Type> temp = x;
x = y; y = temp;
}
}
插入排序 (Insert Sorting)
? 基本思想是, 当插入第 i (i ? 1) 个对象时,前
面的 V[0],V[1],…,V[i-1]已经排好序。这时,
用 V[i]的排序码与 V[i-1],V[i-2],… 的排序码
顺序进行比较,找到插入位臵即将 V[i]插入,
原来位臵上的对象向后顺移。
基本方法是, 每步将一个待排序的对象,按
其排序码大小,插入到前面已经排好序的一
组对象的适当位臵上,直到对象全部插入为止 。
直接插入排序 (Insert Sort)
各
趟
排
序
结
果
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 49 25* 16 08 25i = 1
0 1 2 3 4 5 temp
21 25 49 25* 16 08 49i = 2
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 16 08i = 4
0 1 2 3 4 5 temp
21 25 4925*16 08i = 5
i = 3 25*
16
08
16
4916
16
21 25 4925*1608
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 08
i = 4 时的排序过程
0 1 2 3 4 5 temp
21 25 4925*
完成
16
08 16
i = 4
j = 3
i = 4
j = 2
25
25*16
16
21 25 4925* 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 4925* 08
0 1 2 3 4 5 temp
21 25 4925*
16
08 16
16
25
21
i = 4
j = 1
i = 4
j = 0
i = 4
j = -1 16
直接插入排序的算法
template <class Type>
void dataList <Type>,,InsertSort ( ) {
//按排序码 Key非递减顺序对表进行排序
Element<Type> temp; int i,j;
for ( i = 1; i < CurrentSize; i++ ) {
temp = Vector[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < Vector[j-1] )
Vector[j] = Vector[j-1];
else break;
Vector[j] = temp;
算法分析
? 设待排序对象个数为 currentSize = n,则该算
法的主程序执行 n-1趟。
? 排序码比较次数和对象移动次数与对象排序
码的初始排列有关。
? 最好情况下,排序前对象已按排序码从小到
大有序,每趟只需与前面有序对象序列的最
后一个对象比较 1次,移动 2次对象,总的排序
码比较次数为 n-1,对象移动次数 为 2(n-1)。
}
}
? 最坏情况下,第 i 趟时第 i 个对象必须与前面
i 个对象都做排序码比较,并且每做 1次比较
就要做 1次数据移动 。 则总 排序码比较次数
KCN和 对象移动次数 RMN分别为
? 在平均情况下的 排序码比较次数 和 对象移动
次数 约为 n2/4。因此，直接插入排序的时间
复杂度为 o(n2)。
? 直接插入排序是一种 稳定 的排序方法。
?
?
?
?
?
?
??????
????
1
1
1
1
22142
221
n
i
n
i
nnniRM N
nnniKC N
//))(()(
,//)(
2
2
折半插入排序 (Binary Insertsort)
? 基本思想是, 设在顺序表中有一 个对象序列
V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,
V[i-1]是已经排好序的对象。在插入 V[i]时,
利用折半搜索法寻找 V[i]的插入位臵。
折半插入排序的算法
template <class Type>
void dataList<Type>,,BineryInsSort ( ) {
Element<Type> temp; int Left,Right;
for ( int i = 1; i < CurrentSize; i++) {
Left = 0; Right = i-1; temp = Vector[i];
while ( Left <= Right ) {
int middle = ( Left + Right )/2;
if ( temp < Vector[middle] )
Right = middle - 1;
else Left = middle + 1;
}
for ( int k = i-1; k >= Left; k-- )
Vector[k+1] = Vector[k];
Vector[Left] = temp;
}
算法分析
? 折半搜索比顺序搜索查找快,所以折半插入
排序就 平均性能 来说比直接插入排序要快。
? 它所需的 排序码比较次数与待排序对象序
列的初始排列无关,仅依赖于对象个数。 在
插入第 i 个对象时,需要经过 ?log2i?+1 次排
序码比较,才能确定它应插入的位臵。 因此,
将 n 个对象 (为推导方便,设为 n=2k )用折半
插入排序所进行的排序码比较次数为：
? 折半插入排序是一个 稳定 的排序方法。
? ?? ??
?
?
???
1
1
22 l o g1l o g
n
i
nni
? 当 n 较大 时,总排序码比较次数比直接插入
排序的最坏情况要好得多,但比其最好情况
要差 。
? 在对象的初始排列已经按排序码排好序或
接近有序时,直接插入排序比折半插入排序
执行的排序码比较次数要少 。 折半插入排
序的对象移动次数与直接插入排序相同,依
赖于对象的初始排列 。
链表插入排序
? 基本思想是：在每个对象的结点中增加一个
链接指针 数据成员 link。
? 对于数组中的一组对象 V[1],…,V[n],若
V[1],…,V[i-1]已经通过指针 link,按其排序
码从小到大链接起来。现要插入 V[i],i = 2,
3,…,n,则必须在前面 i-1个链接起来的对象
当中,循链检测比较,找到 V[i] 应插入的位臵,
把 V[i]链入,并修改相应链接指针。从而得到
V[1],…,V[i]的一个通过指针排好的链表。
? 如此重复执行，直到把 V[n]也插入到链表中
排好序为止。
? 25 49 25* 16
08
0 1 2 3 4 5 6
i = 2
i = 3
21
初始
current pre i
current pre i
pre current i
i = 4
? 25 49 25* 16
08
0 1 2 3 4 5 6
i = 5
i = 6
21
pre current i
结果
pre current i
用于链表排序的静态链表的类定义
template <class Type> class staticlinklist;
template <class Type> class Element {
private:
Type key; //结点的排序码
int link; //结点的链接指针
public:
Element ( ), key(0),link (NULL) { }
Type getKey ( ) { return key; }
void setKey ( const Type x ) { key = x; }
int getLink ( ) { return link; }
void setLink ( const int l ) { link = l; }
}
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]; }
}
链表插入排序的算法
template <class Type>
int staticlinklis<Type>,,LinkedInsSort ( ) {
Vector[0].key = MaxNum;
Vector[0].link = 1; Vector[1].link = 0;
//元素 V[0]与 V[1]形成循环链表
for ( int i = 2; i <= CurrentSize; i++ ) {
int current = Vector[0].link; //检测指针
int pre = 0; //检测指针的前驱指针
while ( Vector[current].key <=
Vector[i].key ) { //找插入位置
pre = current; //pre跟上,current向 前走
? 使用链表插入排序,每插入一个对象,最大排
序码比较次数等于链表中已排好序的对象个
数,最小排序码比较次数为 1。故总的 排序码
比较次数最小 为 n-1,最大 为
current = Vector[current].link;
}
Vector[i].link = current; Vector[pre].link = i;
//在 pre与 current之间链入
}
}
2
)1(1
1
????
?
nnin
i
? 用链表插入排序时,对象移动次数为 0。但为
了实现链表插入,在每个对象中增加了一个
链域 link,并使用了 Vector[0]作为链表的表
头结点,用了 n 个附加域 和 一个附加对象 。
? 算法在 Vector[pre].key == Vector[i].key时,
将 Vector[i]插在 Vector[pre]的后面,所以,链
表插入排序方法是 稳定 的。
希尔排序 (Shell Sort)
? 希尔排序方法又称为缩小增量排序。该方法
的基本思想是, 设待排序对象序列有 n 个对
象,首先取一个整数 gap < n 作为间隔,将全
部对象分为 gap 个子序列,所有 距离为 gap
的对象放在 同一个子序列 中,在每一个子序
列中分别施行直接插入排序。然后缩小间隔
gap,例如取 gap = ?gap/2?，重复上述的子序
列划分和排序工作。直到最后取 gap == 1,
将所有对象放在同一个序列中排序为止。
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*
i = 1
08
49
Gap = 3
25 16
4925 16
08
49 25*
0821
2521 25* 16
21 25 4925*16 08
0 1 2 3 4 5
21
i = 2
08
49
Gap = 2
25
16
4916 25*
0821 25
4925*
08 16 21 25* 25
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
Gap = 1
2516 4925*
? 开始时 gap 的值较大,子序列中的对象较少,
排序速度较快 ; 随着排序进展,gap 值逐渐
变小,子序列中对象个数逐渐变多,由于前
面工作的基础,大多数对象已基本有序,所
以排序速度仍然很快。
希尔排序的算法
template <class Type>
void dataList<Type>,,ShellSort ( ) {
Element<Type> temp;
int gap = CurrentSize / 2; //gap是子序列间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < CurrentSize; i++) {
temp = Vector[i]; //直接插入排序
for ( int j = i; j >= gap; j -= gap )
if ( temp < Vector[j-gap] )
Vector[j] = Vector[j-gap];
else break;
Vector[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
? Gap的取法有多种。最初 shell 提出取 gap =
?n/2?,gap = ?gap/2?,直到 gap = 1。 knuth
提出取 gap = ?gap/3?+1。还有人提出都取
奇数为好，也有人提出各 gap 互质为好。
? 对特定的待排序对象序列，可以准确地估算
排序码的比较次数和对象移动次数 。
? 想要弄清排序码比较次数和对象移动次数
与增量选择之间的依赖关系, 并给出完整
的数学分析, 还没有人能够做到 。
? Knuth利用大量实验统计资料得出, 当 n
很大时, 排序码平均比较次数和对象平均
移动次数大约在 n1.25到 1.6n1.25的范围内 。
这是在利用直接插入排序作为子序列排序
方法的情况下得到的 。
交换排序 ( Exchange Sort )
? 基本方法是：设待排序对象序列中的对象个
数为 n。最多作 n-1 趟,i = 1,2,?,n-1 。
在第 i 趟中 从后向前, j = n-1,n-2,?,i，顺
次两两 比较 V[j-1].key和 V[j].key。 如果发生
逆序，则交换 V[j-1]和 V[j]。
基本思想是 两两比较待排序对象的排序码,如
果发生逆序 (即排列顺序与排序后的次序正好相
反 )，则交换之 。直到所有对象都排好序为止。
起泡排序 (Bubble Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
2516
25 16
08
49
Exchang=108
25*4921
Exchang=1
i = 2
i = 3
08 16 Exchang=125*2521
25*
0 1 2 3 4 5
i = 4 4916
Exchang=008
2521
起泡排序的算法
template <class Type>
void dataList<Type>,,BubbleSort ( ) {
int pass = 1; int exchange = 1;
while ( pass < CurrentSize && exchange ){
exchange = 0; //标志置为 0,假定未交换
for ( int j = CurrentSize-1; j >= pass; j-- )
if ( Vector[j-1] > Vector[j] ) { //逆序
Swap ( Vector[j-1],Vector[j] ); //交换
exchange = 1; //标志置为 1,有交换
}
pass++;
}
}
? 第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-1]
进行排序,结果 将该序列中排序码最小的对
象交换到序列的第一个位臵 (i-1),其它对象
也都向排序的最终位臵移动 。 在个别情形,
对象可能在排序中途向相反的方向移动 。
? 最多做 n-1趟起泡 就能把所有对象排好序 。
? 在对象的 初始排列已经按排序码从小到大排
好序 时,此算法 只执行一趟起泡,做 n-1次排
序码比较,不移动对象 。 这是最好的情形 。
? 最坏的情形是算法 执行 n-1趟起泡,第 i趟 (1?
i? n) 做 n- i 次排序码比较,执行 n-i 次对象
交换 。 这样在最坏情形下总的 排序码比较次
数 KCN和 对象移动次数 RMN为：
?
?
?
?
?
?
????
????
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninRM N
nninKCN
)()(
)()(
快速排序 (Quick Sort)
? 基本思想是任取 待排序对象序列中的某个对象
(例如取第一个对象 ) 作为基准,按照该对象的
排序码大小,将整个对象序列划分为左右两
个子序列,
? 起泡排序需要一个附加对象以实现对象值的
对换。
? 起泡排序是一个 稳定 的排序方法。
? 左侧子序列中所有对象的排序码都小于
或等于基准对象的排序码
? 右侧子序列中所有对象的排序码都大于
基准对象的排序码
? 基准对象则排在这两个子序列中间 (这也是
该对象最终应安放的位臵 )。
? 然后分别对这两个子序列重复施行上述方
法，直到所有的对象都排在相应位臵上为
止。
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
算法描述
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25*16
2516
08
49
pivot
08
25 4921i = 2
i = 3
08 16 2525*21
pivotpivot
pivot
21 25 49 25* 16 08
0 1 2 3 4 5
25*
i = 1
划分
2516
2516
08
49
pivotpos
08
25* 49
08 16 25* 2521
pivotpos
21
比较 4次
交换 25,16
i
i
pivotpos
21
比较 1次
交换 49,08
49
low pivotpos
交换 21,08
快速排序的算法
template <class Type>
void dataList<Type>,,QuickSort ( const int left,
const int right ) {
//在序列 left?right 中递归地进行快速排序
if ( left < right) {
int pivotpos = Partition ( left,right ); //划分
//对左序列同样处理
QuickSort ( left,pivotpos-1);
//对右序列同样处理
QuickSort ( pivotpos+1,right );
}
}
template <class Type> int dataList<Type>,,
Partition ( const int low,const int high ) {
int pivotpos = low; //基准位置
Element<Type> pivot = Vector[low];
for ( int i = low+1; i <= high; i++ )
if ( Vector[i] < pivot ) {
pivotpos++;
if ( pivotpos != i )
Swap ( Vector[pivotpos],Vector[i] );
} //小于基准对象的交换到区间的左侧去
Swap ( Vector[low],Vector[pivotpos] );
return pivotpos;
}
? 算法 quicksort是一个递归的算法,其递归树
如图所示。
? 算法 partition利用 序列第一个对象作为基准,
将整个序列划分为左右两个子序列 。算法
中执行了一个循环,只要是排序码小于基准
对象排序码的对象都移到序列左侧,最后基
准对象安放到位,函数返回其位臵。
21
25*
25
49
08
16
算法分析
? 从快速排序算法的递归树可知,快速排序的
趟数取决于递归树的高度 。
? 如果每次划分对一个对象定位后,该对象的
左侧子序列与右侧子序列的长度相同,则下
一步将是对两个长度减半的子序列进行排序,
这是最理想的情况。
? 在 n个元素的序列中,对一个对象定位所需
时间为 O(n)。 若设 t (n) 是对 n 个元素的序
列进行排序所需的时间,而且每次对一个对
象正确定位后,正好把序列划分为长度相等
的两个子序列,此时,总的计算时间为：
T(n) ? cn + 2T(n/2 ) // c 是一个常数
? cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)
? 2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8)
………
? cn log2n + nT(1) = O(n log2n )
? 可以证明,函数 quicksort的平均计算时间也
是 O(nlog2n)。 实验结果表明, 就平均计算时
间而言,快速排序是所有内排序方法中最好
的一个 。
? 快速排序是递归的, 需要有一个栈存放每层
递归调用时的指针和参数 。
? 最大递归调用层次数与递归树的高度一致,
理想情况为 ?log2(n+1)? 。 因此, 要求存储
开销为 O(log2n)。
? 在最坏的情况,即 待排序对象序列已经按其
排序码从小到大排好序 的情况下,其 递归树
成为单支树,每次划分只得到一个比上一次
少一个对象的子序列 。 必须经过 n-1 趟才
能把所有对象定位,而且 第 i 趟需要经过 n-
i 次排序码比较 才能找到第 i 个对象的安放
位臵, 总的排序码比较次数将达到
212
1 21
1
nnninn
i
?????
?
?
)()(
用第一个对象作为基准对象
快速排序退化的例子
08 16 21 25 25* 49 08
0 1 2 3 4 5 pivot
初始
16 21 25 25* 4908 16
21 25 25* 49 2108 16
2525 25* 4908 16 21
25* 49 25*08 16 21 25
4908 16 21 25 25*
i = 1
i = 2
i = 3
i = 4
i = 5
用居中排序码对象作为基准对象
08 16 21 25 25* 49
0 1 2 3 4 5 pivot
21初始
08 16 21 25 25* 49 08 25*
08 16 21 25 25* 49
i = 1
i = 2
? 其 排序速度退化到简单排序的水平,比直接插
入排序还慢 。占用附加存储 (栈 )将达到 O(n)。
? 改进办法, 取每个待排序对象序列的 第一个对
象, 最后一个对象 和 位臵接近正中的 3 个对
象，取其排序码居中者作为基准对象。
? 快速排序是一种 不稳定 的排序方法 。
? 对于 n 较大的平均情况而言,快速排序是
,快速, 的,但是当 n 很小时,这种排序方
法往往比其它简单排序方法还要慢 。
Type mid ( Type a,Type b,Type c ) {
Type first = a,second; //first记录最小
if ( b < first ) { second = first; first = b; }
else second = b; //second记录次小
if ( c < first ) { second = first; first = c; }
else if ( c < second ) second = c;
return second;
}
基本思想是, 每一趟 (例如第 i 趟,i = 0,1,…,
n-2) 在后面 n-i 个待排序对象中选出排序码
最小的对象,作为有序对象序列的第 i 个对象。
待到第 n-2 趟作完,待排序对象只剩下 1个,就
不用再选了。
选择排序
② 若它不是这组对象中的第一个对象,则
将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码
的对象 。 在剩下的对象 V[i+1]～ V[n-1]中
重复执行第 ①, ② 步,直到剩余对象只有
一个为止 。
? 直接选择排序是一种简单的排序方法,它的
基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最
小排序码的对象；
直接选择排序 (Select Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 0
49
25 16
25 16
08
49
08
25*49 21i = 1
i = 2
08 16
25* 25 21
初始
最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
4925*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3
08 16 2521
最小者 25*
无交换
最小者 25
无交换252116
08
各趟排序后的结果
直接选择排序的算法
template <class Type>
void dataList <Type>,,SelectSort ( ) {
for ( int i = 0; i < CurrentSize-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < CurrentSize; j++)
if ( Vector[j] < Vector[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位置
Swap ( Vector[i],Vector[k] );
}
}
0 1 2 3 4 5
49
1608 25*49 21
08 25*
25
21
i =1时选择排序的过程
i k j
4925
08 25* 16 21
i k j
49 ? 25
25* ? 25
1625
i k j 16 < 25
4925
08 25* 16 21
0 1 2 3 4 5
i k j 21 ? 16
k 指示当前序列中最小者
? 直接选择排序的 排序码比较次数 KCN 与对
象的初始排列无关。设整个待排序对象序列
有 n 个对象,则第 i 趟选择具有最小排序码
对象所需的比较次数 总是 n-i-1次 。总的排
序码比较次数为
?
?
?
????? 2
0 2
11n
i
nninKC N )()(
? 对象的移动次数与对象序列的初始排列有
关 。当这组对象的初始状态是按其排序码
从小到大有序的时候,对象的移动次数
RMN = 0，达到最少。
? 最坏情况是每一趟都要进行交换,总的对
象移动次数 为 RMN = 3(n-1)。
? 直接选择排序是一种 不稳定 的排序方法。
锦标赛排序 (Tournament Tree Sort)
? 它的思想与体育比赛时的淘汰赛类似。首
先取得 n 个对象的排序码,进行 两两比较,
得到 ?n/2?个 比较的优胜者 (排序码小者 ),
作为第一步比较的结果保留下来。然后对
这 ?n/2?个对象再进行排序码的两两比
较,…,如此重复,直到选出一个排序码最小
的对象为止。
? 在图例中,最下面是对象排列的初始状态,
相当于一棵满二叉树的叶结点,它存放的
是 所有参加排序的对象的排序码 。
? 如果 n 不是 2 的 k 次幂, 则让叶结点数补足
到满足 2k-1 < n ? 2k的 2k个 。 叶结点上面一
层的非叶结点是叶结点排序码两两比较的结
果 。 最顶层是树的根 。
08
Winner
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
胜者树的概念
? 每次两两比较的结果是把 排序码小者作为
优胜者上升到双亲结点, 称这种比赛树为
胜者树 。
? 位于 最底层的叶结点 叫做胜者树的 外结点,
非叶结点 称为胜者树的 内结点 。 每个结点
除了存放对象的排序码 data 外, 还存放了
此对象是否要参选的标志 Active 和此对象
在满二叉树中的序号 index。
? 胜者树最顶层是树的 根,表示 最后选择出
来的具有最小排序码的对象 。
08
Winner (胜者 )
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
形成初始胜者树（最小排序码上升到根）
a[0]
排序码比较次数, 6
VS,VS,VS.
VS.
VS.
VS.
up
up 对手不参选
VS,比较
16
Winner (胜者 )
21 16
16 6325*21
21 25 49 25* 16 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出冠军并调整胜者树后树的状态
a[1]
排序码比较次数, 2
VS.
VS.
up
up 对手不参选
VS,比较
21
Winner (胜者 )
21 63
6325*21
21 25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出亚军并调整胜者树后树的状态
a[2]
排序码比较次数, 1
VS.
up
up 对手不参选
VS,比较
25
Winner (胜者 )
25 63
6325*25
25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第三名并调整胜者树后树的状态
a[3]
排序码比较次数, 2
VS.
VS.
up
up 对手不参选
VS,比较
25*
Winner (胜者 )
25* 63
6325*
49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第四名并调整胜者树后树的状态
a[4]
排序码比较次数, 1
VS.
up
up 对手不参选
VS,比较
49
Winner (胜者 )
49 63
6349
49 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第五名并调整胜者树后树的状态
a[5]
排序码比较次数, 1
VS.
up
up
up 对手不参选
VS,比较
63
Winner (胜者 )
63
63
63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
全部比赛结果输出时树的状态
a[6]
排序码比较次数, 0
up
up 对手不参选
VS,比较
? 锦标赛排序构成的胜者树是满的完全二叉树,
其深度为 ?log2n?,其中 n 为待排序元素个数。
? 除 第一次选择具有最小排序码的对象 需要进
行 n-1 次 排序码比较 外,重构胜者树选择具
有次小、再次小排序码对象所需的 排序码比
较次数 均为 O(log2n)。 总排序码比较次数 为
O(nlog2n)。
? 对象的移动次数不超过排序码的比较次数,
所以锦标赛排序总时间复杂度为 O(nlog2n)。
? 这种排序方法虽然减少了许多排序时间,但
是使用了较多的附加存储。
? 如果有 n 个对象，必须使用至少 2n-1 个结
点来存放胜者树。最多需要找到满足
2k-1 < n ? 2k
的 k，使用 2*2k-1 个结点。
? 每个结点包括 排序码, 结点序号 和 比较标志
三种信息。
? 锦标赛排序是一个 稳定 的排序方法 。
? 利用堆及其运算,可以很容易地实现选择排
序的思路。
? 堆排序分为两个步骤
? 根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
? 通过一系列的对象交换和重新调整堆进
行排序。
堆排序 (Heap Sort)
建立初始的最大堆
21
25
25*
49
16 08
0
1 2
3 4 5
i 21
25
25* 16
49
08
0
2
543
1
i
21 25 49 25* 16 08
初始排序码集合
21 25 49 25* 16 08
i = 2 时的局部调整
21
25
25*
49
16 08
0
1 2
3 4 5
i
49
25
25* 16
21
08
0
2
543
1
21 25 49 25* 16 08 49 25 21 25* 16 08
i = 0 时的局部调整
形成最大堆
i = 1 时的局部调整
最大堆的向下调整算法
template <class Type> void MaxHeap<Type>,:
FilterDown ( const int i,const int EndOfHeap ) {
int current = i; int child = 2*i+1;
Type temp = heap[i];
while ( child <= EndOfHeap ) { //最后位置
if ( child +1 < EndOfHeap &&
heap[child] < heap[child+1] )
child = child+1; //选两子女的大者
if ( temp >= heap[child] )
break; //temp排序码大,不做调整
else {
heap[current] = heap[child]; //大 子女上移
current = child; //向下继续调整
child = 2*child+1;
}
}
heap[current] = temp; //回放到合适位置
}
将表转换成堆
for ( int i = ( CurrentSize-2) / 2 ; i >= 0; i-- )
FilterDown ( i,CurrentSize-1 );
基于初始堆进行堆排序
? 最大堆堆顶 V[0]具有最大的排序码,将 V[0]与
V[n-1]对调,把具有最大排序码的对象交换
到最后,再对前面的 n-1个对象,使用堆的调
整算法 FilterDown(0,n-2),重新建立最大堆,
具有次最大排序码的对象又上浮到 V[0]位臵。
? 再 对调 V[0]和 V[n-2],调用 FilterDown(0,n-3),
对前 n-2个对象重新调整,… 。
? 如此反复执行，最后得到全部排序好的对象
序列。这个算法即堆排序算法，其细节在下
面的程序中给出。
49
25
25*
21
16 08
0
1 2
3 4 5
08
25
25* 16
21
49
0
2
543
1
49 25 21 25* 16 08 08 25 21 25* 16 49
交换 0 号与 5 号对象,
5 号对象就位
初始最大堆
25
25*
08
21
16 49
0
1 2
3 4 5
16
25*
08 25
21
49
0
2
543
1
25 25* 21 08 16 49 16 25* 21 08 25 49
交换 0 号与 4 号对象,
4 号对象就位
从 0 号到 4 号 重新
调整为最大堆
25*
16
08
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
25* 16 21 08 25 49 08 16 21 25* 25 49
交换 0 号与 3 号对象,
3 号对象就位
从 0 号到 3 号 重新
调整为最大堆
21
16
25*
08
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
21 16 08 25* 25 49 08 16 21 25* 25 49
交换 0 号与 2 号对象,
2 号对象就位
从 0 号到 2 号 重新
调整为最大堆
16
08
25*
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
16 08 21 25* 25 49 08 16 21 25* 25 49
交换 0 号与 1 号对象,
1 号对象就位
从 0 号到 1 号 重新
调整为最大堆
堆排序的算法
template <class Type> void MaxHeap<Type>,:
HeapSort ( ) {
//对表 heap[0]到 heap[n-1]进行排序,使得表中
//各 个对象按其排序码非递减有序 。
for ( int i = ( CurrentSize-2 ) / 2; i >= 0; i-- )
FilterDown ( i,CurrentSize-1 ); //初始堆
for ( i = CurrentSize-1; i >= 1; i--) {
Swap ( heap[0],heap[i] ); //交换
FilterDown ( 0,i-1 ); //重建最大堆
}
}
? 若设堆中有 n 个结点,且 2k-1 ? n ? 2k,则对
应的完全二叉树有 k 层 。在第 i 层上的结点
数 ? 2i (i = 0,1,…,k-1)。 在第一个形成初
始堆的 for 循环中对每一个非叶结点调用了
一次堆调整算法 FilterDown( ),因此该循环
所用的计算时间为：
? 其中,i 是层序号,2i 是第 i 层的最大结点数,
(k-i-1)是第 i 层结点能够移动的最大距离。
? ??
?
?
????
2
0
22
k
i
i ik 1
? 第二个 for循环中调用了 n-1次 FilterDown( )算
法,该循环的计算时间为 O(nlog2n)。因此,堆
排序的时间复杂性为 O(nlog2n)。
? 该算法的附加存储主要是在第二个 for循环中
用来执行对象交换时所用的一个临时对象。
因此，该算法的空间复杂性为 O(1)。
? 堆排序是一个 不稳定 的排序方法 。
n
j
n
j
jik
k
j
k
j
jj
k
k
j
jk
k
i
i
4?????
????????
? ?
??
?
?
?
?
?
?
?
??
?
?
1
1
1
1
1
1
1
1
2
0
2
2
2
22
22122 )(
归并排序 (Merge Sort)
? 归并，是将两个或两个以上的有序表合并成
一个新的有序表。
? 对象序列 initList中两个有序表 V[l] …V[ m]和
V[m+1] …V[ n]。它们可归并成一个有序表,
存于另一对象序列 mergedList的 V[l] …V[ n]
中。
? 这种归并方法称为 两路归并 (2-way merging)。
? 设变量 i 和 j 分别是表 V[l] …V[ m]和
V[m+1] …V[ n]的当前检测指针。变量 k 是存
放指针。
归并
08 21 25 25* 49 62 72 93 16 37 54
left mid mid+1 right
initList
i j
08 16 21 25 25* 37 49 54 62 72 93
left right
k
mergeList
? 当 i 和 j 都在两个表的表长内变化时,根据对
应项的排序码的大小,依次把排序码小的对
象排放到新表 k 所指位臵 中；
? 当 i 与 j 中有一个已经超出表长时，将另一
个表中的剩余部分照抄到新表中。
迭代的归并排序算法
? 迭代的归并排序算法就是利用两路归并过程
进行排序的。其基本思想是：
? 假设初始对象序列有 n 个对象,首先把它看
成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到 ?n / 2? 个长度为 2 的归
并项 (如果 n 为奇数，则最后一个有序子序
列的长度为 1)；再做两两归并,…,如此重
复,最后得到一个长度为 n 的有序序列 。
两路归并算法
template <class Type> void dataList<Type>,:
merge ( dataList <Type> & mergedList,const
int left,const int mid,const int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较
if ( Vector[i] <= Vector[j] ) {
mergedList.Vector[k] = Vector[i];
i++; k++;
}
else {
mergedList.Vector[k] = Vector[j];
j++; k++;
}
if ( i <= mid )
for ( int n1 = k,n2 = i; n2 <= mid;
n1++,n2++ )
mergedList.Vector[n1] = Vector[n2];
else
for ( int n1 = k,n2 = j; n2 <= right;
n1++,n2++)
mergedList.Vector[n1] = Vector[n2];
}
一趟归并排序的情形
? 设 initList.Vector[0]到 initList.Vector[n-1]中
n 个对象 已经分为一些长度为 len 的归并项,
将这些归并项两两归并,归并成长度为 2len
的归并项,结果放到 mergedList.Vector中。
? 如果 n不是 2len的整数倍,则一趟归并到最后,
可能遇到两种情形：
? 剩下一个长度为 len的归并项和另一个长
度不足 len的归并项,可用 merge算法 将它
们归并成一个长度小于 2len 的归并项。
? 只剩下一个归并项，其长度小于或等于
len,将它直接抄到 MergedList.Vector中。
template <class Type> void datalist<Type>,:
MergePass ( dataList<Type> & mergedList,
const int len ) {
int i = 0;
while (i+2*len <= CurrentSize-1) {
merge(mergedList,i,i+len-1,i+2*len-1);
i += 2 * len; //循环两两归并
}
if ( i+len <= CurrentSize-1 )
merge(mergedList,i,i+len-1,CurrentSize-1);
else for ( int j = i; j <= CurrentSize-1; j++)
mergedList.Vector[j] = Vector[j];
}
迭代的归并排序算法
21 25
25*
25* 93 62 72 08 37 16 5449
21 25 49 62 93 08 72 16 37 54
21 25 25* 49 08 62 72 93 16 37 54
08
08
21
16
25
21
25*
25
49
25*
62
37
72
49
93
54
16 37 54
62 72 93
len=1
len=2
len=4
len=8
len=16
(两路 )归并排序的主算法
template <class Type>
void dataList<Type>,,MergeSort ( ) {
//按对象排序码非递减的顺序对表中对象排序
dataList<Type> & tempList ( MaxSize );
int len = 1;
while ( len < CurrentSize ) {
MergePass ( tempList,len ); len *= 2;
tempList.MergePass ( this,len ); len *= 2;
}
delete [ ] tempList;
}
? 在迭代的归并排序算法中,函数 MergePass( )
做一趟两路归并排序,要调用 merge ( )函数
?n/(2*len)? ? O(n/len) 次,函数 MergeSort( )调
用 MergePass( )正好 ?log2n? 次,而每次 merge( )
要执行比较 O(len)次,所以算法总的时间复杂
度为 O(nlog2n)。
? 归并排序占用附加存储较多,需要另外一个与
原待排序对象数组同样大小的辅助数组 。 这
是这个算法的缺点 。
? 归并排序是一个 稳定 的排序方法 。
递归的表归并排序
? 与快速排序类似，归并排序也可以利用划分
为子序列的方法递归实现。
? 在递归的归并排序方法中，首先要 把整个待
排序序列划分为两个长度大致相等的部分,
分别称之为 左子表 和 右子表 。 对这些子表分
别递归地进行排序,然后再把 排好序的两个
子表进行归并 。
? 图示：待排序对象序列的排序码为 { 21,25,
49,25*,16,08 }，先是进行子表划分，待到子
表中只有一个对象时递归到底。再是实施归
并，逐步退出递归调用的过程。
21 25 49 25* 16 08
21 25 49 25* 16 08
21
25 49
25 49
21
25* 16 08
25* 16 08
21 25 49 25* 16 08
16 0825* 25 4921
递
归
21 25* 16 08 49 25
25* 16 0821 25 49
回
推
静态链表的两路归并算法
template <class Type>
int staticlinkList<Type>,,ListMerge (
const int start1,const int start2 ) {
int k = 0,i = start1,j = start2;
while ( i && j )
if ( Vector[i].key <= Vector[j].key ) {
Vector[k].link = i; k = i;
i = Vector[i].link;
}
else {
Vector[k].link = j; k = j;
j = Vector[j].link;
}
if ( i == 0 ) Vector[k].link = j;
else Vector[k].link = i;
return Vector[0].link;
}
递归的归并排序算法
template <class Type>
int staticlinkList<Type>,,MergeSort (
const int left,const int right ) {
if ( left >= right ) return left;
int mid = ( left + right ) / 2;
return ListMerge (
MergeSort ( left,mid ),
MegerSort ( mid+1,right ) );
//以中点 mid为界,分别对左半部和右半部进
//行表归并排序
}
? 链表的归并排序方法的 递归深度 为 O(log2n)，
对象排序码的比较次数为 O(nlog2n)。
? 链表的归并排序方法是一种 稳定 的排序方法。
基数排序 (Radix Sort)
? 基数排序是采用,分配,与,收集,的办法，
用对多排序码进行排序的思想实现对单排序
码进行排序的方法。
多排序码排序
? 以扑克牌排序为例 。 每张扑克牌有两个, 排
序码,, 花色 和 面值 。 其有序关系为：
? 花色,???????
? 面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 <
J < Q < K < A
? 如果我们把所有扑克牌排成以下次序：
? 2,…,? A,? 2,…,? A,? 2,…,? A,?
2,…,? A
? 这就是 多排序码排序 。排序后形成的有序序
列叫做词典有序序列。
? 对于上例两排序码的排序，可以先按花色排
序，之后再按面值排序；也可以先按面值排
序，再按花色排序。
? 一般情况下，假定有一个 n 个对象的序列
{V0,V1,…,V n-1 }，且每个对象 Vi 中含有 d 个
排序码
? 如果对于序列中任意两个对象 Vi 和 Vj (0 ? i <
j ? n-1 ) 都满足：
? 则称序列对排序码 (K1,K2,…,Kd) 有序。其
中,K1 称为最高位排序码,Kd 称为最低位排
序码。
? 如果排序码是由 多个数据项组成的数据项组,
则依据它进行排序时 就需要利用多排序码排
序 。
? 实现多排序码排序有两种常用的方法
? ?diii KKK,,,?21
? ? ? ?djjjdiii KKKKKK,,,,,,?? 2121 ?
? 最高位优先 MSD ( Most Significant Digit
first )
? 最低位优先 LSD ( Least Significant Digit
first)
? 最高位优先法 通常是一个递归的过程：
? 先根据 最高位排序码 K1排序,得到若干对
象组,对象组中各对象都有相同 排序码 K1。
? 再分别对每组中对象根据 排序码 K2 进行
排序,按 K2 值的不同,再分成若干个更小
的子组,每个子组中的对象具有相同的 K1
和 K2值。
? 依此重复,直到对 排序码 Kd完成排序为止 。
? 最后,把所有子组中的对象依次连接起来,
就得到一个有序的对象序列 。
? 最低位优先法 首先依据 最低位排序码 Kd对所
有对象进行一趟排序, 再依据 次低位排序码
Kd-1对上一趟排序的结果再排序, 依次重复,
直到依据 排序码 K1最后一趟排序完成, 就可
以得到一个有序的序列 。 使用这种排序方法
对每一个排序码进行排序时, 不需要再分组,
而是整个对象组都参加排序 。
? 基数排序是典型的 LSD排序方法,利用, 分配,
和, 收集, 对单排序码进行排序 。 在这种方
法中, 把单排序码 Ki 看成是一个 d元组：
? 其中的每一个分量 ( 1? j ? d ) 也可看成是
一个排序码 。
? ?diii KKK,,,?21
? LSD和 MSD方法也可应用于对一个排序码进
行的排序。此时可将 单排序码 Ki 看作是一个
子排序码组：
? ?diii KKK,,,?21
链式基数排序
jiK
jiK
? 分量 (1 ? j ? d) 有 radix种取值,称 radix为
基数 。 例如,排序码 984可以看成是一个 3元
组 (9,8,4),每一位有 0,1,…,9 等 10种取值,
基数 radix = 10。 排序码 ‘ data’可以看成是
一个 4元组 (d,a,t,a),每一位有 ‘ a’,‘b’,…,
‘z’等 26种取值, radix = 26。
? 针对 d元组中的每一位分量,把对象序列中
的所有对象,按 的取值, 先, 分配, 到 rd
个队列中去 。 然后再按各队列的顺序, 依
次把对象从队列中, 收集, 起来, 这样所
有对象按取值 排序完成 。
jiK
jiK
jiK
? 如果对于所有对象的排序码 K0,K1,…,Kn-1,
依次对各位的分量,让 j = d,d-1,…,10,分
别用,分配,、,收集,的运算 逐趟进行排
序,在最后一趟,分配,、,收集, 完成
后,所有对象就按其排序码的值从小到大排
好序了 。
? 各队列采用链式队列结构,分配到同一队列
的排序码用链接指针链接起来。每一队列设
臵两 个队列指针,int front [radix]指示队
头,int rear [radix] 指向队尾。
? 为了有效地存储和重排 n 个待排序对象，以
静态链表作为它们的存储结构。
基数排序的“分配”与“收集”过程 第
一趟614 921 485 637738 101 215 530 790 306
第一趟分配（按最低位 i = 3 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738921 485 637
101 215
530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第一趟收集
530 790 921 101 614 485 215 306 637 738
基数排序的“分配”与“收集”过程 第
二趟 614921 485 637 738101 215530 790 306
第二趟分配（按次低位 i = 2 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614
738
921 485
637
101
215
530 790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第二趟收集
530 790921101 614 485215306 637 738
基数排序的“分配”与“收集”过程 第
三趟 614 921 485637 738101 215 530 790306
第三趟分配（按最高位 i = 1 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738 921485
637
101 215 530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第三趟收集
530 790 921101 614485215 306 637 738
链表基数排序
template <class Type>
void staticlinkList <Type>,,RadixSort (
const int d,const int radix ) {
int rear[radix],front[radix];
for ( int i = 1; i < CurrentSize; i++ )
Vector[i].link = i+1;
Vector[n].link = 0; //静态链表初始化
int current = 1; //链表扫描指针
for ( i = d-1; i >= 0; i-- ) { //d趟分配,收集
for ( int j = 0; j < radix; j++ ) front[j] = 0;
while ( current != 0 ) { //逐个对象分配
int k = Vector[current].key[i];
//取当前对象排序码的第 i 位
if ( front[k] == 0) //原链表为空
front[k] = current; //队头链入
else //原链表非空,链尾链入
Vector[rear[k]].link = current;
rear[k] = current; //修改链尾指针
current = Vector[current].link; //下一对象
}
j = 0; //从 0号队列开始收集
while ( front[j] == 0 ) j++; //空队列跳过
Vector[0].link = current = front[j]; //新链头
int last = rear[j]; //新链尾
for ( k = j+1; k < radix; k++)
//逐个队列链接
if ( front[k] ) {
Vector[last].link = front[k];
last = rear[k];
}
Vector[last].link = 0; //链收尾
} //下一趟
}
? 若每个排序码有 d 位,需要重复执行 d 趟
,分配, 与, 收集, 。 每趟对 n 个对象进行
,分配,, 对 radix个队列进行, 收集, 。
总时间复杂度为 O ( d ( n+radix ) )。
? 若 基数 radix相同,对于 对象个数较多 而 排序
码位数较少 的情况,使用链式基数排序较好 。
? 基数排序需要增加 n+2radix个附加链接指针 。
? 基数排序是 稳定 的排序方法 。
各种排序方法的比较
比较次数 移动次数 附加存储排 序 方 法
最好 最
差
最好 最
差
稳定
性
最好 最
差
直接插入排序 n n
2
0 n
2
? 1
折半插入排序 n l og
2
n 0 n
2
? 1
起泡排序
n n
2
0 n
2
? 1
快速排序 n l og
2
n n
2
n l og
2
n n
2
? l og
2
n n
2
简单选择排序 n
2
0 n ? 1
锦标赛排序 n l og
2
n n l og
2
n ? n
堆排序 n l og
2
n n l og
2
n ? 1
归并排序
n l og
2
n n l og
2
n ? n
外排序
? 当对象以文件形式存放于磁盘上的时候,通
常是按物理块存储的。
当待排序的对象数目特别多时，在内存中不
能一次处理。必须把它们以文件的形式存放于
外存，排序时再把它们一部分一部分调入内存
进行处理。这样，在排序过程中必须不断地在
内存与外存之间传送数据。 这种基于外部存储
设备（或文件）的排序技术就是外排序 。
外排序的基本过程
? 物理块 也叫做 页块 。每个页块可存放几个对
象。操作系统 按页块对磁盘信息进行读写 。
? 磁盘通常是指 由若干片磁盘组成的磁盘组,
各个盘片安装在同一主轴上高速旋转。各个
盘面上半径相同的磁道构成了柱面。各盘面
设臵一个读写磁头，它们装在同一动臂上，
可以径向从一个柱面移到另一个柱面上。
? 为了访问某一页块,先寻找柱面, 移动动臂使
读写磁头移到指定柱面上, 寻查 (seek)。再根
据磁道号 (盘面号 )选择相应读写磁头,等待指
定页块转到读写磁头下, 等待 (latency)。 在
磁盘组上存取一个页块的时间：
? 基于磁盘进行的排序多使用归并排序方法。
其排序过程主要分为两个阶段：
① 建立 用于外排序的内存缓冲区 。根据它们
的大小 将输入文件划分为若干段,用某种
内排序方法对各段进行排序。经过排序的
段叫做 初始归并段 或初始顺串 (Run)。当
它们生成后就被写到外存中去。
② 仿照归并树模式,把 ① 生成的初始归并段
加以归并,一趟趟地 扩大归并段 和 减少归
并段个数,直到最后归并成一个大归并段
(有序文件 )为止。
tio＝ tseek＋ tlatency＋ trw
? 示例：设有一个包含 4500个对象 的输入文件。
现用一台其内存 至多可容纳 750个对象 的计算
机对该文件进行排序。输入文件放在磁盘上,
磁盘每个页块可容纳 250个对象,这样全部对
象可存储在 4500 / 250＝ 18 个页块中。输出
文件也放在磁盘上,用以存放归并结果。
? 由于内存中可用于排序的存储区域能容纳 750
个对象,因此 内存中恰好能存 3个页块 的对象。
? 在外排序一开始,把 18块对象,每 3块一组,读
入内存。利用某种内排序方法进行内排序,形
成初始归并段,再写回外存。总共可得到 6个
初始归并段。然后一趟一趟进行归并排序。
两路归并排序的归并树
R1 750 R2 750 R3 750 R4 750 R5 750 R6 750
初始
归并段
R12 1500 R34 1500 R56 1500
R1234 3000
R123456 4500
第一趟
归并结果
第二趟
归并结果
第三趟
归并结果
? 若把内存区域等份地分为 3 个缓冲区。其中
的两个为输入缓冲区,一个为输出缓冲区,可
以在内存中利用简单 2 路归并函数 merge( )
实现 2 路归并。
? 首先,从参加归并排序的两个输入归并段 R1
和 R2 中分别读入一块,放在 输入缓冲区 1和
输入缓冲区 2中。然后在内存中进行 2 路归
并，归并结果顺序存放到 输出缓冲区 中。
输入缓冲区 2
输入缓冲区 1
输出缓冲区
? 若总对象个数为 n，磁盘上每个页块可容纳
b 个对象，内存缓冲区可容纳 i 个页块，则
每个 初始归并段长度 为 len = i * b，可生成
m = ?n / len?个 等长的初始归并段 。
? 在做 2 路归并排序时,第一趟从 m 个初始归
并段得到 ?m/2?个归并段,以后各趟将从 l (l
>1) 个归并段得到 ?l/2?个归并段 。总归并趟
数等于 归并树的高度 ?log2m?。
? 估计 2 路归并排序时间 tES 的上界为：
tES = m*tIS + d*tIO + S*u*tmg
? 对 4500 个对象 进行排序的例子,各种操作的
计算时间如下：
? 读 18 个输入块,内部排序 6段,写 18个输
出块 ＝ 6 tIS＋ 36 tIO
? 成对归并初始归并段 R1～ R6
＝ 36 tIO＋ 4500 tmg
? 归并两个具有 1500 个对象的归并段 R12
和 R34
＝ 24 tIO＋ 3000 tmg
? 最后将 R1234 和 R56 归并成一个归并段
＝ 36 tIO＋ 4500 tmg
? 合计 tES＝ 6 tIS＋ 132 tIO＋ 12000 tmg
? 由于 tIO=tseek+tlatency+trw,其中,tseek和 tlatency是
机械动作, 而 trw,tIS,tmg是电子线路的动作,
所以 tIO远远大于 tIS和 tmg。 想要提高外排序的
速度, 应着眼于减少 d。
? 若对相同数目的对象, 在同样页块大小的情
况下做 3 路归并或做 6 路归并 (当然,内存缓
冲区的数目也要变化 ),则可做大致比较：
归并路数 k 总读写磁盘次数 d 归并趟数 S
2 132 3
3 108 2
6 72 1
? 增大归并路数,可减少归并趟数,从而减少总
读写磁盘次数 d。
? 对 m 个初始归并段,做 k 路平衡归并,归并树
可用 正则 k 叉树 (即只有度为 k 与度为 0的结
点的 k 叉树 ) 来表示。
? 第一趟可将 m 个初始归并段归并为 l = ?m/k?
个归并段，以后每一趟归并将 l 个归并段归
并成 l = ?l / k?个归并段，直到最后形成一个
大的归并段为止。树的高度＝ ?logkm?＝ 归
并趟数 S。
k路平衡归并 (k-way Balanced merging)
? 做 k 路平衡归并时,如果有 m 个初始归并段,
则相应的归并树有 ?logkm?+1 层,需要归并
?logkm?趟。下图给出对有 36 个初始归并段
的文件做 6 路平衡归并时的归并树。
? 做内部 k 路归并时,在 k 个对象中选择最小
者, 需要顺序比较 k-1 次 。 每趟归并 u 个对
象需要做 (u-1)*(k-1)次比较,S 趟归并总共需
要的比较次数为,
S*(u-1)*(k-1) = ?logkm?* (u-1) * (k-1)
= ?log2m?* (u-1) * (k-1) / ?log2k?
? 在初始归并段个数 m 与对象个数 u 一定时,
?log2m?*(u-1) = const,而 (k-1) / ?log2k?在 k
增大时趋于无穷大。因此,增大归并路数 k,
会使得内部归并的时间增大。
? 使用,败者树,从 k 个归并段中选最小者,当
k 较大时 (k ? 6)，选出排序码最小的对象只需
比较 ?log2k?次。
S*(u-1)*?log2k?= ?logkm? * (u-1) * ?log2k?
= ?log2m?* (u-1) * ?log2k?/ ?log2k?
= ?log2m?* (u-1)
? 排序码比较次数与 k 无关,总的内部归并时间
不会随 k 的增大而增大 。
? 下面讨论利用败者树在 k 个输入归并段中选择
最小者，实现归并排序的方法。
? 败者树是一棵 正则的完全二叉树 。其中
? 每个叶结点存放各归并段在归并过程中当
前参加比较的对象；
? 每个非叶结点记忆它两个子女结点中对象
排序码小的结点 (即败者 )；
? 因此,根结点中记忆树中当前对象排序码最
小的结点 (最小对象 )。
? 败者树与胜者树的区别在于一个选择了败者
(排序码大者 ),一个选择了胜者 (排序码小者 )。
? 示例：设有 5 个初始归并段,它们中各对象
的排序码分别是：
Run0,{17,21,∞}
Run1,{05,44,∞}
Run2,{10,12,∞}
Run3,{29,32,∞}
Run4,{15,56,∞}
29
32
?
15
56
?
17
21
?
05
44
?
10
12
?
15
100517
29
3
0 2
4
1
k3 k4
k0 k1 k2
Run3 Run4
Run0 Run1 Run2
ls1
ls0
ls2
ls4
ls3
冠军 (最小对象 ),
输出段 1当前对象
选中
输出段 1最小对象，
段 1下一对象参选，
调整败者树
29
32
?
15
56
?
17
21
?
05
44
?
10
12
?
15
104417
29
3
0 1
4
2
k3 k4
k0 k1 k2
Run3 Run4
Run0 Run1 Run2
ls1
ls0
ls2
ls4
ls3
次最小对象
选中
? 败者树的高度为 ?log2k?，在每次调整,找下
一个具有最小排序码对象时,最多做 ?log2k?
次排序码比较。
? 在内存中应 为每一个归并段分配一个输入缓
冲区,其 大小应能容纳一个页块的对象,编号
与归并段号一致 。每个输入缓冲区应有一个
指针,指示当前参加归并的对象。
? 在内存中还应设立 一个输出缓冲区,其大小
相当于一个页块大小。它也有一个缓冲区指
针,指示当前可存放结果对象的位臵。每当
一个对象 i 被选出,就执行 OutputRecord(i)操
作,将对象存放到输出缓冲区中。
? 在实现利用败者树进行多路平衡归并算法时,
把败者树的 叶结点 和 非叶结点 分开定义 。
? 败者树叶结点 key[ ]有 k+1个,key[0]到 key[k-1]
存放 各归并段当前参加归并的对象的排序码,
key[k]是辅助工作单元,在初始建立败者树时
使用, 存放一个最小的在各归并段中不可能出
现的排序码,-MaxNum。
? 败者树非叶结点 loser[ ]有 k个,其中 loser[1]到
loser[k-1]存放各次比较的败者的归并段号,
loser[0]中是最后胜者所在归并段号 。 另外还
有一个存放各归并段参加归并对象的数组 r[k]。
k 路平衡归并排序算法
void kwaymerge ( Element *r ) {
r = new Element[k]; //创建对象数组
int *key = new int[k+1]; //创建外结点数组
int *loser = new int[k]; //创建败者树数组
for ( int i = 0; i < k; i++ ) //传送参选排序码
{ InputRecord ( r[i] ); key[i] = r[i].key; }
for ( i = 0; i < k; i++) loser[i] = k;
key[k] = -MaxNum; //初始化
for ( i = k-1; i; i-- ) //调整形成败者树
adjust ( key,loser,k,i );
while ( key[loser[0]] != MaxNum ) { //选冠军
q = loser[0]; //最小对象的段号
OutputRecord ( r[q] ); //输出
InputRecord ( r[q] ); //从该段补入对象
key[q] = r[q].key;
adjust ( key,loser,k,q ); //调整
}
Output end of run marker; //输出段结束标志
delete [ ] r; delete [ ] key; delete [ ] loser;
}
自某叶结点 key[q]到败者树根结点的调整算法
void adjust ( int key[ ]; int loser[ ]; const int k;
const int q ) {
//q指示败者树某外结点 key[q],从该结点起到
//根进行比较,将最小 key 对象所在归并段的
//段号记入 loser[0]。 k是外结点 key[ ]个数。
for ( int t = (k+q) / 2; t > 0; t /= 2 ) // t是 q双亲
if ( key[loser[t]] < key[q]) {
//败者记入 loser[t],胜者记入 q
int temp = q; q = loser[t]; loser[t] = temp;
} //q与 loser[t]交换
loser[0] = q;
}
? 每选出一个当前排序码最小的对象,就需要
在将它送入输出缓冲区之后,从相应归并段
的输入缓冲区中取出下一个参加归并的对象,
替换已经取走的最小对象,再从叶结点到根
结点,沿某一特定路径进行调整,将下一个排
序码最小对象的归并段号调整到 loser[0]中 。
? 段结束标志 MaxNum升入 loser[0],排序完成 。
? 归并路数 k 不是越大越好。归并路数 k 增大,
相应需增加输入缓冲区个数。如果可供使用
的内存空间不变,势必要减少每个输入缓冲
区的容量,使内外存交换数据的次数增大 。
利用败者树进行 5路平衡归并的过程
(1) 初始状态 (2) 加入 15,29,调整
29 15
5 17
5
05
5
10
-?
5
5
k3 k4 k5
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 10
k2
5
05
ls3
k1
17
4
k0
ls2
3ls4
15
k4
-?
k5
29
k3
5ls1
5ls0
利用败者树进行 5路平衡归并的过程
29 15
3 17
4
05
2
10
-?
1
5
k3 k4 k5
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 10
k2
2
05
ls3
k1
17
0
k0
ls2
3ls4
15
k4
-?
k5
29
k3
4ls1
1ls0
(3) 加入 10,05,调整 (4) 加入 17,调整
输出 05
利用败者树进行 5路平衡归并的过程
29 15
3 17
0
44
1
10
4
2
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 12
k2
1
44
ls3
k1
17
0
k0
ls2
3ls4
15
k4
29
k3
4ls1
2ls0
(5) 输出 05后调整 (6) 输出 10后调整
输入 44
输出 12输出 10
输入 12
利用败者树进行 5路平衡归并的过程
29 15
3 17
0
44
2
?
1
4
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
44
ls3
k1
17
3
k0
ls2
4ls4
56
k4
29
k3
1ls1
0ls0
输入 ?
输出 17输出 15
输入 56
(7) 输出 12后调整 (8) 输出 15后调整
利用败者树进行 5路平衡归并的过程
29 56
4 21
3
44
2
?
1
0
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
44
ls3
k1
?
0
k0
ls2
4ls4
56
k4
29
k3
1ls1
3ls0
输入 21
输出 29输出 21
输入 ?
(9) 输出 17后调整 (10) 输出 21后调整
利用败者树进行 5路平衡归并的过程
32 56
4 ?
0
44
2
?
1
3
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
44
ls3
k1
?
0
k0
ls2
3ls4
56
k4
?
k3
4ls1
1ls0
输入 32
输出 44输出 32
输入 ?
(11) 输出 29后调整 (12) 输出 32后调整
利用败者树进行 5路平衡归并的过程
? 56
3 ?
0
?
2
?
1
4
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
?
ls3
k1
?
0
k0
ls2
3ls4
?
k4
?
k3
1ls1
4ls0 输出 ?，
结束
输出 56
输入 ?输入 ?
(13) 输出 44后调整 (14) 输出 56后调整
初始归并段的生成 (Run Generation)
? 为减少读写磁盘次数,除增加归并路数 k 外,
还可 减少初始归并段个数 m。 在总对象数 n
一定时,要减少 m,必须 增大初始归并段长度 。
? 如果规定每个初始归并段等长,则此长度应
根据生成它的内存工作区空间大小而定,因
而 m的减少也就受到了限制 。
? 为了突破这个限制,可 采用败者树来生成初
始归并段 。 在使用同样大内存工作区的情况
下,可以 生成平均比原来等长情况下大一倍
的初始归并段,从而 减少初始归并段个数 。
? 设输入文件 FI中各对象的排序码序列为 { 17,
21,05,44,10,12,56,32,29 }。
? 选择和臵换过程的步骤如下：
① 从输入文件 FI中把 k 个对象读入内存中,并
构造败者树 。 (内存中存放对象的数组 r可容
纳的对象个数为 k )
② 利用败者树在 r 中选择一个排序码最小的对
象 r[q],其排序码存入 LastKey作为门槛 。 以
后再选出的排序码比它大的对象归入本归并
段,比它小的归入下一归并段 。
③ 将此 r[q]对象写到输出文件 FO中 。 (q 是叶结
点序号 )
④ 若 FI未读完,则从 FI读入下一个对象,臵换
r[q]及败者树中的 key[q]。
⑤ 调整败者树,从所有排序码比 LastKey大的
对象中选择一个排序码最小的对象 r[q]作为
门槛,其排序码存入 LastKey。
⑥ 重复 ③ ～ ⑤,直到在败者树中选不出排序码
比 LastKey大的对象为止 。 此时,在输出文件
FO中得到一个初始归并段,在它最后加一个
归并段结束标志 。
⑦ 重复 ② ～ ⑥,重新开始选择和臵换,产生新的
初始归并段,直到输入文件 FI中所有对象选
完为止 。
输 入 文 件 FI 内存数组 r 输出文件 FO
1
7 21 05 44 10 12 56 32 29
44 10 12 56 32 29 1 7 2 1 05
10 12 56 32 29 17 2 1 4 4 0 5
12 56 32 29 1 0 21 4 4 0 5 1 7
56 32 29 1 0 1 2 44 0 5 1 7 2 1
32 29 1 0 1 2 56 0 5 1 7 2 1 4 4
29 1 0 1 2 3 2 0 5 1 7 2 1 4 4 5 6
29 1 0 1 2 3 2 0 5 1 7 2 1 4 4 5 6 ?
29 10 1 2 3 2
2 9 1 2 3 2 1 0
2 9 ─ 3 2 1 0 1 2
─ ─ 32 1 0 1 2 2 9
─ ─ ─ 1 0 1 2 2 9 3 2
─ ─ ─ 1 0 1 2 2 9 3 2 ?
? 若按在 k 路平衡归并排序 中所讲的, 每个初
始归并段的长度与内存工作区的长度一致,
则上述 9个对象可分成 3个初始归并段：
Run0 { 05,17,21 }
Run1 { 10,12,44 }
Run2 { 29,32,56 }
? 但采用上述选择与臵换的方法,可生成 2个长
度不等的初始归并段,
Run0 { 05,17,21,44,56 }
Run1 { 10,12,29,32 }
? 在利用败者树生成 不等长初始归并段 的算法
和调整败者树并选出最小对象的算法中, 用
两个条件来决定谁为败者, 谁为胜者 。
?首先比较两个对象所在归并段的段号,段
号小者为胜者, 段号大者为败者 ；
?在归并段的段号相同时,排序码小者为胜
者, 排序码大者为败者 。
? 比较后把败者对象在对象数组 r 中的序号记
入它的双亲结点中,把胜者对象在对象数组 r
中的序号记入工作单元 s 中,向更上一层进行
比较,最后的胜者记入 loser[0]中 。
{ 17,21,05,44,10,12,56,32,29 }
17
(1) 初始化 (2) 输入 17,调整
0
0
0
0
0
0
0
0
0
ls1
ls0
ls2
k2
k0
k1
0
0
0
2
1ls0
ls1
k0ls
2
17
1
k2
0
0
k1
0
0
排序码
段号
{ 17,21,05,44,10,12,56,32,29 }
21 (3) 输入 21,调整 (4) 输入 05,建败者树
21
1
1
17
1
0
0
2
0
ls1
ls0
ls2
k2
k0
k1
05
1
2
1
0ls0
ls1
k0ls
2
17
1
k2
21
1
k1
05
选 05
{ 17,21,05,44,10,12,56,32,29 }
44
(5) lastKey=05,置换 (6) lastKey=17,置换
k0,选择 17 k2,段号加 1,选择 21
21
1
1
17
1
44
1
0
2
ls1
ls0
ls2
k2
k0
k1
44
1
0
2
1ls0
ls1
k0ls
2
10
2
k2
21
1
k1
10
选 21选 17
{ 17,21,05,44,10,12,56,32,29 }
12
(7) lastKey=21,置换 (8) lastKey=44,置换
k1,段号加 1,选择 44 k0,选择 56
12
2
1
10
2
44
1
2
0
ls1
ls0
ls2
k2
k0
k1
56
1
2
1
0ls0
ls1
k0ls
2
10
2
k2
12
2
k1
56
选 56选 44
{ 17,21,05,44,10,12,56,32,29 }
32
(9) lastKey=56,置换 (10) 输出段结束标志,
k0,段号加 1,本段结束 选择 10
12
2
1
10
2
32
2
0
2
ls1
ls0
ls2
k2
k0
k1
32
2
0
1
2ls0
ls1
k0ls
2
10
2
k2
12
2
k1
选 10
{ 17,21,05,44,10,12,56,32,29 }
29
(11) lastKey=10,置换 (12) lastKey=12,k1 置
k2,选择 12 虚段,选择 29
12
2
2
29
2
32
2
0
1
ls1
ls0
ls2
k2
k0
k1
32
2
0
1
2ls0
ls1
k0ls
2
29
2
k2
12
3
k1
选 29选 12
虚段
{ 17,21,05,44,10,12,56,32,29 }
(13) lastKey=29,k2 置 (14) lastKey=32,k0 置
虚段,选择 32 虚段,本段结束
12
3
2
29
3
32
2
1
0
ls1
ls0
ls2
k2
k0
k1
32
3
0
2
1ls0
ls1
k0ls
2
29
3
k2
12
3
k1
选 32
虚段虚段 虚段
虚段
虚段
(15) 输出段结束标志,
结束
12
3
2
29
3
32
3
0
1
ls1
ls0
ls2
k2
k0
k1
段号
超出
? 当输入的对象序列已
经按排序码大小排好
序时，只生成一个初
始归并段。
? 在一般情况下，若输
入文件有 n 个对象，
生成初始归并段的时
间开销是 O(nlog2k)，
因为每输出一个对象，
对败者树进行调整需
要时间为 O(log2k)。
最佳归并树
? 归并树是描述归并过程的 m 叉树。因为每一
次做 m 路归并都需要有 m 个归并段参加,因
此,归并树是只有度为 0和度为 m 的结点的正
则 m 叉树。
? 示例, 设有 13个长度不等的初始归并段,其长
度 (对象个数 )分别为
0,0,1,3,5,7,9,13,16,20,24,30,38
? 其中长度为 0 的是空归并段。对它们进行 3
路归并时的归并树如图所示。
此归并树的带权路径长度为
WPL＝ (24+30+38+7+9+13)*2+ (16+20+1+3+5)*3
＝ 377。
16 20 0 1 3 5
36 938 1397
29
03024
54 83
166
? 在归并树中
? 各叶结点代表参加归并的各初始归并段
? 叶结点上的权值即为该初始归并段中的对
象个 数
? 根结点代表最终生成的归并段
? 叶结点到根结点的路径长度表示在归并过
程中的读对象次数
? 各非叶结点代表归并出来的新归并段
? 归并树的带权路径长度 WPL 即为归并过
程中的总读对象数。因而，在归并过程中
总的读写对象次数为 2*WPL = 754。
? 不同的归并方案所对应的归并树的带权路径
长度各不相同。
? 为了使得总的读写次数达到最少,需要改变
归并方案,重新组织归并树。
? 可将霍夫曼树的思想扩充到 m 叉树的情形。
在归并树中,让对象个数少的初始归并段最
先归并,对象个数多的初始归并段最晚归并,
就可建立总读写次数达到最少的最佳归并树。
? 例如,假设有 11个初始归并段,其长度 (对象个
数 )分别为
1,3,5,7,9,13,16,20,24,30,38
做 3路归并。
? 为使归并树成为一棵正则三叉树,可能需要补
入空归并段。补空归并段的原则为：
? 若参加归并的初始归并段有 n 个,做 m 路
平衡归并。因归并树是只有度为 0 和度为
m 的结点的正则 m 叉树,设度为 0 的结点有
n0(= n) 个,度为 m 的结点有 nm 个,则有
n0 = (m-1)nm +1
nm = (n0 -1)／ (m -1)。
? 若 (n0-1) % (m-1) = 0,则说明这 n0 个叶结
点正好可以构造 m 叉归并树。
? 若 (n0 -1) % (m-1) = u ? 0，则对于这 n0 个
叶结点,其中的 u 个不足以参加 m 路归并。
? 故除了有 nm 个度为 m 的内结点之外,还
需增加一个内结点。它在归并树中代替了
一个叶结点位臵,被代替的叶结点加上刚
才多出的 u 个叶结点,再加上 m-u-1 个对
象个数为零的空归并段,就可建立归并树。
? 在示例中,n0 = 11,m = 3,(11-1) % (3-1)
= 0,可以不加空归并段,直接进行 3路归并。
? 它的带权路径长度
WPL = 38*1+(13+16+20+24+30)*2+(7+9)*3
+ (1+3+5)*4 = 328。
1 3 5 7 9 13 16 20 24 30 38
1 3 5
7 9 9 13 16 20 24 30 38
13 16 20 24 25 30 38
1 3 5
97 9
1 3 5
9
25
7
24
9
30 38
13 16 20
49
38
13 16 20
49
24 25 30
79
997
3 51
166
? 如果做 5路归并, 让 m = 5,则有
(11-1)／ (5-1) = 2
? 表示有 2个度为 5的内结点；但是,
u = (11-1) % (5-1) =2 ? 0
? 需要加一个内结点,它在归并树中代替了一
个叶结点的位臵,故一个叶结点参加这个内
结点下的归并,需要增加的空初始归并段数
为 m-u-1＝ 5-2-1 = 2
? 应当补充 2 个空归并段 。 则归并树如图所
示 。
带权路径长度 WPL＝ (1+3+5)*3+(7+9+13+
+16)*2+(20+24+30+38)＝ 229
0 0 1 3 5
7 9 9 13 16 20 24 30 38
0 0 1 3 5
97 9 13 16
5438302420
166
? 插入排序
? 交换排序
? 选择排序
? 归并排序
? 基数排序
? 外排序
概述
? 排序, 将一组杂乱无章的数据按一定的规律
顺次排列起来 。
? 数据表 (datalist),它是待排序数据对象的有限
集合 。
? 排序码 (key),通常数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可
用来区分对象,作为排序依据 。 该域即为 排
序码 。 每个数据表用哪个属性域作为排序码,
要视具体的应用需要而定 。
? 排序算法的稳定性,如果在对象序列中有两
个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],且
在排序之前,对象 r[i]排在 r[j]前面。如果在排
序之后,对象 r[i]仍在对象 r[j]的前面,则称这
个排序方法是稳定的,否则称这个排序方法
是不稳定的。
? 内排序与外排序, 内排序是指在排序期间
数据对象全部存放在内存的排序；外排序
是指在排序期间全部对象个数太多，不能
同时存放在内存，必须根据排序过程的要
求，不断在内、外存之间移动的排序。
? 排序的时间开销, 排序的时间开销是衡量
算法好坏的最重要的标志。 排序的时间开销
可用算法执行中的 数据比较次数 与 数据移动
次数 来衡量 。
? 算法运行时间代价的大略估算一般都 按平均
情况 进行估算。对于那些 受对象排序码序列
初始排列及对象个数影响较大的, 需要 按最
好情况 和 最坏情况 进行估算 。
? 算法执行时所需的附加存储, 评价算法好
坏的另一标准。
待排序数据表的类定义
#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:
Element ( ), key(0),otherdata(NULL) { }
Type getKey ( ) { return key; } //提取排序码
void setKey ( const Type x ) { key = x; } //修改
Element<Type> & operator = //赋值
( Element<Type>& x ) { key = x->key;
otherdata = x->otherdata; }
int operator == (Element<Type>& x )
{ return key == x->key; } //判 this == x
int operator <= (Element<Type>& x )
{ return key <= x->key; } //判 this ? x
int operator < (Element<Type>& x )
{ return key < x->key; } //判 this < x
int operator > (Element<Type>& x )
{ return key > x->key; } //判 this > x
}
template <class Type> class dataList {
private:
Element <Type> * Vector; //存储向量
int MaxSize,CurrentSize; //最大与当前个数
public:
datalist ( int MaxSz = DefaultSize ),
MaxSize ( Maxsz ),CurrentSize (0)
{ Vector = new Element <Type> [MaxSz]; }
void sort ( ); //排序
void swap ( Element <Type> & x,//对换
Element <Type> & y ) {
Element<Type> temp = x;
x = y; y = temp;
}
}
插入排序 (Insert Sorting)
? 基本思想是, 当插入第 i (i ? 1) 个对象时,前
面的 V[0],V[1],…,V[i-1]已经排好序。这时,
用 V[i]的排序码与 V[i-1],V[i-2],… 的排序码
顺序进行比较,找到插入位臵即将 V[i]插入,
原来位臵上的对象向后顺移。
基本方法是, 每步将一个待排序的对象,按
其排序码大小,插入到前面已经排好序的一
组对象的适当位臵上,直到对象全部插入为止 。
直接插入排序 (Insert Sort)
各
趟
排
序
结
果
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 49 25* 16 08 25i = 1
0 1 2 3 4 5 temp
21 25 49 25* 16 08 49i = 2
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 16 08i = 4
0 1 2 3 4 5 temp
21 25 4925*16 08i = 5
i = 3 25*
16
08
16
4916
16
21 25 4925*1608
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 08
i = 4 时的排序过程
0 1 2 3 4 5 temp
21 25 4925*
完成
16
08 16
i = 4
j = 3
i = 4
j = 2
25
25*16
16
21 25 4925* 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 4925* 08
0 1 2 3 4 5 temp
21 25 4925*
16
08 16
16
25
21
i = 4
j = 1
i = 4
j = 0
i = 4
j = -1 16
直接插入排序的算法
template <class Type>
void dataList <Type>,,InsertSort ( ) {
//按排序码 Key非递减顺序对表进行排序
Element<Type> temp; int i,j;
for ( i = 1; i < CurrentSize; i++ ) {
temp = Vector[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < Vector[j-1] )
Vector[j] = Vector[j-1];
else break;
Vector[j] = temp;
算法分析
? 设待排序对象个数为 currentSize = n,则该算
法的主程序执行 n-1趟。
? 排序码比较次数和对象移动次数与对象排序
码的初始排列有关。
? 最好情况下,排序前对象已按排序码从小到
大有序,每趟只需与前面有序对象序列的最
后一个对象比较 1次,移动 2次对象,总的排序
码比较次数为 n-1,对象移动次数 为 2(n-1)。
}
}
? 最坏情况下,第 i 趟时第 i 个对象必须与前面
i 个对象都做排序码比较,并且每做 1次比较
就要做 1次数据移动 。 则总 排序码比较次数
KCN和 对象移动次数 RMN分别为
? 在平均情况下的 排序码比较次数 和 对象移动
次数 约为 n2/4。因此，直接插入排序的时间
复杂度为 o(n2)。
? 直接插入排序是一种 稳定 的排序方法。
?
?
?
?
?
?
??????
????
1
1
1
1
22142
221
n
i
n
i
nnniRM N
nnniKC N
//))(()(
,//)(
2
2
折半插入排序 (Binary Insertsort)
? 基本思想是, 设在顺序表中有一 个对象序列
V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,
V[i-1]是已经排好序的对象。在插入 V[i]时,
利用折半搜索法寻找 V[i]的插入位臵。
折半插入排序的算法
template <class Type>
void dataList<Type>,,BineryInsSort ( ) {
Element<Type> temp; int Left,Right;
for ( int i = 1; i < CurrentSize; i++) {
Left = 0; Right = i-1; temp = Vector[i];
while ( Left <= Right ) {
int middle = ( Left + Right )/2;
if ( temp < Vector[middle] )
Right = middle - 1;
else Left = middle + 1;
}
for ( int k = i-1; k >= Left; k-- )
Vector[k+1] = Vector[k];
Vector[Left] = temp;
}
算法分析
? 折半搜索比顺序搜索查找快,所以折半插入
排序就 平均性能 来说比直接插入排序要快。
? 它所需的 排序码比较次数与待排序对象序
列的初始排列无关,仅依赖于对象个数。 在
插入第 i 个对象时,需要经过 ?log2i?+1 次排
序码比较,才能确定它应插入的位臵。 因此,
将 n 个对象 (为推导方便,设为 n=2k )用折半
插入排序所进行的排序码比较次数为：
? 折半插入排序是一个 稳定 的排序方法。
? ?? ??
?
?
???
1
1
22 l o g1l o g
n
i
nni
? 当 n 较大 时,总排序码比较次数比直接插入
排序的最坏情况要好得多,但比其最好情况
要差 。
? 在对象的初始排列已经按排序码排好序或
接近有序时,直接插入排序比折半插入排序
执行的排序码比较次数要少 。 折半插入排
序的对象移动次数与直接插入排序相同,依
赖于对象的初始排列 。
链表插入排序
? 基本思想是：在每个对象的结点中增加一个
链接指针 数据成员 link。
? 对于数组中的一组对象 V[1],…,V[n],若
V[1],…,V[i-1]已经通过指针 link,按其排序
码从小到大链接起来。现要插入 V[i],i = 2,
3,…,n,则必须在前面 i-1个链接起来的对象
当中,循链检测比较,找到 V[i] 应插入的位臵,
把 V[i]链入,并修改相应链接指针。从而得到
V[1],…,V[i]的一个通过指针排好的链表。
? 如此重复执行，直到把 V[n]也插入到链表中
排好序为止。
? 25 49 25* 16
08
0 1 2 3 4 5 6
i = 2
i = 3
21
初始
current pre i
current pre i
pre current i
i = 4
? 25 49 25* 16
08
0 1 2 3 4 5 6
i = 5
i = 6
21
pre current i
结果
pre current i
用于链表排序的静态链表的类定义
template <class Type> class staticlinklist;
template <class Type> class Element {
private:
Type key; //结点的排序码
int link; //结点的链接指针
public:
Element ( ), key(0),link (NULL) { }
Type getKey ( ) { return key; }
void setKey ( const Type x ) { key = x; }
int getLink ( ) { return link; }
void setLink ( const int l ) { link = l; }
}
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]; }
}
链表插入排序的算法
template <class Type>
int staticlinklis<Type>,,LinkedInsSort ( ) {
Vector[0].key = MaxNum;
Vector[0].link = 1; Vector[1].link = 0;
//元素 V[0]与 V[1]形成循环链表
for ( int i = 2; i <= CurrentSize; i++ ) {
int current = Vector[0].link; //检测指针
int pre = 0; //检测指针的前驱指针
while ( Vector[current].key <=
Vector[i].key ) { //找插入位置
pre = current; //pre跟上,current向 前走
? 使用链表插入排序,每插入一个对象,最大排
序码比较次数等于链表中已排好序的对象个
数,最小排序码比较次数为 1。故总的 排序码
比较次数最小 为 n-1,最大 为
current = Vector[current].link;
}
Vector[i].link = current; Vector[pre].link = i;
//在 pre与 current之间链入
}
}
2
)1(1
1
????
?
nnin
i
? 用链表插入排序时,对象移动次数为 0。但为
了实现链表插入,在每个对象中增加了一个
链域 link,并使用了 Vector[0]作为链表的表
头结点,用了 n 个附加域 和 一个附加对象 。
? 算法在 Vector[pre].key == Vector[i].key时,
将 Vector[i]插在 Vector[pre]的后面,所以,链
表插入排序方法是 稳定 的。
希尔排序 (Shell Sort)
? 希尔排序方法又称为缩小增量排序。该方法
的基本思想是, 设待排序对象序列有 n 个对
象,首先取一个整数 gap < n 作为间隔,将全
部对象分为 gap 个子序列,所有 距离为 gap
的对象放在 同一个子序列 中,在每一个子序
列中分别施行直接插入排序。然后缩小间隔
gap,例如取 gap = ?gap/2?，重复上述的子序
列划分和排序工作。直到最后取 gap == 1,
将所有对象放在同一个序列中排序为止。
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*
i = 1
08
49
Gap = 3
25 16
4925 16
08
49 25*
0821
2521 25* 16
21 25 4925*16 08
0 1 2 3 4 5
21
i = 2
08
49
Gap = 2
25
16
4916 25*
0821 25
4925*
08 16 21 25* 25
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
Gap = 1
2516 4925*
? 开始时 gap 的值较大,子序列中的对象较少,
排序速度较快 ; 随着排序进展,gap 值逐渐
变小,子序列中对象个数逐渐变多,由于前
面工作的基础,大多数对象已基本有序,所
以排序速度仍然很快。
希尔排序的算法
template <class Type>
void dataList<Type>,,ShellSort ( ) {
Element<Type> temp;
int gap = CurrentSize / 2; //gap是子序列间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < CurrentSize; i++) {
temp = Vector[i]; //直接插入排序
for ( int j = i; j >= gap; j -= gap )
if ( temp < Vector[j-gap] )
Vector[j] = Vector[j-gap];
else break;
Vector[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
? Gap的取法有多种。最初 shell 提出取 gap =
?n/2?,gap = ?gap/2?,直到 gap = 1。 knuth
提出取 gap = ?gap/3?+1。还有人提出都取
奇数为好，也有人提出各 gap 互质为好。
? 对特定的待排序对象序列，可以准确地估算
排序码的比较次数和对象移动次数 。
? 想要弄清排序码比较次数和对象移动次数
与增量选择之间的依赖关系, 并给出完整
的数学分析, 还没有人能够做到 。
? Knuth利用大量实验统计资料得出, 当 n
很大时, 排序码平均比较次数和对象平均
移动次数大约在 n1.25到 1.6n1.25的范围内 。
这是在利用直接插入排序作为子序列排序
方法的情况下得到的 。
交换排序 ( Exchange Sort )
? 基本方法是：设待排序对象序列中的对象个
数为 n。最多作 n-1 趟,i = 1,2,?,n-1 。
在第 i 趟中 从后向前, j = n-1,n-2,?,i，顺
次两两 比较 V[j-1].key和 V[j].key。 如果发生
逆序，则交换 V[j-1]和 V[j]。
基本思想是 两两比较待排序对象的排序码,如
果发生逆序 (即排列顺序与排序后的次序正好相
反 )，则交换之 。直到所有对象都排好序为止。
起泡排序 (Bubble Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
2516
25 16
08
49
Exchang=108
25*4921
Exchang=1
i = 2
i = 3
08 16 Exchang=125*2521
25*
0 1 2 3 4 5
i = 4 4916
Exchang=008
2521
起泡排序的算法
template <class Type>
void dataList<Type>,,BubbleSort ( ) {
int pass = 1; int exchange = 1;
while ( pass < CurrentSize && exchange ){
exchange = 0; //标志置为 0,假定未交换
for ( int j = CurrentSize-1; j >= pass; j-- )
if ( Vector[j-1] > Vector[j] ) { //逆序
Swap ( Vector[j-1],Vector[j] ); //交换
exchange = 1; //标志置为 1,有交换
}
pass++;
}
}
? 第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-1]
进行排序,结果 将该序列中排序码最小的对
象交换到序列的第一个位臵 (i-1),其它对象
也都向排序的最终位臵移动 。 在个别情形,
对象可能在排序中途向相反的方向移动 。
? 最多做 n-1趟起泡 就能把所有对象排好序 。
? 在对象的 初始排列已经按排序码从小到大排
好序 时,此算法 只执行一趟起泡,做 n-1次排
序码比较,不移动对象 。 这是最好的情形 。
? 最坏的情形是算法 执行 n-1趟起泡,第 i趟 (1?
i? n) 做 n- i 次排序码比较,执行 n-i 次对象
交换 。 这样在最坏情形下总的 排序码比较次
数 KCN和 对象移动次数 RMN为：
?
?
?
?
?
?
????
????
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninRM N
nninKCN
)()(
)()(
快速排序 (Quick Sort)
? 基本思想是任取 待排序对象序列中的某个对象
(例如取第一个对象 ) 作为基准,按照该对象的
排序码大小,将整个对象序列划分为左右两
个子序列,
? 起泡排序需要一个附加对象以实现对象值的
对换。
? 起泡排序是一个 稳定 的排序方法。
? 左侧子序列中所有对象的排序码都小于
或等于基准对象的排序码
? 右侧子序列中所有对象的排序码都大于
基准对象的排序码
? 基准对象则排在这两个子序列中间 (这也是
该对象最终应安放的位臵 )。
? 然后分别对这两个子序列重复施行上述方
法，直到所有的对象都排在相应位臵上为
止。
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
算法描述
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25*16
2516
08
49
pivot
08
25 4921i = 2
i = 3
08 16 2525*21
pivotpivot
pivot
21 25 49 25* 16 08
0 1 2 3 4 5
25*
i = 1
划分
2516
2516
08
49
pivotpos
08
25* 49
08 16 25* 2521
pivotpos
21
比较 4次
交换 25,16
i
i
pivotpos
21
比较 1次
交换 49,08
49
low pivotpos
交换 21,08
快速排序的算法
template <class Type>
void dataList<Type>,,QuickSort ( const int left,
const int right ) {
//在序列 left?right 中递归地进行快速排序
if ( left < right) {
int pivotpos = Partition ( left,right ); //划分
//对左序列同样处理
QuickSort ( left,pivotpos-1);
//对右序列同样处理
QuickSort ( pivotpos+1,right );
}
}
template <class Type> int dataList<Type>,,
Partition ( const int low,const int high ) {
int pivotpos = low; //基准位置
Element<Type> pivot = Vector[low];
for ( int i = low+1; i <= high; i++ )
if ( Vector[i] < pivot ) {
pivotpos++;
if ( pivotpos != i )
Swap ( Vector[pivotpos],Vector[i] );
} //小于基准对象的交换到区间的左侧去
Swap ( Vector[low],Vector[pivotpos] );
return pivotpos;
}
? 算法 quicksort是一个递归的算法,其递归树
如图所示。
? 算法 partition利用 序列第一个对象作为基准,
将整个序列划分为左右两个子序列 。算法
中执行了一个循环,只要是排序码小于基准
对象排序码的对象都移到序列左侧,最后基
准对象安放到位,函数返回其位臵。
21
25*
25
49
08
16
算法分析
? 从快速排序算法的递归树可知,快速排序的
趟数取决于递归树的高度 。
? 如果每次划分对一个对象定位后,该对象的
左侧子序列与右侧子序列的长度相同,则下
一步将是对两个长度减半的子序列进行排序,
这是最理想的情况。
? 在 n个元素的序列中,对一个对象定位所需
时间为 O(n)。 若设 t (n) 是对 n 个元素的序
列进行排序所需的时间,而且每次对一个对
象正确定位后,正好把序列划分为长度相等
的两个子序列,此时,总的计算时间为：
T(n) ? cn + 2T(n/2 ) // c 是一个常数
? cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)
? 2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8)
………
? cn log2n + nT(1) = O(n log2n )
? 可以证明,函数 quicksort的平均计算时间也
是 O(nlog2n)。 实验结果表明, 就平均计算时
间而言,快速排序是所有内排序方法中最好
的一个 。
? 快速排序是递归的, 需要有一个栈存放每层
递归调用时的指针和参数 。
? 最大递归调用层次数与递归树的高度一致,
理想情况为 ?log2(n+1)? 。 因此, 要求存储
开销为 O(log2n)。
? 在最坏的情况,即 待排序对象序列已经按其
排序码从小到大排好序 的情况下,其 递归树
成为单支树,每次划分只得到一个比上一次
少一个对象的子序列 。 必须经过 n-1 趟才
能把所有对象定位,而且 第 i 趟需要经过 n-
i 次排序码比较 才能找到第 i 个对象的安放
位臵, 总的排序码比较次数将达到
212
1 21
1
nnninn
i
?????
?
?
)()(
用第一个对象作为基准对象
快速排序退化的例子
08 16 21 25 25* 49 08
0 1 2 3 4 5 pivot
初始
16 21 25 25* 4908 16
21 25 25* 49 2108 16
2525 25* 4908 16 21
25* 49 25*08 16 21 25
4908 16 21 25 25*
i = 1
i = 2
i = 3
i = 4
i = 5
用居中排序码对象作为基准对象
08 16 21 25 25* 49
0 1 2 3 4 5 pivot
21初始
08 16 21 25 25* 49 08 25*
08 16 21 25 25* 49
i = 1
i = 2
? 其 排序速度退化到简单排序的水平,比直接插
入排序还慢 。占用附加存储 (栈 )将达到 O(n)。
? 改进办法, 取每个待排序对象序列的 第一个对
象, 最后一个对象 和 位臵接近正中的 3 个对
象，取其排序码居中者作为基准对象。
? 快速排序是一种 不稳定 的排序方法 。
? 对于 n 较大的平均情况而言,快速排序是
,快速, 的,但是当 n 很小时,这种排序方
法往往比其它简单排序方法还要慢 。
Type mid ( Type a,Type b,Type c ) {
Type first = a,second; //first记录最小
if ( b < first ) { second = first; first = b; }
else second = b; //second记录次小
if ( c < first ) { second = first; first = c; }
else if ( c < second ) second = c;
return second;
}
基本思想是, 每一趟 (例如第 i 趟,i = 0,1,…,
n-2) 在后面 n-i 个待排序对象中选出排序码
最小的对象,作为有序对象序列的第 i 个对象。
待到第 n-2 趟作完,待排序对象只剩下 1个,就
不用再选了。
选择排序
② 若它不是这组对象中的第一个对象,则
将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码
的对象 。 在剩下的对象 V[i+1]～ V[n-1]中
重复执行第 ①, ② 步,直到剩余对象只有
一个为止 。
? 直接选择排序是一种简单的排序方法,它的
基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最
小排序码的对象；
直接选择排序 (Select Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 0
49
25 16
25 16
08
49
08
25*49 21i = 1
i = 2
08 16
25* 25 21
初始
最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
4925*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3
08 16 2521
最小者 25*
无交换
最小者 25
无交换252116
08
各趟排序后的结果
直接选择排序的算法
template <class Type>
void dataList <Type>,,SelectSort ( ) {
for ( int i = 0; i < CurrentSize-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < CurrentSize; j++)
if ( Vector[j] < Vector[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位置
Swap ( Vector[i],Vector[k] );
}
}
0 1 2 3 4 5
49
1608 25*49 21
08 25*
25
21
i =1时选择排序的过程
i k j
4925
08 25* 16 21
i k j
49 ? 25
25* ? 25
1625
i k j 16 < 25
4925
08 25* 16 21
0 1 2 3 4 5
i k j 21 ? 16
k 指示当前序列中最小者
? 直接选择排序的 排序码比较次数 KCN 与对
象的初始排列无关。设整个待排序对象序列
有 n 个对象,则第 i 趟选择具有最小排序码
对象所需的比较次数 总是 n-i-1次 。总的排
序码比较次数为
?
?
?
????? 2
0 2
11n
i
nninKC N )()(
? 对象的移动次数与对象序列的初始排列有
关 。当这组对象的初始状态是按其排序码
从小到大有序的时候,对象的移动次数
RMN = 0，达到最少。
? 最坏情况是每一趟都要进行交换,总的对
象移动次数 为 RMN = 3(n-1)。
? 直接选择排序是一种 不稳定 的排序方法。
锦标赛排序 (Tournament Tree Sort)
? 它的思想与体育比赛时的淘汰赛类似。首
先取得 n 个对象的排序码,进行 两两比较,
得到 ?n/2?个 比较的优胜者 (排序码小者 ),
作为第一步比较的结果保留下来。然后对
这 ?n/2?个对象再进行排序码的两两比
较,…,如此重复,直到选出一个排序码最小
的对象为止。
? 在图例中,最下面是对象排列的初始状态,
相当于一棵满二叉树的叶结点,它存放的
是 所有参加排序的对象的排序码 。
? 如果 n 不是 2 的 k 次幂, 则让叶结点数补足
到满足 2k-1 < n ? 2k的 2k个 。 叶结点上面一
层的非叶结点是叶结点排序码两两比较的结
果 。 最顶层是树的根 。
08
Winner
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
胜者树的概念
? 每次两两比较的结果是把 排序码小者作为
优胜者上升到双亲结点, 称这种比赛树为
胜者树 。
? 位于 最底层的叶结点 叫做胜者树的 外结点,
非叶结点 称为胜者树的 内结点 。 每个结点
除了存放对象的排序码 data 外, 还存放了
此对象是否要参选的标志 Active 和此对象
在满二叉树中的序号 index。
? 胜者树最顶层是树的 根,表示 最后选择出
来的具有最小排序码的对象 。
08
Winner (胜者 )
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
形成初始胜者树（最小排序码上升到根）
a[0]
排序码比较次数, 6
VS,VS,VS.
VS.
VS.
VS.
up
up 对手不参选
VS,比较
16
Winner (胜者 )
21 16
16 6325*21
21 25 49 25* 16 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出冠军并调整胜者树后树的状态
a[1]
排序码比较次数, 2
VS.
VS.
up
up 对手不参选
VS,比较
21
Winner (胜者 )
21 63
6325*21
21 25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出亚军并调整胜者树后树的状态
a[2]
排序码比较次数, 1
VS.
up
up 对手不参选
VS,比较
25
Winner (胜者 )
25 63
6325*25
25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第三名并调整胜者树后树的状态
a[3]
排序码比较次数, 2
VS.
VS.
up
up 对手不参选
VS,比较
25*
Winner (胜者 )
25* 63
6325*
49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第四名并调整胜者树后树的状态
a[4]
排序码比较次数, 1
VS.
up
up 对手不参选
VS,比较
49
Winner (胜者 )
49 63
6349
49 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第五名并调整胜者树后树的状态
a[5]
排序码比较次数, 1
VS.
up
up
up 对手不参选
VS,比较
63
Winner (胜者 )
63
63
63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
全部比赛结果输出时树的状态
a[6]
排序码比较次数, 0
up
up 对手不参选
VS,比较
? 锦标赛排序构成的胜者树是满的完全二叉树,
其深度为 ?log2n?,其中 n 为待排序元素个数。
? 除 第一次选择具有最小排序码的对象 需要进
行 n-1 次 排序码比较 外,重构胜者树选择具
有次小、再次小排序码对象所需的 排序码比
较次数 均为 O(log2n)。 总排序码比较次数 为
O(nlog2n)。
? 对象的移动次数不超过排序码的比较次数,
所以锦标赛排序总时间复杂度为 O(nlog2n)。
? 这种排序方法虽然减少了许多排序时间,但
是使用了较多的附加存储。
? 如果有 n 个对象，必须使用至少 2n-1 个结
点来存放胜者树。最多需要找到满足
2k-1 < n ? 2k
的 k，使用 2*2k-1 个结点。
? 每个结点包括 排序码, 结点序号 和 比较标志
三种信息。
? 锦标赛排序是一个 稳定 的排序方法 。
? 利用堆及其运算,可以很容易地实现选择排
序的思路。
? 堆排序分为两个步骤
? 根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
? 通过一系列的对象交换和重新调整堆进
行排序。
堆排序 (Heap Sort)
建立初始的最大堆
21
25
25*
49
16 08
0
1 2
3 4 5
i 21
25
25* 16
49
08
0
2
543
1
i
21 25 49 25* 16 08
初始排序码集合
21 25 49 25* 16 08
i = 2 时的局部调整
21
25
25*
49
16 08
0
1 2
3 4 5
i
49
25
25* 16
21
08
0
2
543
1
21 25 49 25* 16 08 49 25 21 25* 16 08
i = 0 时的局部调整
形成最大堆
i = 1 时的局部调整
最大堆的向下调整算法
template <class Type> void MaxHeap<Type>,:
FilterDown ( const int i,const int EndOfHeap ) {
int current = i; int child = 2*i+1;
Type temp = heap[i];
while ( child <= EndOfHeap ) { //最后位置
if ( child +1 < EndOfHeap &&
heap[child] < heap[child+1] )
child = child+1; //选两子女的大者
if ( temp >= heap[child] )
break; //temp排序码大,不做调整
else {
heap[current] = heap[child]; //大 子女上移
current = child; //向下继续调整
child = 2*child+1;
}
}
heap[current] = temp; //回放到合适位置
}
将表转换成堆
for ( int i = ( CurrentSize-2) / 2 ; i >= 0; i-- )
FilterDown ( i,CurrentSize-1 );
基于初始堆进行堆排序
? 最大堆堆顶 V[0]具有最大的排序码,将 V[0]与
V[n-1]对调,把具有最大排序码的对象交换
到最后,再对前面的 n-1个对象,使用堆的调
整算法 FilterDown(0,n-2),重新建立最大堆,
具有次最大排序码的对象又上浮到 V[0]位臵。
? 再 对调 V[0]和 V[n-2],调用 FilterDown(0,n-3),
对前 n-2个对象重新调整,… 。
? 如此反复执行，最后得到全部排序好的对象
序列。这个算法即堆排序算法，其细节在下
面的程序中给出。
49
25
25*
21
16 08
0
1 2
3 4 5
08
25
25* 16
21
49
0
2
543
1
49 25 21 25* 16 08 08 25 21 25* 16 49
交换 0 号与 5 号对象,
5 号对象就位
初始最大堆
25
25*
08
21
16 49
0
1 2
3 4 5
16
25*
08 25
21
49
0
2
543
1
25 25* 21 08 16 49 16 25* 21 08 25 49
交换 0 号与 4 号对象,
4 号对象就位
从 0 号到 4 号 重新
调整为最大堆
25*
16
08
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
25* 16 21 08 25 49 08 16 21 25* 25 49
交换 0 号与 3 号对象,
3 号对象就位
从 0 号到 3 号 重新
调整为最大堆
21
16
25*
08
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
21 16 08 25* 25 49 08 16 21 25* 25 49
交换 0 号与 2 号对象,
2 号对象就位
从 0 号到 2 号 重新
调整为最大堆
16
08
25*
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
16 08 21 25* 25 49 08 16 21 25* 25 49
交换 0 号与 1 号对象,
1 号对象就位
从 0 号到 1 号 重新
调整为最大堆
堆排序的算法
template <class Type> void MaxHeap<Type>,:
HeapSort ( ) {
//对表 heap[0]到 heap[n-1]进行排序,使得表中
//各 个对象按其排序码非递减有序 。
for ( int i = ( CurrentSize-2 ) / 2; i >= 0; i-- )
FilterDown ( i,CurrentSize-1 ); //初始堆
for ( i = CurrentSize-1; i >= 1; i--) {
Swap ( heap[0],heap[i] ); //交换
FilterDown ( 0,i-1 ); //重建最大堆
}
}
? 若设堆中有 n 个结点,且 2k-1 ? n ? 2k,则对
应的完全二叉树有 k 层 。在第 i 层上的结点
数 ? 2i (i = 0,1,…,k-1)。 在第一个形成初
始堆的 for 循环中对每一个非叶结点调用了
一次堆调整算法 FilterDown( ),因此该循环
所用的计算时间为：
? 其中,i 是层序号,2i 是第 i 层的最大结点数,
(k-i-1)是第 i 层结点能够移动的最大距离。
? ??
?
?
????
2
0
22
k
i
i ik 1
? 第二个 for循环中调用了 n-1次 FilterDown( )算
法,该循环的计算时间为 O(nlog2n)。因此,堆
排序的时间复杂性为 O(nlog2n)。
? 该算法的附加存储主要是在第二个 for循环中
用来执行对象交换时所用的一个临时对象。
因此，该算法的空间复杂性为 O(1)。
? 堆排序是一个 不稳定 的排序方法 。
n
j
n
j
jik
k
j
k
j
jj
k
k
j
jk
k
i
i
4?????
????????
? ?
??
?
?
?
?
?
?
?
??
?
?
1
1
1
1
1
1
1
1
2
0
2
2
2
22
22122 )(
归并排序 (Merge Sort)
? 归并，是将两个或两个以上的有序表合并成
一个新的有序表。
? 对象序列 initList中两个有序表 V[l] …V[ m]和
V[m+1] …V[ n]。它们可归并成一个有序表,
存于另一对象序列 mergedList的 V[l] …V[ n]
中。
? 这种归并方法称为 两路归并 (2-way merging)。
? 设变量 i 和 j 分别是表 V[l] …V[ m]和
V[m+1] …V[ n]的当前检测指针。变量 k 是存
放指针。
归并
08 21 25 25* 49 62 72 93 16 37 54
left mid mid+1 right
initList
i j
08 16 21 25 25* 37 49 54 62 72 93
left right
k
mergeList
? 当 i 和 j 都在两个表的表长内变化时,根据对
应项的排序码的大小,依次把排序码小的对
象排放到新表 k 所指位臵 中；
? 当 i 与 j 中有一个已经超出表长时，将另一
个表中的剩余部分照抄到新表中。
迭代的归并排序算法
? 迭代的归并排序算法就是利用两路归并过程
进行排序的。其基本思想是：
? 假设初始对象序列有 n 个对象,首先把它看
成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到 ?n / 2? 个长度为 2 的归
并项 (如果 n 为奇数，则最后一个有序子序
列的长度为 1)；再做两两归并,…,如此重
复,最后得到一个长度为 n 的有序序列 。
两路归并算法
template <class Type> void dataList<Type>,:
merge ( dataList <Type> & mergedList,const
int left,const int mid,const int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较
if ( Vector[i] <= Vector[j] ) {
mergedList.Vector[k] = Vector[i];
i++; k++;
}
else {
mergedList.Vector[k] = Vector[j];
j++; k++;
}
if ( i <= mid )
for ( int n1 = k,n2 = i; n2 <= mid;
n1++,n2++ )
mergedList.Vector[n1] = Vector[n2];
else
for ( int n1 = k,n2 = j; n2 <= right;
n1++,n2++)
mergedList.Vector[n1] = Vector[n2];
}
一趟归并排序的情形
? 设 initList.Vector[0]到 initList.Vector[n-1]中
n 个对象 已经分为一些长度为 len 的归并项,
将这些归并项两两归并,归并成长度为 2len
的归并项,结果放到 mergedList.Vector中。
? 如果 n不是 2len的整数倍,则一趟归并到最后,
可能遇到两种情形：
? 剩下一个长度为 len的归并项和另一个长
度不足 len的归并项,可用 merge算法 将它
们归并成一个长度小于 2len 的归并项。
? 只剩下一个归并项，其长度小于或等于
len,将它直接抄到 MergedList.Vector中。
template <class Type> void datalist<Type>,:
MergePass ( dataList<Type> & mergedList,
const int len ) {
int i = 0;
while (i+2*len <= CurrentSize-1) {
merge(mergedList,i,i+len-1,i+2*len-1);
i += 2 * len; //循环两两归并
}
if ( i+len <= CurrentSize-1 )
merge(mergedList,i,i+len-1,CurrentSize-1);
else for ( int j = i; j <= CurrentSize-1; j++)
mergedList.Vector[j] = Vector[j];
}
迭代的归并排序算法
21 25
25*
25* 93 62 72 08 37 16 5449
21 25 49 62 93 08 72 16 37 54
21 25 25* 49 08 62 72 93 16 37 54
08
08
21
16
25
21
25*
25
49
25*
62
37
72
49
93
54
16 37 54
62 72 93
len=1
len=2
len=4
len=8
len=16
(两路 )归并排序的主算法
template <class Type>
void dataList<Type>,,MergeSort ( ) {
//按对象排序码非递减的顺序对表中对象排序
dataList<Type> & tempList ( MaxSize );
int len = 1;
while ( len < CurrentSize ) {
MergePass ( tempList,len ); len *= 2;
tempList.MergePass ( this,len ); len *= 2;
}
delete [ ] tempList;
}
? 在迭代的归并排序算法中,函数 MergePass( )
做一趟两路归并排序,要调用 merge ( )函数
?n/(2*len)? ? O(n/len) 次,函数 MergeSort( )调
用 MergePass( )正好 ?log2n? 次,而每次 merge( )
要执行比较 O(len)次,所以算法总的时间复杂
度为 O(nlog2n)。
? 归并排序占用附加存储较多,需要另外一个与
原待排序对象数组同样大小的辅助数组 。 这
是这个算法的缺点 。
? 归并排序是一个 稳定 的排序方法 。
递归的表归并排序
? 与快速排序类似，归并排序也可以利用划分
为子序列的方法递归实现。
? 在递归的归并排序方法中，首先要 把整个待
排序序列划分为两个长度大致相等的部分,
分别称之为 左子表 和 右子表 。 对这些子表分
别递归地进行排序,然后再把 排好序的两个
子表进行归并 。
? 图示：待排序对象序列的排序码为 { 21,25,
49,25*,16,08 }，先是进行子表划分，待到子
表中只有一个对象时递归到底。再是实施归
并，逐步退出递归调用的过程。
21 25 49 25* 16 08
21 25 49 25* 16 08
21
25 49
25 49
21
25* 16 08
25* 16 08
21 25 49 25* 16 08
16 0825* 25 4921
递
归
21 25* 16 08 49 25
25* 16 0821 25 49
回
推
静态链表的两路归并算法
template <class Type>
int staticlinkList<Type>,,ListMerge (
const int start1,const int start2 ) {
int k = 0,i = start1,j = start2;
while ( i && j )
if ( Vector[i].key <= Vector[j].key ) {
Vector[k].link = i; k = i;
i = Vector[i].link;
}
else {
Vector[k].link = j; k = j;
j = Vector[j].link;
}
if ( i == 0 ) Vector[k].link = j;
else Vector[k].link = i;
return Vector[0].link;
}
递归的归并排序算法
template <class Type>
int staticlinkList<Type>,,MergeSort (
const int left,const int right ) {
if ( left >= right ) return left;
int mid = ( left + right ) / 2;
return ListMerge (
MergeSort ( left,mid ),
MegerSort ( mid+1,right ) );
//以中点 mid为界,分别对左半部和右半部进
//行表归并排序
}
? 链表的归并排序方法的 递归深度 为 O(log2n)，
对象排序码的比较次数为 O(nlog2n)。
? 链表的归并排序方法是一种 稳定 的排序方法。
基数排序 (Radix Sort)
? 基数排序是采用,分配,与,收集,的办法，
用对多排序码进行排序的思想实现对单排序
码进行排序的方法。
多排序码排序
? 以扑克牌排序为例 。 每张扑克牌有两个, 排
序码,, 花色 和 面值 。 其有序关系为：
? 花色,???????
? 面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 <
J < Q < K < A
? 如果我们把所有扑克牌排成以下次序：
? 2,…,? A,? 2,…,? A,? 2,…,? A,?
2,…,? A
? 这就是 多排序码排序 。排序后形成的有序序
列叫做词典有序序列。
? 对于上例两排序码的排序，可以先按花色排
序，之后再按面值排序；也可以先按面值排
序，再按花色排序。
? 一般情况下，假定有一个 n 个对象的序列
{V0,V1,…,V n-1 }，且每个对象 Vi 中含有 d 个
排序码
? 如果对于序列中任意两个对象 Vi 和 Vj (0 ? i <
j ? n-1 ) 都满足：
? 则称序列对排序码 (K1,K2,…,Kd) 有序。其
中,K1 称为最高位排序码,Kd 称为最低位排
序码。
? 如果排序码是由 多个数据项组成的数据项组,
则依据它进行排序时 就需要利用多排序码排
序 。
? 实现多排序码排序有两种常用的方法
? ?diii KKK,,,?21
? ? ? ?djjjdiii KKKKKK,,,,,,?? 2121 ?
? 最高位优先 MSD ( Most Significant Digit
first )
? 最低位优先 LSD ( Least Significant Digit
first)
? 最高位优先法 通常是一个递归的过程：
? 先根据 最高位排序码 K1排序,得到若干对
象组,对象组中各对象都有相同 排序码 K1。
? 再分别对每组中对象根据 排序码 K2 进行
排序,按 K2 值的不同,再分成若干个更小
的子组,每个子组中的对象具有相同的 K1
和 K2值。
? 依此重复,直到对 排序码 Kd完成排序为止 。
? 最后,把所有子组中的对象依次连接起来,
就得到一个有序的对象序列 。
? 最低位优先法 首先依据 最低位排序码 Kd对所
有对象进行一趟排序, 再依据 次低位排序码
Kd-1对上一趟排序的结果再排序, 依次重复,
直到依据 排序码 K1最后一趟排序完成, 就可
以得到一个有序的序列 。 使用这种排序方法
对每一个排序码进行排序时, 不需要再分组,
而是整个对象组都参加排序 。
? 基数排序是典型的 LSD排序方法,利用, 分配,
和, 收集, 对单排序码进行排序 。 在这种方
法中, 把单排序码 Ki 看成是一个 d元组：
? 其中的每一个分量 ( 1? j ? d ) 也可看成是
一个排序码 。
? ?diii KKK,,,?21
? LSD和 MSD方法也可应用于对一个排序码进
行的排序。此时可将 单排序码 Ki 看作是一个
子排序码组：
? ?diii KKK,,,?21
链式基数排序
jiK
jiK
? 分量 (1 ? j ? d) 有 radix种取值,称 radix为
基数 。 例如,排序码 984可以看成是一个 3元
组 (9,8,4),每一位有 0,1,…,9 等 10种取值,
基数 radix = 10。 排序码 ‘ data’可以看成是
一个 4元组 (d,a,t,a),每一位有 ‘ a’,‘b’,…,
‘z’等 26种取值, radix = 26。
? 针对 d元组中的每一位分量,把对象序列中
的所有对象,按 的取值, 先, 分配, 到 rd
个队列中去 。 然后再按各队列的顺序, 依
次把对象从队列中, 收集, 起来, 这样所
有对象按取值 排序完成 。
jiK
jiK
jiK
? 如果对于所有对象的排序码 K0,K1,…,Kn-1,
依次对各位的分量,让 j = d,d-1,…,10,分
别用,分配,、,收集,的运算 逐趟进行排
序,在最后一趟,分配,、,收集, 完成
后,所有对象就按其排序码的值从小到大排
好序了 。
? 各队列采用链式队列结构,分配到同一队列
的排序码用链接指针链接起来。每一队列设
臵两 个队列指针,int front [radix]指示队
头,int rear [radix] 指向队尾。
? 为了有效地存储和重排 n 个待排序对象，以
静态链表作为它们的存储结构。
基数排序的“分配”与“收集”过程 第
一趟614 921 485 637738 101 215 530 790 306
第一趟分配（按最低位 i = 3 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738921 485 637
101 215
530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第一趟收集
530 790 921 101 614 485 215 306 637 738
基数排序的“分配”与“收集”过程 第
二趟 614921 485 637 738101 215530 790 306
第二趟分配（按次低位 i = 2 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614
738
921 485
637
101
215
530 790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第二趟收集
530 790921101 614 485215306 637 738
基数排序的“分配”与“收集”过程 第
三趟 614 921 485637 738101 215 530 790306
第三趟分配（按最高位 i = 1 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738 921485
637
101 215 530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第三趟收集
530 790 921101 614485215 306 637 738
链表基数排序
template <class Type>
void staticlinkList <Type>,,RadixSort (
const int d,const int radix ) {
int rear[radix],front[radix];
for ( int i = 1; i < CurrentSize; i++ )
Vector[i].link = i+1;
Vector[n].link = 0; //静态链表初始化
int current = 1; //链表扫描指针
for ( i = d-1; i >= 0; i-- ) { //d趟分配,收集
for ( int j = 0; j < radix; j++ ) front[j] = 0;
while ( current != 0 ) { //逐个对象分配
int k = Vector[current].key[i];
//取当前对象排序码的第 i 位
if ( front[k] == 0) //原链表为空
front[k] = current; //队头链入
else //原链表非空,链尾链入
Vector[rear[k]].link = current;
rear[k] = current; //修改链尾指针
current = Vector[current].link; //下一对象
}
j = 0; //从 0号队列开始收集
while ( front[j] == 0 ) j++; //空队列跳过
Vector[0].link = current = front[j]; //新链头
int last = rear[j]; //新链尾
for ( k = j+1; k < radix; k++)
//逐个队列链接
if ( front[k] ) {
Vector[last].link = front[k];
last = rear[k];
}
Vector[last].link = 0; //链收尾
} //下一趟
}
? 若每个排序码有 d 位,需要重复执行 d 趟
,分配, 与, 收集, 。 每趟对 n 个对象进行
,分配,, 对 radix个队列进行, 收集, 。
总时间复杂度为 O ( d ( n+radix ) )。
? 若 基数 radix相同,对于 对象个数较多 而 排序
码位数较少 的情况,使用链式基数排序较好 。
? 基数排序需要增加 n+2radix个附加链接指针 。
? 基数排序是 稳定 的排序方法 。
各种排序方法的比较
比较次数 移动次数 附加存储排 序 方 法
最好 最
差
最好 最
差
稳定
性
最好 最
差
直接插入排序 n n
2
0 n
2
? 1
折半插入排序 n l og
2
n 0 n
2
? 1
起泡排序
n n
2
0 n
2
? 1
快速排序 n l og
2
n n
2
n l og
2
n n
2
? l og
2
n n
2
简单选择排序 n
2
0 n ? 1
锦标赛排序 n l og
2
n n l og
2
n ? n
堆排序 n l og
2
n n l og
2
n ? 1
归并排序
n l og
2
n n l og
2
n ? n
外排序
? 当对象以文件形式存放于磁盘上的时候,通
常是按物理块存储的。
当待排序的对象数目特别多时，在内存中不
能一次处理。必须把它们以文件的形式存放于
外存，排序时再把它们一部分一部分调入内存
进行处理。这样，在排序过程中必须不断地在
内存与外存之间传送数据。 这种基于外部存储
设备（或文件）的排序技术就是外排序 。
外排序的基本过程
? 物理块 也叫做 页块 。每个页块可存放几个对
象。操作系统 按页块对磁盘信息进行读写 。
? 磁盘通常是指 由若干片磁盘组成的磁盘组,
各个盘片安装在同一主轴上高速旋转。各个
盘面上半径相同的磁道构成了柱面。各盘面
设臵一个读写磁头，它们装在同一动臂上，
可以径向从一个柱面移到另一个柱面上。
? 为了访问某一页块,先寻找柱面, 移动动臂使
读写磁头移到指定柱面上, 寻查 (seek)。再根
据磁道号 (盘面号 )选择相应读写磁头,等待指
定页块转到读写磁头下, 等待 (latency)。 在
磁盘组上存取一个页块的时间：
? 基于磁盘进行的排序多使用归并排序方法。
其排序过程主要分为两个阶段：
① 建立 用于外排序的内存缓冲区 。根据它们
的大小 将输入文件划分为若干段,用某种
内排序方法对各段进行排序。经过排序的
段叫做 初始归并段 或初始顺串 (Run)。当
它们生成后就被写到外存中去。
② 仿照归并树模式,把 ① 生成的初始归并段
加以归并,一趟趟地 扩大归并段 和 减少归
并段个数,直到最后归并成一个大归并段
(有序文件 )为止。
tio＝ tseek＋ tlatency＋ trw
? 示例：设有一个包含 4500个对象 的输入文件。
现用一台其内存 至多可容纳 750个对象 的计算
机对该文件进行排序。输入文件放在磁盘上,
磁盘每个页块可容纳 250个对象,这样全部对
象可存储在 4500 / 250＝ 18 个页块中。输出
文件也放在磁盘上,用以存放归并结果。
? 由于内存中可用于排序的存储区域能容纳 750
个对象,因此 内存中恰好能存 3个页块 的对象。
? 在外排序一开始,把 18块对象,每 3块一组,读
入内存。利用某种内排序方法进行内排序,形
成初始归并段,再写回外存。总共可得到 6个
初始归并段。然后一趟一趟进行归并排序。
两路归并排序的归并树
R1 750 R2 750 R3 750 R4 750 R5 750 R6 750
初始
归并段
R12 1500 R34 1500 R56 1500
R1234 3000
R123456 4500
第一趟
归并结果
第二趟
归并结果
第三趟
归并结果
? 若把内存区域等份地分为 3 个缓冲区。其中
的两个为输入缓冲区,一个为输出缓冲区,可
以在内存中利用简单 2 路归并函数 merge( )
实现 2 路归并。
? 首先,从参加归并排序的两个输入归并段 R1
和 R2 中分别读入一块,放在 输入缓冲区 1和
输入缓冲区 2中。然后在内存中进行 2 路归
并，归并结果顺序存放到 输出缓冲区 中。
输入缓冲区 2
输入缓冲区 1
输出缓冲区
? 若总对象个数为 n，磁盘上每个页块可容纳
b 个对象，内存缓冲区可容纳 i 个页块，则
每个 初始归并段长度 为 len = i * b，可生成
m = ?n / len?个 等长的初始归并段 。
? 在做 2 路归并排序时,第一趟从 m 个初始归
并段得到 ?m/2?个归并段,以后各趟将从 l (l
>1) 个归并段得到 ?l/2?个归并段 。总归并趟
数等于 归并树的高度 ?log2m?。
? 估计 2 路归并排序时间 tES 的上界为：
tES = m*tIS + d*tIO + S*u*tmg
? 对 4500 个对象 进行排序的例子,各种操作的
计算时间如下：
? 读 18 个输入块,内部排序 6段,写 18个输
出块 ＝ 6 tIS＋ 36 tIO
? 成对归并初始归并段 R1～ R6
＝ 36 tIO＋ 4500 tmg
? 归并两个具有 1500 个对象的归并段 R12
和 R34
＝ 24 tIO＋ 3000 tmg
? 最后将 R1234 和 R56 归并成一个归并段
＝ 36 tIO＋ 4500 tmg
? 合计 tES＝ 6 tIS＋ 132 tIO＋ 12000 tmg
? 由于 tIO=tseek+tlatency+trw,其中,tseek和 tlatency是
机械动作, 而 trw,tIS,tmg是电子线路的动作,
所以 tIO远远大于 tIS和 tmg。 想要提高外排序的
速度, 应着眼于减少 d。
? 若对相同数目的对象, 在同样页块大小的情
况下做 3 路归并或做 6 路归并 (当然,内存缓
冲区的数目也要变化 ),则可做大致比较：
归并路数 k 总读写磁盘次数 d 归并趟数 S
2 132 3
3 108 2
6 72 1
? 增大归并路数,可减少归并趟数,从而减少总
读写磁盘次数 d。
? 对 m 个初始归并段,做 k 路平衡归并,归并树
可用 正则 k 叉树 (即只有度为 k 与度为 0的结
点的 k 叉树 ) 来表示。
? 第一趟可将 m 个初始归并段归并为 l = ?m/k?
个归并段，以后每一趟归并将 l 个归并段归
并成 l = ?l / k?个归并段，直到最后形成一个
大的归并段为止。树的高度＝ ?logkm?＝ 归
并趟数 S。
k路平衡归并 (k-way Balanced merging)
? 做 k 路平衡归并时,如果有 m 个初始归并段,
则相应的归并树有 ?logkm?+1 层,需要归并
?logkm?趟。下图给出对有 36 个初始归并段
的文件做 6 路平衡归并时的归并树。
? 做内部 k 路归并时,在 k 个对象中选择最小
者, 需要顺序比较 k-1 次 。 每趟归并 u 个对
象需要做 (u-1)*(k-1)次比较,S 趟归并总共需
要的比较次数为,
S*(u-1)*(k-1) = ?logkm?* (u-1) * (k-1)
= ?log2m?* (u-1) * (k-1) / ?log2k?
? 在初始归并段个数 m 与对象个数 u 一定时,
?log2m?*(u-1) = const,而 (k-1) / ?log2k?在 k
增大时趋于无穷大。因此,增大归并路数 k,
会使得内部归并的时间增大。
? 使用,败者树,从 k 个归并段中选最小者,当
k 较大时 (k ? 6)，选出排序码最小的对象只需
比较 ?log2k?次。
S*(u-1)*?log2k?= ?logkm? * (u-1) * ?log2k?
= ?log2m?* (u-1) * ?log2k?/ ?log2k?
= ?log2m?* (u-1)
? 排序码比较次数与 k 无关,总的内部归并时间
不会随 k 的增大而增大 。
? 下面讨论利用败者树在 k 个输入归并段中选择
最小者，实现归并排序的方法。
? 败者树是一棵 正则的完全二叉树 。其中
? 每个叶结点存放各归并段在归并过程中当
前参加比较的对象；
? 每个非叶结点记忆它两个子女结点中对象
排序码小的结点 (即败者 )；
? 因此,根结点中记忆树中当前对象排序码最
小的结点 (最小对象 )。
? 败者树与胜者树的区别在于一个选择了败者
(排序码大者 ),一个选择了胜者 (排序码小者 )。
? 示例：设有 5 个初始归并段,它们中各对象
的排序码分别是：
Run0,{17,21,∞}
Run1,{05,44,∞}
Run2,{10,12,∞}
Run3,{29,32,∞}
Run4,{15,56,∞}
29
32
?
15
56
?
17
21
?
05
44
?
10
12
?
15
100517
29
3
0 2
4
1
k3 k4
k0 k1 k2
Run3 Run4
Run0 Run1 Run2
ls1
ls0
ls2
ls4
ls3
冠军 (最小对象 ),
输出段 1当前对象
选中
输出段 1最小对象，
段 1下一对象参选，
调整败者树
29
32
?
15
56
?
17
21
?
05
44
?
10
12
?
15
104417
29
3
0 1
4
2
k3 k4
k0 k1 k2
Run3 Run4
Run0 Run1 Run2
ls1
ls0
ls2
ls4
ls3
次最小对象
选中
? 败者树的高度为 ?log2k?，在每次调整,找下
一个具有最小排序码对象时,最多做 ?log2k?
次排序码比较。
? 在内存中应 为每一个归并段分配一个输入缓
冲区,其 大小应能容纳一个页块的对象,编号
与归并段号一致 。每个输入缓冲区应有一个
指针,指示当前参加归并的对象。
? 在内存中还应设立 一个输出缓冲区,其大小
相当于一个页块大小。它也有一个缓冲区指
针,指示当前可存放结果对象的位臵。每当
一个对象 i 被选出,就执行 OutputRecord(i)操
作,将对象存放到输出缓冲区中。
? 在实现利用败者树进行多路平衡归并算法时,
把败者树的 叶结点 和 非叶结点 分开定义 。
? 败者树叶结点 key[ ]有 k+1个,key[0]到 key[k-1]
存放 各归并段当前参加归并的对象的排序码,
key[k]是辅助工作单元,在初始建立败者树时
使用, 存放一个最小的在各归并段中不可能出
现的排序码,-MaxNum。
? 败者树非叶结点 loser[ ]有 k个,其中 loser[1]到
loser[k-1]存放各次比较的败者的归并段号,
loser[0]中是最后胜者所在归并段号 。 另外还
有一个存放各归并段参加归并对象的数组 r[k]。
k 路平衡归并排序算法
void kwaymerge ( Element *r ) {
r = new Element[k]; //创建对象数组
int *key = new int[k+1]; //创建外结点数组
int *loser = new int[k]; //创建败者树数组
for ( int i = 0; i < k; i++ ) //传送参选排序码
{ InputRecord ( r[i] ); key[i] = r[i].key; }
for ( i = 0; i < k; i++) loser[i] = k;
key[k] = -MaxNum; //初始化
for ( i = k-1; i; i-- ) //调整形成败者树
adjust ( key,loser,k,i );
while ( key[loser[0]] != MaxNum ) { //选冠军
q = loser[0]; //最小对象的段号
OutputRecord ( r[q] ); //输出
InputRecord ( r[q] ); //从该段补入对象
key[q] = r[q].key;
adjust ( key,loser,k,q ); //调整
}
Output end of run marker; //输出段结束标志
delete [ ] r; delete [ ] key; delete [ ] loser;
}
自某叶结点 key[q]到败者树根结点的调整算法
void adjust ( int key[ ]; int loser[ ]; const int k;
const int q ) {
//q指示败者树某外结点 key[q],从该结点起到
//根进行比较,将最小 key 对象所在归并段的
//段号记入 loser[0]。 k是外结点 key[ ]个数。
for ( int t = (k+q) / 2; t > 0; t /= 2 ) // t是 q双亲
if ( key[loser[t]] < key[q]) {
//败者记入 loser[t],胜者记入 q
int temp = q; q = loser[t]; loser[t] = temp;
} //q与 loser[t]交换
loser[0] = q;
}
? 每选出一个当前排序码最小的对象,就需要
在将它送入输出缓冲区之后,从相应归并段
的输入缓冲区中取出下一个参加归并的对象,
替换已经取走的最小对象,再从叶结点到根
结点,沿某一特定路径进行调整,将下一个排
序码最小对象的归并段号调整到 loser[0]中 。
? 段结束标志 MaxNum升入 loser[0],排序完成 。
? 归并路数 k 不是越大越好。归并路数 k 增大,
相应需增加输入缓冲区个数。如果可供使用
的内存空间不变,势必要减少每个输入缓冲
区的容量,使内外存交换数据的次数增大 。
利用败者树进行 5路平衡归并的过程
(1) 初始状态 (2) 加入 15,29,调整
29 15
5 17
5
05
5
10
-?
5
5
k3 k4 k5
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 10
k2
5
05
ls3
k1
17
4
k0
ls2
3ls4
15
k4
-?
k5
29
k3
5ls1
5ls0
利用败者树进行 5路平衡归并的过程
29 15
3 17
4
05
2
10
-?
1
5
k3 k4 k5
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 10
k2
2
05
ls3
k1
17
0
k0
ls2
3ls4
15
k4
-?
k5
29
k3
4ls1
1ls0
(3) 加入 10,05,调整 (4) 加入 17,调整
输出 05
利用败者树进行 5路平衡归并的过程
29 15
3 17
0
44
1
10
4
2
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 12
k2
1
44
ls3
k1
17
0
k0
ls2
3ls4
15
k4
29
k3
4ls1
2ls0
(5) 输出 05后调整 (6) 输出 10后调整
输入 44
输出 12输出 10
输入 12
利用败者树进行 5路平衡归并的过程
29 15
3 17
0
44
2
?
1
4
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
44
ls3
k1
17
3
k0
ls2
4ls4
56
k4
29
k3
1ls1
0ls0
输入 ?
输出 17输出 15
输入 56
(7) 输出 12后调整 (8) 输出 15后调整
利用败者树进行 5路平衡归并的过程
29 56
4 21
3
44
2
?
1
0
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
44
ls3
k1
?
0
k0
ls2
4ls4
56
k4
29
k3
1ls1
3ls0
输入 21
输出 29输出 21
输入 ?
(9) 输出 17后调整 (10) 输出 21后调整
利用败者树进行 5路平衡归并的过程
32 56
4 ?
0
44
2
?
1
3
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
44
ls3
k1
?
0
k0
ls2
3ls4
56
k4
?
k3
4ls1
1ls0
输入 32
输出 44输出 32
输入 ?
(11) 输出 29后调整 (12) 输出 32后调整
利用败者树进行 5路平衡归并的过程
? 56
3 ?
0
?
2
?
1
4
k3 k4
k0 k1 k2
ls1
ls0
ls2 ls3
ls4 ?
k2
2
?
ls3
k1
?
0
k0
ls2
3ls4
?
k4
?
k3
1ls1
4ls0 输出 ?，
结束
输出 56
输入 ?输入 ?
(13) 输出 44后调整 (14) 输出 56后调整
初始归并段的生成 (Run Generation)
? 为减少读写磁盘次数,除增加归并路数 k 外,
还可 减少初始归并段个数 m。 在总对象数 n
一定时,要减少 m,必须 增大初始归并段长度 。
? 如果规定每个初始归并段等长,则此长度应
根据生成它的内存工作区空间大小而定,因
而 m的减少也就受到了限制 。
? 为了突破这个限制,可 采用败者树来生成初
始归并段 。 在使用同样大内存工作区的情况
下,可以 生成平均比原来等长情况下大一倍
的初始归并段,从而 减少初始归并段个数 。
? 设输入文件 FI中各对象的排序码序列为 { 17,
21,05,44,10,12,56,32,29 }。
? 选择和臵换过程的步骤如下：
① 从输入文件 FI中把 k 个对象读入内存中,并
构造败者树 。 (内存中存放对象的数组 r可容
纳的对象个数为 k )
② 利用败者树在 r 中选择一个排序码最小的对
象 r[q],其排序码存入 LastKey作为门槛 。 以
后再选出的排序码比它大的对象归入本归并
段,比它小的归入下一归并段 。
③ 将此 r[q]对象写到输出文件 FO中 。 (q 是叶结
点序号 )
④ 若 FI未读完,则从 FI读入下一个对象,臵换
r[q]及败者树中的 key[q]。
⑤ 调整败者树,从所有排序码比 LastKey大的
对象中选择一个排序码最小的对象 r[q]作为
门槛,其排序码存入 LastKey。
⑥ 重复 ③ ～ ⑤,直到在败者树中选不出排序码
比 LastKey大的对象为止 。 此时,在输出文件
FO中得到一个初始归并段,在它最后加一个
归并段结束标志 。
⑦ 重复 ② ～ ⑥,重新开始选择和臵换,产生新的
初始归并段,直到输入文件 FI中所有对象选
完为止 。
输 入 文 件 FI 内存数组 r 输出文件 FO
1
7 21 05 44 10 12 56 32 29
44 10 12 56 32 29 1 7 2 1 05
10 12 56 32 29 17 2 1 4 4 0 5
12 56 32 29 1 0 21 4 4 0 5 1 7
56 32 29 1 0 1 2 44 0 5 1 7 2 1
32 29 1 0 1 2 56 0 5 1 7 2 1 4 4
29 1 0 1 2 3 2 0 5 1 7 2 1 4 4 5 6
29 1 0 1 2 3 2 0 5 1 7 2 1 4 4 5 6 ?
29 10 1 2 3 2
2 9 1 2 3 2 1 0
2 9 ─ 3 2 1 0 1 2
─ ─ 32 1 0 1 2 2 9
─ ─ ─ 1 0 1 2 2 9 3 2
─ ─ ─ 1 0 1 2 2 9 3 2 ?
? 若按在 k 路平衡归并排序 中所讲的, 每个初
始归并段的长度与内存工作区的长度一致,
则上述 9个对象可分成 3个初始归并段：
Run0 { 05,17,21 }
Run1 { 10,12,44 }
Run2 { 29,32,56 }
? 但采用上述选择与臵换的方法,可生成 2个长
度不等的初始归并段,
Run0 { 05,17,21,44,56 }
Run1 { 10,12,29,32 }
? 在利用败者树生成 不等长初始归并段 的算法
和调整败者树并选出最小对象的算法中, 用
两个条件来决定谁为败者, 谁为胜者 。
?首先比较两个对象所在归并段的段号,段
号小者为胜者, 段号大者为败者 ；
?在归并段的段号相同时,排序码小者为胜
者, 排序码大者为败者 。
? 比较后把败者对象在对象数组 r 中的序号记
入它的双亲结点中,把胜者对象在对象数组 r
中的序号记入工作单元 s 中,向更上一层进行
比较,最后的胜者记入 loser[0]中 。
{ 17,21,05,44,10,12,56,32,29 }
17
(1) 初始化 (2) 输入 17,调整
0
0
0
0
0
0
0
0
0
ls1
ls0
ls2
k2
k0
k1
0
0
0
2
1ls0
ls1
k0ls
2
17
1
k2
0
0
k1
0
0
排序码
段号
{ 17,21,05,44,10,12,56,32,29 }
21 (3) 输入 21,调整 (4) 输入 05,建败者树
21
1
1
17
1
0
0
2
0
ls1
ls0
ls2
k2
k0
k1
05
1
2
1
0ls0
ls1
k0ls
2
17
1
k2
21
1
k1
05
选 05
{ 17,21,05,44,10,12,56,32,29 }
44
(5) lastKey=05,置换 (6) lastKey=17,置换
k0,选择 17 k2,段号加 1,选择 21
21
1
1
17
1
44
1
0
2
ls1
ls0
ls2
k2
k0
k1
44
1
0
2
1ls0
ls1
k0ls
2
10
2
k2
21
1
k1
10
选 21选 17
{ 17,21,05,44,10,12,56,32,29 }
12
(7) lastKey=21,置换 (8) lastKey=44,置换
k1,段号加 1,选择 44 k0,选择 56
12
2
1
10
2
44
1
2
0
ls1
ls0
ls2
k2
k0
k1
56
1
2
1
0ls0
ls1
k0ls
2
10
2
k2
12
2
k1
56
选 56选 44
{ 17,21,05,44,10,12,56,32,29 }
32
(9) lastKey=56,置换 (10) 输出段结束标志,
k0,段号加 1,本段结束 选择 10
12
2
1
10
2
32
2
0
2
ls1
ls0
ls2
k2
k0
k1
32
2
0
1
2ls0
ls1
k0ls
2
10
2
k2
12
2
k1
选 10
{ 17,21,05,44,10,12,56,32,29 }
29
(11) lastKey=10,置换 (12) lastKey=12,k1 置
k2,选择 12 虚段,选择 29
12
2
2
29
2
32
2
0
1
ls1
ls0
ls2
k2
k0
k1
32
2
0
1
2ls0
ls1
k0ls
2
29
2
k2
12
3
k1
选 29选 12
虚段
{ 17,21,05,44,10,12,56,32,29 }
(13) lastKey=29,k2 置 (14) lastKey=32,k0 置
虚段,选择 32 虚段,本段结束
12
3
2
29
3
32
2
1
0
ls1
ls0
ls2
k2
k0
k1
32
3
0
2
1ls0
ls1
k0ls
2
29
3
k2
12
3
k1
选 32
虚段虚段 虚段
虚段
虚段
(15) 输出段结束标志,
结束
12
3
2
29
3
32
3
0
1
ls1
ls0
ls2
k2
k0
k1
段号
超出
? 当输入的对象序列已
经按排序码大小排好
序时，只生成一个初
始归并段。
? 在一般情况下，若输
入文件有 n 个对象，
生成初始归并段的时
间开销是 O(nlog2k)，
因为每输出一个对象，
对败者树进行调整需
要时间为 O(log2k)。
最佳归并树
? 归并树是描述归并过程的 m 叉树。因为每一
次做 m 路归并都需要有 m 个归并段参加,因
此,归并树是只有度为 0和度为 m 的结点的正
则 m 叉树。
? 示例, 设有 13个长度不等的初始归并段,其长
度 (对象个数 )分别为
0,0,1,3,5,7,9,13,16,20,24,30,38
? 其中长度为 0 的是空归并段。对它们进行 3
路归并时的归并树如图所示。
此归并树的带权路径长度为
WPL＝ (24+30+38+7+9+13)*2+ (16+20+1+3+5)*3
＝ 377。
16 20 0 1 3 5
36 938 1397
29
03024
54 83
166
? 在归并树中
? 各叶结点代表参加归并的各初始归并段
? 叶结点上的权值即为该初始归并段中的对
象个 数
? 根结点代表最终生成的归并段
? 叶结点到根结点的路径长度表示在归并过
程中的读对象次数
? 各非叶结点代表归并出来的新归并段
? 归并树的带权路径长度 WPL 即为归并过
程中的总读对象数。因而，在归并过程中
总的读写对象次数为 2*WPL = 754。
? 不同的归并方案所对应的归并树的带权路径
长度各不相同。
? 为了使得总的读写次数达到最少,需要改变
归并方案,重新组织归并树。
? 可将霍夫曼树的思想扩充到 m 叉树的情形。
在归并树中,让对象个数少的初始归并段最
先归并,对象个数多的初始归并段最晚归并,
就可建立总读写次数达到最少的最佳归并树。
? 例如,假设有 11个初始归并段,其长度 (对象个
数 )分别为
1,3,5,7,9,13,16,20,24,30,38
做 3路归并。
? 为使归并树成为一棵正则三叉树,可能需要补
入空归并段。补空归并段的原则为：
? 若参加归并的初始归并段有 n 个,做 m 路
平衡归并。因归并树是只有度为 0 和度为
m 的结点的正则 m 叉树,设度为 0 的结点有
n0(= n) 个,度为 m 的结点有 nm 个,则有
n0 = (m-1)nm +1
nm = (n0 -1)／ (m -1)。
? 若 (n0-1) % (m-1) = 0,则说明这 n0 个叶结
点正好可以构造 m 叉归并树。
? 若 (n0 -1) % (m-1) = u ? 0，则对于这 n0 个
叶结点,其中的 u 个不足以参加 m 路归并。
? 故除了有 nm 个度为 m 的内结点之外,还
需增加一个内结点。它在归并树中代替了
一个叶结点位臵,被代替的叶结点加上刚
才多出的 u 个叶结点,再加上 m-u-1 个对
象个数为零的空归并段,就可建立归并树。
? 在示例中,n0 = 11,m = 3,(11-1) % (3-1)
= 0,可以不加空归并段,直接进行 3路归并。
? 它的带权路径长度
WPL = 38*1+(13+16+20+24+30)*2+(7+9)*3
+ (1+3+5)*4 = 328。
1 3 5 7 9 13 16 20 24 30 38
1 3 5
7 9 9 13 16 20 24 30 38
13 16 20 24 25 30 38
1 3 5
97 9
1 3 5
9
25
7
24
9
30 38
13 16 20
49
38
13 16 20
49
24 25 30
79
997
3 51
166
? 如果做 5路归并, 让 m = 5,则有
(11-1)／ (5-1) = 2
? 表示有 2个度为 5的内结点；但是,
u = (11-1) % (5-1) =2 ? 0
? 需要加一个内结点,它在归并树中代替了一
个叶结点的位臵,故一个叶结点参加这个内
结点下的归并,需要增加的空初始归并段数
为 m-u-1＝ 5-2-1 = 2
? 应当补充 2 个空归并段 。 则归并树如图所
示 。
带权路径长度 WPL＝ (1+3+5)*3+(7+9+13+
+16)*2+(20+24+30+38)＝ 229
0 0 1 3 5
7 9 9 13 16 20 24 30 38
0 0 1 3 5
97 9 13 16
5438302420
166
