1
? 概述
? 插入排序
? 交换排序
? 选择排序
? 归并排序
? 外排序
2
概述
? 排序, 将一组杂乱无章的数据按一定的规律
顺次排列起来 。
? 数据表 (datalist),它是待排序数据对象的有限
集合 。
? 排序码 (key),通常数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可
用来区分对象,作为排序依据 。 该域即为 排
序码 。 每个数据表用哪个属性域作为排序码,
要视具体的应用需要而定 。
3
? 排序算法的稳定性,如果在对象序列中有两
个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],且
在排序之前,对象 r[i]排在 r[j]前面。如果在排
序之后,对象 r[i]仍在对象 r[j]的前面,则称这
个排序方法是稳定的,否则称这个排序方法
是不稳定的。
? 内排序与外排序, 内排序是指在排序期间
数据对象全部存放在内存的排序；外排序
是指在排序期间全部对象个数太多，不能
同时存放在内存，必须根据排序过程的要
求，不断在内、外存之间移动的排序。
4
? 排序的时间开销, 排序的时间开销是衡量
算法好坏的最重要的标志。 排序的时间开销
可用算法执行中的 数据比较次数 与 数据移动
次数 来衡量 。
? 算法运行时间代价的大略估算一般都 按平均
情况 进行估算。对于那些 受对象排序码序列
初始排列及对象个数影响较大的, 需要 按最
好情况 和 最坏情况 进行估算 。
? 算法执行时所需的附加存储, 评价算法好
坏的另一标准。
5
插入排序 (Insert Sorting)
? 基本思想是, 当插入第 i (i ? 1) 个对象时,前
面的 V[0],V[1],…,V[i-1]已经排好序。这时,
用 V[i]的排序码与 V[i-1],V[i-2],… 的排序码
顺序进行比较,找到插入位臵即将 V[i]插入,
原来位臵上的对象向后顺移。
基本方法是, 每步将一个待排序的对象,按
其排序码大小,插入到前面已经排好序的一
组对象的适当位臵上,直到对象全部插入为止 。
直接插入排序 (Insert Sort)
6
各
趟
排
序
结
果
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
7
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
8
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
9
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
10
直接插入排序的算法
typedef int SortData;
void InsertSort ( SortData V[ ],int n ) {
//按非递减顺序对表进行排序
SortData temp; int i,j;
for ( i = 1; i < n; i++ ) {
temp = V[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < V[j-1] ) V[j] = V[j-1];
else break;
V[j] = temp;
}
}
11
算法分析
? 设待排序对象个数为 n,则该算法的主程序
执行 n-1趟。
? 排序码比较次数和对象移动次数与对象排
序码的初始排列有关。
? 最好情况下,排序前对象已按排序码从小
到大有序,每趟只需与前面有序对象序列
的最后一个对象比较 1次,移动 2次对象,总
的排序 码比较次数为 n-1,对象移动次数
为 2(n-1)。
12
? 最坏情况下,第 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
13
折半插入排序 (Binary Insertsort)
? 基本思想, 设在顺序表中有一 个对象序列
V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,
V[i-1] 是已经排好序的对象。在插入 V[i] 时,
利用折半搜索法寻找 V[i]的插入位臵。
折半插入排序的算法
typedef int SortData;
void BinInsSort ( SortData V[ ],int n ) {
SortData temp; int Left,Right;
14
for ( int i = 1; i < n; i++) {
Left = 0; Right = i-1; temp = V[i];
while ( Left <= Right ) {
int mid = ( Left + Right )/2;
if ( temp < V[mid] ) Right = mid - 1;
else Left = mid + 1;
}
for ( int k = i-1; k >= Left; k-- )
V[k+1] = V[k];
V[Left] = temp;
}
}
15
? 折半搜索比顺序搜索查找快,所以折半插入
排序就 平均性能 来说比直接插入排序要快。
? 它所需的 排序码比较次数与待排序对象序
列的初始排列无关,仅依赖于对象个数。 在
插入第 i 个对象时,需要经过 ?log2i?+1 次排
序码比较,才能确定它应插入的位臵。 因此,
将 n 个对象 (为推导方便,设为 n=2k )用折半
插入排序所进行的排序码比较次数为：
? ?? ??
?
?
???
1
1
22 l o g1l o g
n
i
nni
算法分析
16
? 当 n 较大 时,总排序码比较次数比直接插
入排序的最坏情况要好得多,但比其最好
情况要差 。
? 在对象的初始排列已经按排序码排好序或
接近有序时,直接插入排序比折半插入排
序执行的排序码比较次数要少 。 折半插入
排序的对象移动次数与直接插入排序相同,
依赖于对象的初始排列 。
? 折半插入排序是一个 稳定 的排序方法。
17
希尔排序 (Shell Sort)
? 希尔排序方法又称为缩小增量排序。该方法
的基本思想是, 设待排序对象序列有 n 个对
象,首先取一个整数 gap < n 作为间隔,将全
部对象分为 gap 个子序列,所有 距离为 gap
的对象放在 同一个子序列 中,在每一个子序
列中分别施行直接插入排序。然后缩小间隔
gap,例如取 gap = ?gap/2?，重复上述的子序
列划分和排序工作。直到最后取 gap == 1,
将所有对象放在同一个序列中排序为止。
18
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
19
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
20
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
Gap = 1
2516 4925*
? 开始时 gap 的值较大,子序列中的对象较少,
排序速度较快 ; 随着排序进展,gap 值逐渐
变小,子序列中对象个数逐渐变多,由于前
面工作的基础,大多数对象已基本有序,所
以排序速度仍然很快。
21
希尔排序的算法
typedef int SortData;
void ShellSort ( SortData V[ ],int n ) {
SortData temp; int gap = n / 2; //gap是间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < n; i++) {
temp = V[i]; //直接插入排序
for ( int j = i; j >= gap; j = j-gap )
if ( temp < V[j-gap] )
V[j] = V[j-gap];
else break;
22
V[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
? Gap的取法有多种。最初 shell 提出取 gap =
?n/2?,gap = ?gap/2?,直到 gap = 1。 knuth
提出取 gap = ?gap/3?+1。
? 对特定的待排序对象序列，可以准确地估算
排序码的比较次数和对象移动次数 。
23
? 想要弄清排序码比较次数和对象移动次数
与增量选择之间的依赖关系, 并给出完整
的数学分析, 还没有人能够做到 。
? Knuth利用大量实验统计资料得出, 当 n
很大时, 排序码平均比较次数和对象平均
移动次数大约在 n1.25到 1.6n1.25的范围内 。
这是在利用直接插入排序作为子序列排序
方法的情况下得到的 。
24
交换排序 ( Exchange Sort )
? 基本方法：设待排序对象序列中的对象个
数为 n。最多作 n-1 趟,i = 1,2,?,n-1。
在第 i 趟中 从后向前, j = n-1,n-2,?,i，
顺次两两 比较 V[j-1]和 V[j]。 如果发生逆序，
则交换 V[j-1]和 V[j]。
基本思想是 两两比较待排序对象的排序码,
如发生逆序 (即排列顺序与排序后的次序正好
相反 )，则交换之 。直到所有对象都排好序为
止。
起泡排序 (Bubble Sort)
25
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
26
25*
0 1 2 3 4 5
i = 4 4916
Exchang=008
2521
起泡排序的算法
typedef int SortData;
void BubbleSort ( SortData V[ ],int n ) {
int i = 1; int exchange = 1;
while ( i < n && exchange ){
exchange = 0; //标志置为 0,假定未交换
for ( int j = n-1; j >= i; j-- )
if ( V[j-1] > V[j] ) { //逆序
27
Swap ( V[j-1],V[j] );,//交换
exchange = 1; //标志置为 1,有交换
}
i++;
}
}
? 第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-1]
进行排序,结果 将该序列中排序码最小的对
象交换到序列的第一个位臵 (i-1),其它对象
也都向排序的最终位臵移动 。 在个别情形,
对象可能在排序中途向相反的方向移动 。
28
? 最多做 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
)()(
)()(
29
快速排序 (Quick Sort)
? 基本思想是任取 待排序对象序列中的某个对象
(例如取第一个对象 ) 作为基准,按照该对象的
排序码大小,将整个对象序列划分为左右两
个子序列,
? 起泡排序需要一个附加对象以实现对象值的
对换。
? 起泡排序是一个 稳定 的排序方法。
30
? 左侧子序列中所有对象的排序码都小于
或等于基准对象的排序码
? 右侧子序列中所有对象的排序码都大于
基准对象的排序码
? 基准对象则排在这两个子序列中间 (这也是
该对象最终应安放的位臵 )。
? 然后分别对这两个子序列重复施行上述方
法，直到所有的对象都排在相应位臵上为
止。
31
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
算法描述
32
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
33
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
34
快速排序的算法
typedef int SortData;
void QuickSort ( SortData V[ ],int left,int right ){
//在序列 left?right 中递归地进行快速排序
if ( left < right) {
int pivotpos = Partition (V,left,right); //划分
//对左序列同样处理
QuickSort ( V,left,pivotpos-1);
//对右序列同样处理
QuickSort ( V,pivotpos+1,right );
}
}
35
int Partition ( SortData V[ ],int low,int high ) {
int pivotpos = low; //基准位置
SortData pivot = V[low];
for ( int i = low+1; i <= high; i++ )
if ( V[i] < pivot ) {
pivotpos++;
if ( pivotpos != i )
Swap ( V[pivotpos],V[i] );
} //小于基准对象的交换到区间的左侧去
Swap ( V[low],V[pivotpos] );
return pivotpos;
}
36
? 算法 quicksort是一个递归的算法,其递归树
如图所示。
? 算法 partition利用 序列第一个对象作为基准,
将整个序列划分为左右两个子序列 。算法
中执行了一个循环,只要是排序码小于基准
对象排序码的对象都移到序列左侧,最后基
准对象安放到位,函数返回其位臵。
21
25*
25
49
08
16
37
算法分析
? 快速排序的趟数取决于递归树的高度 。
? 如果每次划分对一个对象定位后,该对象的
左侧子序列与右侧子序列的长度相同,则下
一步将是对两个长度减半的子序列进行排序,
这是最理想的情况。
? 在 n个元素的序列中,对一个对象定位所需
时间为 O(n)。 若设 t (n) 是对 n 个元素的序
列进行排序所需的时间,而且每次对一个对
象正确定位后,正好把序列划分为长度相等
的两个子序列,此时,总的计算时间为：
38
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)。 实验结果表明, 就平均计算时
间而言,快速排序是所有内排序方法中最好
的一个 。
? 快速排序是递归的, 需要有一个栈存放每层
递归调用时的指针和参数 。
39
? 最大递归调用层次数与递归树的高度一致,
理想情况为 ?log2(n+1)? 。 因此, 要求存储
开销为 O(log2n)。
? 在最坏的情况,即 待排序对象序列已经按其
排序码从小到大排好序 的情况下,其 递归树
成为单支树,每次划分只得到一个比上一次
少一个对象的子序列 。 总的排序码比较次
数将达
? 快速排序是一种 不稳定 的排序方法 。
212
1 21
1
nnninn
i
?????
?
?
)()(
40
用第一个对象作为基准对象
快速排序退化的例子
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
41用居中排序码对象作为基准对象
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 个对
象，取其排序码居中者作为基准对象。
42
基本思想是, 每一趟 (例如第 i 趟,i = 0,1,…,
n-2) 在后面 n-i 个待排序对象中选出排序码
最小的对象,作为有序对象序列的第 i 个对象。
待到第 n-2 趟作完,待排序对象只剩下 1个,就
不用再选了。
选择排序
43
② 若它不是这组对象中的第一个对象,则
将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码
的对象 。 在剩下的对象 V[i+1]～ V[n-1]中
重复执行第 ①, ② 步,直到剩余对象只有
一个为止 。
? 直接选择排序是一种简单的排序方法,它的
基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最
小排序码的对象；
直接选择排序 (Select Sort)
44
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
45
4925*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3
08 16 2521
最小者 25*
无交换
最小者 25
无交换252116
08
各趟排序后的结果
46
直接选择排序的算法
typedef int SortData;
void SelectSort ( SortData V[ ],int n ) {
for ( int i = 0; i < n-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < n; j++)
if ( V[j] < V[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位置
Swap ( V[i],V[k] );
}
}
47
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
48
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 )()(
49
? 对象的移动次数与对象序列的初始排列有
关 。当这组对象的初始状态是按其排序码
从小到大有序的时候,对象的移动次数
RMN = 0，达到最少。
? 最坏情况是每一趟都要进行交换,总的对
象移动次数 为 RMN = 3(n-1)。
? 直接选择排序是一种 不稳定 的排序方法。
50
链表直接选择排序
15 25
25
15
25 35 15 0f h 0
q p
25f
15
0 h 35 0
pq=0
0f 35 0h
pq=0
f=0 h 35 0
f
51
void selectSort ( ListNode * head ) {
ListNode * f = head->link,p,q,r,s;
head->link = NULL;
while ( f != NULL ) { //原始链表未扫描完
p = s = f; q = r = NULL;
while ( p != NULL ) {
//扫描原始链表,寻找排序码最大的结点 *s
if ( p->data > s->data ) { s = p; r = q; }
//记忆当前找到的排序码最大结点
q = p; p = p->link;
}
52
if ( s == f ) f = f ->link;
//排序码最大结点是链表前端结点,摘下
else r->link = s->link;
//排序码最大结点是链表表中结点,摘下
s->link = head->link;
head->link = s;
//结点 s插入到结果链表的前端
}
}
53
? 利用堆及其运算,可以很容易地实现选择排
序的思路。
? 堆排序分为两个步骤
? 根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
? 通过一系列的对象交换和重新调整堆进
行排序。
堆排序 (Heap Sort)
54
建立初始的最大堆
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 时的局部调整
55
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 时的局部调整
56
最大堆的向下调整算法
void FilterDown ( MaxHeap *H,
int start,int EndOfHeap ) {
int i = start; int j = 2*i+1;
HeadData temp = H->data[i];
while ( j <= EndOfHeap ) { //最后位置
if ( j < EndOfHeap &&
H->data[j] < H->data[j+1] )
j = j+1; //选两子女的大者
if ( temp >= H->data[j] ) break;
else {
57
H->data[i] = H->data[j]; //大 子女上移
i = j; j = 2*j+1; //向下继续调整
}
}
H->data[i] = temp; //回放到合适位置
}
将表转换成堆
for ( int i = ( H->CSize-2) / 2 ; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 );
58
基于初始堆进行堆排序
? 最大堆堆顶 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个对象重新调整,… 。
? 如此反复执行，最后得到全部排序好的对象
序列。这个算法即堆排序算法，其细节在下
面的程序中给出。
59
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 号对象就位
初始最大堆
60
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 号 重新
调整为最大堆
61
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 号 重新
调整为最大堆
62
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 号 重新
调整为最大堆
63
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 号 重新
调整为最大堆
64
堆排序的算法
void HeapSort ( MaxHeap *H ) {
//对表 heap[0]到 heap[n-1]进行排序,使得表中
//各 个对象按其排序码非递减有序 。
for ( int i = ( H->CSize-2 ) / 2; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 ); //初始堆
for ( i = H->CSize-1; i >= 1; i--) {
Swap ( H->data[0],H->data[i] ); //交换
FilterDown ( H,0,i-1 ); //重建最大堆
}
}
65
? 若设堆中有 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
66
? 第二个 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 )(
67
归并排序 (Merge Sort)
? 归并，是将两个或两个以上的有序表合并成
一个新的有序表。
? 原始序列 initList[ ]中两个有序表
initList[l] … initList[ m]和 initList[m+1] …
initList[n]。它们可归并成一个有序表,存于
另一对象序列 mergedList的 l … n 中。
? 这种归并方法称为 两路归并 (2-way merging)。
? 设变量 i 和 j 是表 initList[l … m]和 initList
[m+1… n]的当前检测指针。 k是存放指针。
归并
68
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 中有一个已经超出表长时，将另一
个表中的剩余部分照抄到新表中。
69
迭代的归并排序算法
? 迭代的归并排序算法就是利用两路归并过程
进行排序的。其基本思想是：
? 假设初始对象序列有 n 个对象,首先把它看
成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到 ?n / 2? 个长度为 2 的归
并项 (如果 n 为奇数，则最后一个有序子序
列的长度为 1)；再做两两归并,…,如此重
复,最后得到一个长度为 n 的有序序列 。
70
两路归并算法
typedef int SortData;
void merge ( SortData InitList[ ],
SortData mergedList[ ],
int left,int mid,int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较
if ( InitList[i] <= InitList[j] )
{ mergedList [k] = InitList[i]; i++; k++; }
else
{ mergedList [k] = InitList[j]; j++; k++; }
71
while ( i <= mid )
{ mergedList[k] = InitList[i]; i++; k++; }
while ( j <= right )
{ mergedList[k] = InitList[j]; j++; k++; }
}
72
一趟归并排序的情形
? 设 initList[0]到 initList[n-1]中 n 个对象 已经
分为一些长度为 len 的归并项,将这些归并
项两两归并,归并成长度为 2len 的归并项,
结果放到 mergedList[ ]中。
? 如果 n不是 2len的整数倍,则一趟归并到最后,
可能遇到两种情形：
? 剩下一个长度为 len的归并项和另一个长
度不足 len的归并项,可用 merge算法 将它
们归并成一个长度小于 2len 的归并项。
? 只剩下一个归并项，其长度小于或等于
len,将它直接抄到 MergedList[ ]中。
73
void MergePass ( SortData initList[ ],SortData
mergedList[ ],int len ) {
int i = 0;
while (i+2*len-1 <= n-1) {
merge( initList,mergedList,
i,i+len-1,i+2*len-1);
i += 2 * len; //循环两两归并
}
if ( i+len <= n-1 )
( initList,mergedList,i,i+len-1,n-1);
else for ( int j = i; j <= n-1; j++)
mergedList [j] = initList[j];
}
74
迭代的归并排序算法
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
75
(两路 )归并排序的主算法
void MergeSort ( SortData initList[ ],int n ) {
//按对象排序码非递减的顺序对表中对象排序
SortData tempList[n];
int len = 1;
while ( len < n ) {
MergePass ( initList,tempList,len );
len *= 2;
MergePass ( tempList,initList,len );
len *= 2;
}
}
76
? 在迭代的归并排序算法中,函数 MergePass( )
做一趟两路归并排序,要调用 merge ( )函数
?n/(2*len)? ? O(n/len) 次,函数 MergeSort( )调
用 MergePass( )正好 ?log2n? 次,而每次 merge( )
要执行比较 O(len)次,所以算法总的时间复杂
度为 O(nlog2n)。
? 归并排序占用附加存储较多,需要另外一个与
原待排序对象数组同样大小的辅助数组 。 这
是这个算法的缺点 。
? 归并排序是一个 稳定 的排序方法 。
77
只需要一个附加存储的两路归并算法
? 设算法中参加归并的两个归并段是 A[left]
?A[mid] 和 A[mid+1]?A[right]，归并后结
果归并段放在原地。
08 21 25 49 62 72 16 37 54
left mid mid+1 right
A 08 < 16
08 21 25 49 62 72 16 37 54 A 21 > 16
08 21 25 49 62 16 37 54 A temp = 72
78
left mid mid+1 right
08 16 21 25 49 62 16 37 54 A temp = 72
08 16 21 25 49 62 37 54 A temp = 72
08 16 21 25 49 62 37 54 72 A
08 16 21 25 49 62 37 54 72 A 21 < 37
08 16 21 25 49 62 37 54 72 A 25 < 37
08 16 21 25 49 62 37 54 72 A 49 > 37
79
left mid mid+1 right
08 16 21 25 49 37 54 72 A temp = 62
08 16 21 25 37 49 37 54 72A temp = 62
08 16 21 25 37 49 54 62 72 A
08 16 21 25 37 49 54 62 72 A 49 < 54
08 16 21 25 37 49 54 62 72A 结束
80
typedef int SortData;
void merge( SortData A[ ],
int left,int mid,int right ) {
int i,j; SortData temp;
for ( i = left; i <= mid; i++ ) {
if ( A[i] > A[mid+1] ) {
temp = A[mid];
for ( j = mid-1; j >= i; j-- )
A[j+1] = A[j];
A[i] = A[mid+1];
if ( temp <= A[mid+2] )
A[mid+1] = temp;
81
else {
for ( j = mid+2; j <= right; j++ )
if ( temp > A[j] ) A[j-1] = A[j];
else { A[j-1] = temp; break; }
}
}
}
}
82
各种排序方法的比较
比较次数 移动次数 附加存储排 序 方 法
最好 最
差
最好 最
差
稳定
性
最好 最
差
直接插入排序 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
83
外排序
? 当对象以文件形式存放于磁盘上的时候,通
常是按物理块存储的。
当待排序的对象数目特别多时，在内存中不
能一次处理。必须把它们以文件的形式存放于
外存，排序时再把它们一部分一部分调入内存
进行处理。这样，在排序过程中必须不断地在
内存与外存之间传送数据。 这种基于外部存储
设备（或文件）的排序技术就是外排序 。
外排序的基本过程
84
? 物理块 也叫做 页块 。每个页块可存放几个对
象。操作系统 按页块对磁盘信息进行读写 。
? 磁盘通常是指 由若干片磁盘组成的磁盘组,
各个盘片安装在同一主轴上高速旋转。各个
盘面上半径相同的磁道构成了柱面。各盘面
设臵一个读写磁头，它们装在同一动臂上，
可以径向从一个柱面移到另一个柱面上。
? 为了访问某一页块,先寻找柱面, 移动动臂使
读写磁头移到指定柱面上, 寻查 (seek)。再根
据磁道号 (盘面号 )选择相应读写磁头,等待指
定页块转到读写磁头下, 等待 (latency)。 在
磁盘组上存取一个页块的时间：
85
? 基于磁盘进行的排序多使用归并排序方法。
其排序过程主要分为两个阶段：
① 建立 用于外排序的内存缓冲区 。根据它们
的大小 将输入文件划分为若干段,用某种
内排序方法对各段进行排序。经过排序的
段叫做 初始归并段 或初始顺串 (Run)。当
它们生成后就被写到外存中去。
② 仿照归并树模式,把 ① 生成的初始归并段
加以归并,一趟趟地 扩大归并段 和 减少归
并段个数,直到最后归并成一个大归并段
(有序文件 )为止。
tio＝ tseek＋ tlatency＋ trw
86
? 示例：设有一个包含 4500个对象 的输入文件。
现用一台其内存 至多可容纳 750个对象 的计算
机对该文件进行排序。输入文件放在磁盘上,
磁盘每个页块可容纳 250个对象,这样全部对
象可存储在 4500 / 250＝ 18 个页块中。输出
文件也放在磁盘上,用以存放归并结果。
? 由于内存中可用于排序的存储区域能容纳 750
个对象,因此 内存中恰好能存 3个页块 的对象。
? 在外排序一开始,把 18块对象,每 3块一组,读
入内存。利用某种内排序方法进行内排序,形
成初始归并段,再写回外存。总共可得到 6个
初始归并段。然后一趟一趟进行归并排序。
87
两路归并排序的归并树
R1 750 R2 750 R3 750 R4 750 R5 750 R6 750
初始
归并段
R12 1500 R34 1500 R56 1500
R1234 3000
R123456 4500
第一趟
归并结果
第二趟
归并结果
第三趟
归并结果
88
? 若把内存区域等份地分为 3 个缓冲区。其中
的两个为输入缓冲区,一个为输出缓冲区,可
以在内存中利用简单 2 路归并函数 merge( )
实现 2 路归并。
? 首先,从参加归并排序的两个输入归并段 R1
和 R2 中分别读入一块,放在 输入缓冲区 1和
输入缓冲区 2中。然后在内存中进行 2 路归
并，归并结果顺序存放到 输出缓冲区 中。
输入缓冲区 2
输入缓冲区 1
输出缓冲区
89
? 若总对象个数为 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
90
? 对 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
91
? 由于 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
92
? 增大归并路数,可减少归并趟数,从而减少总
读写磁盘次数 d。
? 对 m 个初始归并段,做 k 路平衡归并,归并树
可用 正则 k 叉树 (即只有度为 k 与度为 0的结
点的 k 叉树 ) 来表示。
? 第一趟可将 m 个初始归并段归并为 l = ?m/k?
个归并段，以后每一趟归并将 l 个归并段归
并成 l = ?l / k?个归并段，直到最后形成一个
大的归并段为止。树的高度＝ ?logkm?＝ 归
并趟数 S。
93
k路平衡归并 (k-way Balanced merging)
? 做 k 路平衡归并时,如果有 m 个初始归并段,
则相应的归并树有 ?logkm?+1 层,需要归并
?logkm?趟。下图给出对有 36 个初始归并段
的文件做 6 路平衡归并时的归并树。
94
最佳归并树
? 归并树是描述归并过程的 m 叉树。因为每一
次做 m 路归并都需要有 m 个归并段参加,因
此,归并树是只有度为 0和度为 m 的结点的正
则 m 叉树。
? 示例, 设有 13个长度不等的初始归并段,其长
度 (对象个数 )分别为
0,0,1,3,5,7,9,13,16,20,24,30,38
? 其中长度为 0 的是空归并段。对它们进行 3
路归并时的归并树如图所示。
95
此归并树的带权路径长度为
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
96
? 在归并树中
? 各叶结点代表参加归并的各初始归并段
? 叶结点上的权值即为该初始归并段中的对
象个 数
? 根结点代表最终生成的归并段
? 叶结点到根结点的路径长度表示在归并过
程中的读对象次数
? 各非叶结点代表归并出来的新归并段
? 归并树的带权路径长度 WPL 即为归并过
程中的总读对象数。因而，在归并过程中
总的读写对象次数为 2*WPL = 754。
97
? 不同的归并方案所对应的归并树的带权路径
长度各不相同。
? 为了使得总的读写次数达到最少,需要改变
归并方案,重新组织归并树。
? 可将霍夫曼树的思想扩充到 m 叉树的情形。
在归并树中,让对象个数少的初始归并段最
先归并,对象个数多的初始归并段最晚归并,
就可建立总读写次数达到最少的最佳归并树。
? 例如,假设有 11个初始归并段,其长度 (对象个
数 )分别为
1,3,5,7,9,13,16,20,24,30,38
做 3路归并。
98
? 为使归并树成为一棵正则三叉树,可能需要补
入空归并段。补空归并段的原则为：
? 若参加归并的初始归并段有 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 路归并。
99
? 故除了有 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。
100
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
101
? 如果做 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 个空归并段 。 则归并树如图所
示 。
102
带权路径长度 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
? 概述
? 插入排序
? 交换排序
? 选择排序
? 归并排序
? 外排序
2
概述
? 排序, 将一组杂乱无章的数据按一定的规律
顺次排列起来 。
? 数据表 (datalist),它是待排序数据对象的有限
集合 。
? 排序码 (key),通常数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可
用来区分对象,作为排序依据 。 该域即为 排
序码 。 每个数据表用哪个属性域作为排序码,
要视具体的应用需要而定 。
3
? 排序算法的稳定性,如果在对象序列中有两
个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],且
在排序之前,对象 r[i]排在 r[j]前面。如果在排
序之后,对象 r[i]仍在对象 r[j]的前面,则称这
个排序方法是稳定的,否则称这个排序方法
是不稳定的。
? 内排序与外排序, 内排序是指在排序期间
数据对象全部存放在内存的排序；外排序
是指在排序期间全部对象个数太多，不能
同时存放在内存，必须根据排序过程的要
求，不断在内、外存之间移动的排序。
4
? 排序的时间开销, 排序的时间开销是衡量
算法好坏的最重要的标志。 排序的时间开销
可用算法执行中的 数据比较次数 与 数据移动
次数 来衡量 。
? 算法运行时间代价的大略估算一般都 按平均
情况 进行估算。对于那些 受对象排序码序列
初始排列及对象个数影响较大的, 需要 按最
好情况 和 最坏情况 进行估算 。
? 算法执行时所需的附加存储, 评价算法好
坏的另一标准。
5
插入排序 (Insert Sorting)
? 基本思想是, 当插入第 i (i ? 1) 个对象时,前
面的 V[0],V[1],…,V[i-1]已经排好序。这时,
用 V[i]的排序码与 V[i-1],V[i-2],… 的排序码
顺序进行比较,找到插入位臵即将 V[i]插入,
原来位臵上的对象向后顺移。
基本方法是, 每步将一个待排序的对象,按
其排序码大小,插入到前面已经排好序的一
组对象的适当位臵上,直到对象全部插入为止 。
直接插入排序 (Insert Sort)
6
各
趟
排
序
结
果
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
7
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
8
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
9
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
10
直接插入排序的算法
typedef int SortData;
void InsertSort ( SortData V[ ],int n ) {
//按非递减顺序对表进行排序
SortData temp; int i,j;
for ( i = 1; i < n; i++ ) {
temp = V[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < V[j-1] ) V[j] = V[j-1];
else break;
V[j] = temp;
}
}
11
算法分析
? 设待排序对象个数为 n,则该算法的主程序
执行 n-1趟。
? 排序码比较次数和对象移动次数与对象排
序码的初始排列有关。
? 最好情况下,排序前对象已按排序码从小
到大有序,每趟只需与前面有序对象序列
的最后一个对象比较 1次,移动 2次对象,总
的排序 码比较次数为 n-1,对象移动次数
为 2(n-1)。
12
? 最坏情况下,第 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
13
折半插入排序 (Binary Insertsort)
? 基本思想, 设在顺序表中有一 个对象序列
V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,
V[i-1] 是已经排好序的对象。在插入 V[i] 时,
利用折半搜索法寻找 V[i]的插入位臵。
折半插入排序的算法
typedef int SortData;
void BinInsSort ( SortData V[ ],int n ) {
SortData temp; int Left,Right;
14
for ( int i = 1; i < n; i++) {
Left = 0; Right = i-1; temp = V[i];
while ( Left <= Right ) {
int mid = ( Left + Right )/2;
if ( temp < V[mid] ) Right = mid - 1;
else Left = mid + 1;
}
for ( int k = i-1; k >= Left; k-- )
V[k+1] = V[k];
V[Left] = temp;
}
}
15
? 折半搜索比顺序搜索查找快,所以折半插入
排序就 平均性能 来说比直接插入排序要快。
? 它所需的 排序码比较次数与待排序对象序
列的初始排列无关,仅依赖于对象个数。 在
插入第 i 个对象时,需要经过 ?log2i?+1 次排
序码比较,才能确定它应插入的位臵。 因此,
将 n 个对象 (为推导方便,设为 n=2k )用折半
插入排序所进行的排序码比较次数为：
? ?? ??
?
?
???
1
1
22 l o g1l o g
n
i
nni
算法分析
16
? 当 n 较大 时,总排序码比较次数比直接插
入排序的最坏情况要好得多,但比其最好
情况要差 。
? 在对象的初始排列已经按排序码排好序或
接近有序时,直接插入排序比折半插入排
序执行的排序码比较次数要少 。 折半插入
排序的对象移动次数与直接插入排序相同,
依赖于对象的初始排列 。
? 折半插入排序是一个 稳定 的排序方法。
17
希尔排序 (Shell Sort)
? 希尔排序方法又称为缩小增量排序。该方法
的基本思想是, 设待排序对象序列有 n 个对
象,首先取一个整数 gap < n 作为间隔,将全
部对象分为 gap 个子序列,所有 距离为 gap
的对象放在 同一个子序列 中,在每一个子序
列中分别施行直接插入排序。然后缩小间隔
gap,例如取 gap = ?gap/2?，重复上述的子序
列划分和排序工作。直到最后取 gap == 1,
将所有对象放在同一个序列中排序为止。
18
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
19
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
20
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
Gap = 1
2516 4925*
? 开始时 gap 的值较大,子序列中的对象较少,
排序速度较快 ; 随着排序进展,gap 值逐渐
变小,子序列中对象个数逐渐变多,由于前
面工作的基础,大多数对象已基本有序,所
以排序速度仍然很快。
21
希尔排序的算法
typedef int SortData;
void ShellSort ( SortData V[ ],int n ) {
SortData temp; int gap = n / 2; //gap是间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < n; i++) {
temp = V[i]; //直接插入排序
for ( int j = i; j >= gap; j = j-gap )
if ( temp < V[j-gap] )
V[j] = V[j-gap];
else break;
22
V[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
? Gap的取法有多种。最初 shell 提出取 gap =
?n/2?,gap = ?gap/2?,直到 gap = 1。 knuth
提出取 gap = ?gap/3?+1。
? 对特定的待排序对象序列，可以准确地估算
排序码的比较次数和对象移动次数 。
23
? 想要弄清排序码比较次数和对象移动次数
与增量选择之间的依赖关系, 并给出完整
的数学分析, 还没有人能够做到 。
? Knuth利用大量实验统计资料得出, 当 n
很大时, 排序码平均比较次数和对象平均
移动次数大约在 n1.25到 1.6n1.25的范围内 。
这是在利用直接插入排序作为子序列排序
方法的情况下得到的 。
24
交换排序 ( Exchange Sort )
? 基本方法：设待排序对象序列中的对象个
数为 n。最多作 n-1 趟,i = 1,2,?,n-1。
在第 i 趟中 从后向前, j = n-1,n-2,?,i，
顺次两两 比较 V[j-1]和 V[j]。 如果发生逆序，
则交换 V[j-1]和 V[j]。
基本思想是 两两比较待排序对象的排序码,
如发生逆序 (即排列顺序与排序后的次序正好
相反 )，则交换之 。直到所有对象都排好序为
止。
起泡排序 (Bubble Sort)
25
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
26
25*
0 1 2 3 4 5
i = 4 4916
Exchang=008
2521
起泡排序的算法
typedef int SortData;
void BubbleSort ( SortData V[ ],int n ) {
int i = 1; int exchange = 1;
while ( i < n && exchange ){
exchange = 0; //标志置为 0,假定未交换
for ( int j = n-1; j >= i; j-- )
if ( V[j-1] > V[j] ) { //逆序
27
Swap ( V[j-1],V[j] );,//交换
exchange = 1; //标志置为 1,有交换
}
i++;
}
}
? 第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-1]
进行排序,结果 将该序列中排序码最小的对
象交换到序列的第一个位臵 (i-1),其它对象
也都向排序的最终位臵移动 。 在个别情形,
对象可能在排序中途向相反的方向移动 。
28
? 最多做 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
)()(
)()(
29
快速排序 (Quick Sort)
? 基本思想是任取 待排序对象序列中的某个对象
(例如取第一个对象 ) 作为基准,按照该对象的
排序码大小,将整个对象序列划分为左右两
个子序列,
? 起泡排序需要一个附加对象以实现对象值的
对换。
? 起泡排序是一个 稳定 的排序方法。
30
? 左侧子序列中所有对象的排序码都小于
或等于基准对象的排序码
? 右侧子序列中所有对象的排序码都大于
基准对象的排序码
? 基准对象则排在这两个子序列中间 (这也是
该对象最终应安放的位臵 )。
? 然后分别对这两个子序列重复施行上述方
法，直到所有的对象都排在相应位臵上为
止。
31
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
算法描述
32
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
33
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
34
快速排序的算法
typedef int SortData;
void QuickSort ( SortData V[ ],int left,int right ){
//在序列 left?right 中递归地进行快速排序
if ( left < right) {
int pivotpos = Partition (V,left,right); //划分
//对左序列同样处理
QuickSort ( V,left,pivotpos-1);
//对右序列同样处理
QuickSort ( V,pivotpos+1,right );
}
}
35
int Partition ( SortData V[ ],int low,int high ) {
int pivotpos = low; //基准位置
SortData pivot = V[low];
for ( int i = low+1; i <= high; i++ )
if ( V[i] < pivot ) {
pivotpos++;
if ( pivotpos != i )
Swap ( V[pivotpos],V[i] );
} //小于基准对象的交换到区间的左侧去
Swap ( V[low],V[pivotpos] );
return pivotpos;
}
36
? 算法 quicksort是一个递归的算法,其递归树
如图所示。
? 算法 partition利用 序列第一个对象作为基准,
将整个序列划分为左右两个子序列 。算法
中执行了一个循环,只要是排序码小于基准
对象排序码的对象都移到序列左侧,最后基
准对象安放到位,函数返回其位臵。
21
25*
25
49
08
16
37
算法分析
? 快速排序的趟数取决于递归树的高度 。
? 如果每次划分对一个对象定位后,该对象的
左侧子序列与右侧子序列的长度相同,则下
一步将是对两个长度减半的子序列进行排序,
这是最理想的情况。
? 在 n个元素的序列中,对一个对象定位所需
时间为 O(n)。 若设 t (n) 是对 n 个元素的序
列进行排序所需的时间,而且每次对一个对
象正确定位后,正好把序列划分为长度相等
的两个子序列,此时,总的计算时间为：
38
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)。 实验结果表明, 就平均计算时
间而言,快速排序是所有内排序方法中最好
的一个 。
? 快速排序是递归的, 需要有一个栈存放每层
递归调用时的指针和参数 。
39
? 最大递归调用层次数与递归树的高度一致,
理想情况为 ?log2(n+1)? 。 因此, 要求存储
开销为 O(log2n)。
? 在最坏的情况,即 待排序对象序列已经按其
排序码从小到大排好序 的情况下,其 递归树
成为单支树,每次划分只得到一个比上一次
少一个对象的子序列 。 总的排序码比较次
数将达
? 快速排序是一种 不稳定 的排序方法 。
212
1 21
1
nnninn
i
?????
?
?
)()(
40
用第一个对象作为基准对象
快速排序退化的例子
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
41用居中排序码对象作为基准对象
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 个对
象，取其排序码居中者作为基准对象。
42
基本思想是, 每一趟 (例如第 i 趟,i = 0,1,…,
n-2) 在后面 n-i 个待排序对象中选出排序码
最小的对象,作为有序对象序列的第 i 个对象。
待到第 n-2 趟作完,待排序对象只剩下 1个,就
不用再选了。
选择排序
43
② 若它不是这组对象中的第一个对象,则
将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码
的对象 。 在剩下的对象 V[i+1]～ V[n-1]中
重复执行第 ①, ② 步,直到剩余对象只有
一个为止 。
? 直接选择排序是一种简单的排序方法,它的
基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最
小排序码的对象；
直接选择排序 (Select Sort)
44
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
45
4925*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3
08 16 2521
最小者 25*
无交换
最小者 25
无交换252116
08
各趟排序后的结果
46
直接选择排序的算法
typedef int SortData;
void SelectSort ( SortData V[ ],int n ) {
for ( int i = 0; i < n-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < n; j++)
if ( V[j] < V[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位置
Swap ( V[i],V[k] );
}
}
47
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
48
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 )()(
49
? 对象的移动次数与对象序列的初始排列有
关 。当这组对象的初始状态是按其排序码
从小到大有序的时候,对象的移动次数
RMN = 0，达到最少。
? 最坏情况是每一趟都要进行交换,总的对
象移动次数 为 RMN = 3(n-1)。
? 直接选择排序是一种 不稳定 的排序方法。
50
链表直接选择排序
15 25
25
15
25 35 15 0f h 0
q p
25f
15
0 h 35 0
pq=0
0f 35 0h
pq=0
f=0 h 35 0
f
51
void selectSort ( ListNode * head ) {
ListNode * f = head->link,p,q,r,s;
head->link = NULL;
while ( f != NULL ) { //原始链表未扫描完
p = s = f; q = r = NULL;
while ( p != NULL ) {
//扫描原始链表,寻找排序码最大的结点 *s
if ( p->data > s->data ) { s = p; r = q; }
//记忆当前找到的排序码最大结点
q = p; p = p->link;
}
52
if ( s == f ) f = f ->link;
//排序码最大结点是链表前端结点,摘下
else r->link = s->link;
//排序码最大结点是链表表中结点,摘下
s->link = head->link;
head->link = s;
//结点 s插入到结果链表的前端
}
}
53
? 利用堆及其运算,可以很容易地实现选择排
序的思路。
? 堆排序分为两个步骤
? 根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
? 通过一系列的对象交换和重新调整堆进
行排序。
堆排序 (Heap Sort)
54
建立初始的最大堆
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 时的局部调整
55
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 时的局部调整
56
最大堆的向下调整算法
void FilterDown ( MaxHeap *H,
int start,int EndOfHeap ) {
int i = start; int j = 2*i+1;
HeadData temp = H->data[i];
while ( j <= EndOfHeap ) { //最后位置
if ( j < EndOfHeap &&
H->data[j] < H->data[j+1] )
j = j+1; //选两子女的大者
if ( temp >= H->data[j] ) break;
else {
57
H->data[i] = H->data[j]; //大 子女上移
i = j; j = 2*j+1; //向下继续调整
}
}
H->data[i] = temp; //回放到合适位置
}
将表转换成堆
for ( int i = ( H->CSize-2) / 2 ; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 );
58
基于初始堆进行堆排序
? 最大堆堆顶 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个对象重新调整,… 。
? 如此反复执行，最后得到全部排序好的对象
序列。这个算法即堆排序算法，其细节在下
面的程序中给出。
59
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 号对象就位
初始最大堆
60
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 号 重新
调整为最大堆
61
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 号 重新
调整为最大堆
62
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 号 重新
调整为最大堆
63
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 号 重新
调整为最大堆
64
堆排序的算法
void HeapSort ( MaxHeap *H ) {
//对表 heap[0]到 heap[n-1]进行排序,使得表中
//各 个对象按其排序码非递减有序 。
for ( int i = ( H->CSize-2 ) / 2; i >= 0; i-- )
FilterDown ( H,i,H->CSize-1 ); //初始堆
for ( i = H->CSize-1; i >= 1; i--) {
Swap ( H->data[0],H->data[i] ); //交换
FilterDown ( H,0,i-1 ); //重建最大堆
}
}
65
? 若设堆中有 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
66
? 第二个 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 )(
67
归并排序 (Merge Sort)
? 归并，是将两个或两个以上的有序表合并成
一个新的有序表。
? 原始序列 initList[ ]中两个有序表
initList[l] … initList[ m]和 initList[m+1] …
initList[n]。它们可归并成一个有序表,存于
另一对象序列 mergedList的 l … n 中。
? 这种归并方法称为 两路归并 (2-way merging)。
? 设变量 i 和 j 是表 initList[l … m]和 initList
[m+1… n]的当前检测指针。 k是存放指针。
归并
68
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 中有一个已经超出表长时，将另一
个表中的剩余部分照抄到新表中。
69
迭代的归并排序算法
? 迭代的归并排序算法就是利用两路归并过程
进行排序的。其基本思想是：
? 假设初始对象序列有 n 个对象,首先把它看
成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到 ?n / 2? 个长度为 2 的归
并项 (如果 n 为奇数，则最后一个有序子序
列的长度为 1)；再做两两归并,…,如此重
复,最后得到一个长度为 n 的有序序列 。
70
两路归并算法
typedef int SortData;
void merge ( SortData InitList[ ],
SortData mergedList[ ],
int left,int mid,int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较
if ( InitList[i] <= InitList[j] )
{ mergedList [k] = InitList[i]; i++; k++; }
else
{ mergedList [k] = InitList[j]; j++; k++; }
71
while ( i <= mid )
{ mergedList[k] = InitList[i]; i++; k++; }
while ( j <= right )
{ mergedList[k] = InitList[j]; j++; k++; }
}
72
一趟归并排序的情形
? 设 initList[0]到 initList[n-1]中 n 个对象 已经
分为一些长度为 len 的归并项,将这些归并
项两两归并,归并成长度为 2len 的归并项,
结果放到 mergedList[ ]中。
? 如果 n不是 2len的整数倍,则一趟归并到最后,
可能遇到两种情形：
? 剩下一个长度为 len的归并项和另一个长
度不足 len的归并项,可用 merge算法 将它
们归并成一个长度小于 2len 的归并项。
? 只剩下一个归并项，其长度小于或等于
len,将它直接抄到 MergedList[ ]中。
73
void MergePass ( SortData initList[ ],SortData
mergedList[ ],int len ) {
int i = 0;
while (i+2*len-1 <= n-1) {
merge( initList,mergedList,
i,i+len-1,i+2*len-1);
i += 2 * len; //循环两两归并
}
if ( i+len <= n-1 )
( initList,mergedList,i,i+len-1,n-1);
else for ( int j = i; j <= n-1; j++)
mergedList [j] = initList[j];
}
74
迭代的归并排序算法
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
75
(两路 )归并排序的主算法
void MergeSort ( SortData initList[ ],int n ) {
//按对象排序码非递减的顺序对表中对象排序
SortData tempList[n];
int len = 1;
while ( len < n ) {
MergePass ( initList,tempList,len );
len *= 2;
MergePass ( tempList,initList,len );
len *= 2;
}
}
76
? 在迭代的归并排序算法中,函数 MergePass( )
做一趟两路归并排序,要调用 merge ( )函数
?n/(2*len)? ? O(n/len) 次,函数 MergeSort( )调
用 MergePass( )正好 ?log2n? 次,而每次 merge( )
要执行比较 O(len)次,所以算法总的时间复杂
度为 O(nlog2n)。
? 归并排序占用附加存储较多,需要另外一个与
原待排序对象数组同样大小的辅助数组 。 这
是这个算法的缺点 。
? 归并排序是一个 稳定 的排序方法 。
77
只需要一个附加存储的两路归并算法
? 设算法中参加归并的两个归并段是 A[left]
?A[mid] 和 A[mid+1]?A[right]，归并后结
果归并段放在原地。
08 21 25 49 62 72 16 37 54
left mid mid+1 right
A 08 < 16
08 21 25 49 62 72 16 37 54 A 21 > 16
08 21 25 49 62 16 37 54 A temp = 72
78
left mid mid+1 right
08 16 21 25 49 62 16 37 54 A temp = 72
08 16 21 25 49 62 37 54 A temp = 72
08 16 21 25 49 62 37 54 72 A
08 16 21 25 49 62 37 54 72 A 21 < 37
08 16 21 25 49 62 37 54 72 A 25 < 37
08 16 21 25 49 62 37 54 72 A 49 > 37
79
left mid mid+1 right
08 16 21 25 49 37 54 72 A temp = 62
08 16 21 25 37 49 37 54 72A temp = 62
08 16 21 25 37 49 54 62 72 A
08 16 21 25 37 49 54 62 72 A 49 < 54
08 16 21 25 37 49 54 62 72A 结束
80
typedef int SortData;
void merge( SortData A[ ],
int left,int mid,int right ) {
int i,j; SortData temp;
for ( i = left; i <= mid; i++ ) {
if ( A[i] > A[mid+1] ) {
temp = A[mid];
for ( j = mid-1; j >= i; j-- )
A[j+1] = A[j];
A[i] = A[mid+1];
if ( temp <= A[mid+2] )
A[mid+1] = temp;
81
else {
for ( j = mid+2; j <= right; j++ )
if ( temp > A[j] ) A[j-1] = A[j];
else { A[j-1] = temp; break; }
}
}
}
}
82
各种排序方法的比较
比较次数 移动次数 附加存储排 序 方 法
最好 最
差
最好 最
差
稳定
性
最好 最
差
直接插入排序 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
83
外排序
? 当对象以文件形式存放于磁盘上的时候,通
常是按物理块存储的。
当待排序的对象数目特别多时，在内存中不
能一次处理。必须把它们以文件的形式存放于
外存，排序时再把它们一部分一部分调入内存
进行处理。这样，在排序过程中必须不断地在
内存与外存之间传送数据。 这种基于外部存储
设备（或文件）的排序技术就是外排序 。
外排序的基本过程
84
? 物理块 也叫做 页块 。每个页块可存放几个对
象。操作系统 按页块对磁盘信息进行读写 。
? 磁盘通常是指 由若干片磁盘组成的磁盘组,
各个盘片安装在同一主轴上高速旋转。各个
盘面上半径相同的磁道构成了柱面。各盘面
设臵一个读写磁头，它们装在同一动臂上，
可以径向从一个柱面移到另一个柱面上。
? 为了访问某一页块,先寻找柱面, 移动动臂使
读写磁头移到指定柱面上, 寻查 (seek)。再根
据磁道号 (盘面号 )选择相应读写磁头,等待指
定页块转到读写磁头下, 等待 (latency)。 在
磁盘组上存取一个页块的时间：
85
? 基于磁盘进行的排序多使用归并排序方法。
其排序过程主要分为两个阶段：
① 建立 用于外排序的内存缓冲区 。根据它们
的大小 将输入文件划分为若干段,用某种
内排序方法对各段进行排序。经过排序的
段叫做 初始归并段 或初始顺串 (Run)。当
它们生成后就被写到外存中去。
② 仿照归并树模式,把 ① 生成的初始归并段
加以归并,一趟趟地 扩大归并段 和 减少归
并段个数,直到最后归并成一个大归并段
(有序文件 )为止。
tio＝ tseek＋ tlatency＋ trw
86
? 示例：设有一个包含 4500个对象 的输入文件。
现用一台其内存 至多可容纳 750个对象 的计算
机对该文件进行排序。输入文件放在磁盘上,
磁盘每个页块可容纳 250个对象,这样全部对
象可存储在 4500 / 250＝ 18 个页块中。输出
文件也放在磁盘上,用以存放归并结果。
? 由于内存中可用于排序的存储区域能容纳 750
个对象,因此 内存中恰好能存 3个页块 的对象。
? 在外排序一开始,把 18块对象,每 3块一组,读
入内存。利用某种内排序方法进行内排序,形
成初始归并段,再写回外存。总共可得到 6个
初始归并段。然后一趟一趟进行归并排序。
87
两路归并排序的归并树
R1 750 R2 750 R3 750 R4 750 R5 750 R6 750
初始
归并段
R12 1500 R34 1500 R56 1500
R1234 3000
R123456 4500
第一趟
归并结果
第二趟
归并结果
第三趟
归并结果
88
? 若把内存区域等份地分为 3 个缓冲区。其中
的两个为输入缓冲区,一个为输出缓冲区,可
以在内存中利用简单 2 路归并函数 merge( )
实现 2 路归并。
? 首先,从参加归并排序的两个输入归并段 R1
和 R2 中分别读入一块,放在 输入缓冲区 1和
输入缓冲区 2中。然后在内存中进行 2 路归
并，归并结果顺序存放到 输出缓冲区 中。
输入缓冲区 2
输入缓冲区 1
输出缓冲区
89
? 若总对象个数为 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
90
? 对 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
91
? 由于 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
92
? 增大归并路数,可减少归并趟数,从而减少总
读写磁盘次数 d。
? 对 m 个初始归并段,做 k 路平衡归并,归并树
可用 正则 k 叉树 (即只有度为 k 与度为 0的结
点的 k 叉树 ) 来表示。
? 第一趟可将 m 个初始归并段归并为 l = ?m/k?
个归并段，以后每一趟归并将 l 个归并段归
并成 l = ?l / k?个归并段，直到最后形成一个
大的归并段为止。树的高度＝ ?logkm?＝ 归
并趟数 S。
93
k路平衡归并 (k-way Balanced merging)
? 做 k 路平衡归并时,如果有 m 个初始归并段,
则相应的归并树有 ?logkm?+1 层,需要归并
?logkm?趟。下图给出对有 36 个初始归并段
的文件做 6 路平衡归并时的归并树。
94
最佳归并树
? 归并树是描述归并过程的 m 叉树。因为每一
次做 m 路归并都需要有 m 个归并段参加,因
此,归并树是只有度为 0和度为 m 的结点的正
则 m 叉树。
? 示例, 设有 13个长度不等的初始归并段,其长
度 (对象个数 )分别为
0,0,1,3,5,7,9,13,16,20,24,30,38
? 其中长度为 0 的是空归并段。对它们进行 3
路归并时的归并树如图所示。
95
此归并树的带权路径长度为
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
96
? 在归并树中
? 各叶结点代表参加归并的各初始归并段
? 叶结点上的权值即为该初始归并段中的对
象个 数
? 根结点代表最终生成的归并段
? 叶结点到根结点的路径长度表示在归并过
程中的读对象次数
? 各非叶结点代表归并出来的新归并段
? 归并树的带权路径长度 WPL 即为归并过
程中的总读对象数。因而，在归并过程中
总的读写对象次数为 2*WPL = 754。
97
? 不同的归并方案所对应的归并树的带权路径
长度各不相同。
? 为了使得总的读写次数达到最少,需要改变
归并方案,重新组织归并树。
? 可将霍夫曼树的思想扩充到 m 叉树的情形。
在归并树中,让对象个数少的初始归并段最
先归并,对象个数多的初始归并段最晚归并,
就可建立总读写次数达到最少的最佳归并树。
? 例如,假设有 11个初始归并段,其长度 (对象个
数 )分别为
1,3,5,7,9,13,16,20,24,30,38
做 3路归并。
98
? 为使归并树成为一棵正则三叉树,可能需要补
入空归并段。补空归并段的原则为：
? 若参加归并的初始归并段有 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 路归并。
99
? 故除了有 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。
100
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
101
? 如果做 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 个空归并段 。 则归并树如图所
示 。
102
带权路径长度 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
