第 8章 排 序
8.1 排序技术概述
8.2 插入排序
8.3 选择排序
8.4 交换排序
8.5 归并排序
8.6 基数排序
8.7 外部排序概述
8.8 本章小结
8.1 排序技术概述
从操作角度看，排序是线性
结构的一种操作。
为了提高排序效率，人们已
对排序进行了许多研究，提出了
许多方法。
排序就是按照某种规则，
为一组给定的对象排列次序。
排序的 主要目的 是：在排好
序的集合中能够快速查找（检索）
一个元素。
所谓, 内部, 排序，就是指整个排
序过程都是在内存中进行的。
如果排序的数据项很多，内存不足
以存放得下全部数据项时，排序过程就
需要对外存进行存取访问，也就是, 外
部, 排序。
本章的内容以内部排序为主，对外
部排序只进行简单地介绍。
我们把查找时关注或使用的数据
叫做关键字（ key），它可以是数据
信息当中的一个属性，也可以是几个
属性的组合。
关键字可以代表其所在的那项数
据信息。在这项数据信息当中，关键
字所取的值叫做键值。
在本章中，为了突出排序
算法本身的内容，我们简化各项
数据的属性个数。
假设待排序的数据都只有
一个属性，这个属性就是关键字，
并且关键字的类型是 整型 。
我们可以把排序看成是一种定
义在某种数据集合上的操作。
本章所讲的各种内部排序，都
可以认为是在一维数组这种线性数
据结构上定义的操作。其功能是将
一组任一排列的数据元素重新排列
成一个按键值有序的序列。
对排序更为确切的定义,
假设 {D1,D2,?,DN}为含有 N项数据
的序列, 其中 Di（ 1≤ i≤ N） 表示序列中
第 i项数据, N项数据对应的键值序列为
{K1,K2,?,KN}。
排序操作是将这些数据重新排列成一
个 按 键 值 有 序 的 新 序 列
{Rp1,Rp2,?,RpN},使得相应的键值满
足条件 p1≤ p2≤ ? ≤ pN（ 此时新序列成
,升序, ） 或 p1≥ p2≥ ? ≥ pN（ 此时新
序列成, 降序, ） 。
注意,在上面定义叙述中所用到
的 ≤ 或 ≥ 这两个比较符号，是通用意义
上的关系比较符。
对于数值型信息，它是表示关系的
小或大；对于字符串来说，它是指在字
典中所排列位置的前或后。
对于不同类型的数据，我们可以规
定不同的比较规则来反映 ≤ 或 ≥ 的含义。
如果在数据序列中，有多个具
有相同键值的数据，在排序前后，
这些数据之间的相对次序保持不变，
这样的排序方法被称作是 稳定 的，
否则被称为是 不稳定 的。
分析算法效率：
1,从空间角度进行：主要是看
执行算法时所需附加空间的数量；
2,从时间角度进行：从两种操
作入手进行分析。
键值的比较次数
数据移动的次数
8.2 插入排序
插入排序 是指在待排序的序列中，分
成两部分：前面为已经排好序的部分，后
面为仍未排好序的部分。
每一轮都从 没有排好序部分 取出首元
素按照大小将其插到前面 已经排好序部分
中的合适位置上。
这样前面已排序部分就多了一个元素，
后面未排序部分同时少了一个元素。该排
序过程不断进行，直到未排序部分的元素
数目为零。
插入排序
将待排序的序列分成两部分：前
面为已经排好序的部分，后面为仍未
排好序的部分。
每一轮都从没有排好序部分取出首
元素按照大小将其插到前面已经排好
序部分中的合适位置上。
这样前面已排序部分就多了一个元
素，后面未排序部分同时少了一个元
素。该排序过程不断进行，直到未排
序部分的元素数目为零。
排序过程如图 8.1所示。
图（ a）为该轮排序前的状态，
图（ b）为该轮排序后的状态，
阴影表示本轮待排序的元素，在图（ b）
中它已经插入到已排好序部分的合适位
置上。
本轮待插入元素
未排好序部分已排好序部分
插入到合
适位置
( a ) 本轮插入前序列状态
未排好序部分已排好序部分
( b ) 本轮插入后序列状态
注意,
在排序过程开始时，直接把序
列中第一个元素认为是已排好序部
分。另外，用整型数组代表排序的
数据元素序列，数组下标为零的元
素我们当作辅助空间，所以从数组
下标是 1的空间开始存储元素序列。
在把待插入元素从未排序部分移入已
排好序部分时，有多种方法，下面逐一介
绍。
8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 2_路插入排序
8.2.4 表插入排序
8.2.5 希尔排序
8.2.1 直接插入排序
直接插入排序
又称简单插入排序。排序过程
中，待插入元素先放在临时空间
hold中，依次让它和前面的元素作
比较，直到发现其应插入的位置，将
其插入。
//不带哨兵的直接插入排序 。
//数组 rec为待排序的序列,
//count为排序元素的个数
void insertSortSimple(int rec[],
int count)
{ int curr,hold;
for(int inx=2; inx<=count;
inx++)
//从第二个元素起依次做插入排序
{ hold=rec[inx]; curr=inx-1;
//从已排好序部分的尾元素开始向前
//查找待插入位置
while(curr>=1 &&
hold<rec[curr])
{ rec[curr+1]=rec[curr];
curr--;
}
rec[curr+1]=hold;
//将待插入元素插到合适的位置
}
}
算法中,while语句的条件表达式由两部
分组成,curr>=1保证数组下标不会越界
（ curr不会被减到低于零,rec[curr]保证
有意义），但这样做就会增加一次条件判断。
为了提高效率，我们把待插入元素先放在
临时空间 rec[0]中，依次让它和前面的元素
作比较，直到发现其应插入的位置，将其插入。
注意 rec[0]起到了, 哨兵, 的作用。因
为 while语句的条件表达式使得 curr不会被
减到低于零。
//改进后的直接插入排序
//数组 rec为待排序的序列, count为排序元
//素的个数
insertSortSimple(int rec[],int
count)
{ int curr;
for(int inx=2; inx<=count;
inx++)
//从第二个元素起依次做插入排序
{ rec[0]=rec[inx];
curr=inx-1;
//从已排好序部分的尾元素开始向前
//查找待插入位置
while(rec[0]<rec[curr])
{ rec[curr+1]=rec[curr];
curr--;
}
rec[curr+1]=rec[0];
//将待插入元素插到合适的位置
}
}
从 while语句的条件表达式得知直接插入
排序是 稳定 的排序算法 。
分析算法中元素比较与移动的次数
如果每轮待插入的元素都是在已排好序
部分中的最大元素，那么每轮比较次数只有
一次（只和已排好序部分的尾元比较一次），
而且不用移动元素。 N个元素的序列只做了
N-1轮的操作，所以标准操作次数 Tmin=(N-
1)*1+(N-1)*0=N-1=O(N)，显然这种方
式对应的情况是原序列已经是升序。
如果原序列是降序, 而最终结果应该是升
序, 故每一轮中待插入元素要和所有已排好
序的元素进行比较 （ 包括哨兵在内 ）, 而且
这些元素都要依次后移 （ 哨兵不后移 ）, 以
便将首元位置空出, 让待插元素插到最前面
的位置 。 这样,
比较次数为：
Tcompare=2+3+…+N=(N+2)*(N-1)/2
移动次数 为：
Tshift=1+2+…+(N-1)=N*(N-1)/2
所以标准操作次数：
Tmax=Tcompare+Tshift=O(N2)。
注意,
上面计算移动记录次数的过程中，并没有
考虑以下两个赋值操作：给哨兵赋值的操作和
将待插元素插到正确位置的赋值操作。
如果将这两项计算在内，那么移动次数都
应再加上 2(N-1)的值。考虑到排序序列中各
元素值是随机取值的，所以它们之间大小排列
也是随机的，因此各种排列概率相同，我们取
最差时间效率与最好时间效率的平均值做为直
接插入排序的平均时间复杂度，为 O(N2)。在
算法中我们多开了一个辅助空间，故空间复杂
度为 O(1)。
8.2.2 折半 插入排序
在向有序表中插入元素的过程中，
直接插入排序采用的方法是：从后向前
依次与有序表中元素作比较。没有充分
利用, 前部分已经有序, 的特性，这种
方法 效率较低 。
考虑 改进 的方法：
设定有序表长度为 L，那么让待插元素 x和
处于 有序表中间位置 的元素 y作比较：
如果待插元素 x大于或等于 y，则说明插入
的位置一定在有序表的后半部分；
如果待插元素 x较小，则说明插入的位置
一定在有序表的前半部分。
无论哪种情况，我们都可以将可能插入的
位置所在的空间长度降至原来长度的一半，故
称, 折半, 插入排序。
对于长度为 L的有序表，大约需要
log2L次的比较就可以确定出待插元素的
位置。因此对于 N个元素的序列来说，进
行 N-1轮的所有比较次数为 O(N*log2N)，
显然优于直接插入法中平均情况下的比
较次数 O(N2)。但是在确定了待插位置之
后，元素移动的次数并没有降下来，所
以时间复杂度仍为有 O(N2)。
算法中仍旧多开了一个辅助空间，
故空间复杂度为 O(1)，保持不变。
void insertSortBinary(int rec[],
int count)
{ int hold; //当前正处理的元素
int btm,top,mid;
for(int inx=2; inx<=count;
inx++)
//从第二个元素起依次做插入排序
{ hold=rec[inx];
btm=1;top=inx-1;
//从已排好序部分的尾元素开始向前
//查找待插入位置
while(btm<=top)
{ mid=(btm+top)/2;
if(rec[mid]<hold)
btm=mid+1;
else top=mid-1;
}
for(int i=inx-1;i>=btm;i--)
rec[i+1]=rec[i];
rec[btm]=hold;
//将待插入元素插到合适的位置
}
}
8.2.3 2_路插入排序
在折半插入排序的基础上，再
针对数据元素的移动进行算法的改
进，就得到 2_路插入排序算法。
我们开设一个辅助数组 temp，其大小为
待排序元素的个数，把它当作是 循环数组 。
将第一个元素放在数组 temp[0]中，并
把它当作是有序表中 处于中间位置 的元素。
从第二个元素开始，每个元素在做插入的
时候，都先与 temp[0]进行比较。
若是 小于 temp[0]，则往它 前面 的有序
表中插； 否则,往其 后面 的有序表中插。
有序表首元素和尾元素的下标分别用
first与 last表示。显然，开始状态下，有
序表中 仅有 temp[0]，所以 first=last=0。
由于多开了辅助数组，所以该算法的空间
复杂度为 O(N)。
- 1242 94125544 57
44
r e c 数组
t e m p 数组
first last
44 55
first last
44 1255
firstlast
44 421255
firstlast
44 42129455
firstlast
44 4212 129455
firstlast
44 4212 12945755
firstlast
将r e c [ 1 ] 直接拷入t e m p [ 0 ]
处理r e c [ 2 ],修改l a s t
处理r e c [ 3 ],修改f i r s t
处理r e c [ 4 ],修改f i r s t
处理r e c [ 5 ],修改l a s t
处理r e c [ 6 ],修改f i r s t
处理r e c [ 7 ],修改l a s t
图8,2 示例2 _ 路插入排序的过程
//2_路插入排序
//数组 rec为待排序的序列, count为排序元素的个数
void insertSortBinary(int rec[],int count)
{ int *temp=new int[count]; //分配辅助空间
temp[0]=rec[1];
//第一个元素直接放入辅助数组, 形成初始的有序表
int first=last=0; //有序表首元和尾元的下标
for(int inx=2; inx<=count; inx++)
//从第二个元素起依次做插入排序
{ if(rec[inx]<temp[0]) {
//新插元素比有序表中间元素还小
for(int i=first; temp[i]<=rec[inx];
i=(i+1)%count )
temp[(i-1+count)%count]=temp[i];
temp[(i-1+count)%count]=rec[inx];
//插入待插元素
first=(first-1+count)%count;
}else { //新插元素比有序表表中间元素还大
for(int i=last;temp[i]>rec[inx];i--)
temp[i+1]=temp[i];
temp[i+1]=rec[inx]; //插入待插元素
last++;
}
}
for(int inx=0; inx<count; inx++)
rec[inx+1]=temp[inx]; //复制回原数组
delete[] temp; //释放空间
}
在上面的算法中，确实在一定程度
上减少了数据移动的次数，但仍旧没有
完全解决数据移动的问题。由第二章线
性表中的知识，我们知道：要想 彻底提
高数据移动的效率，就应该使用链表结
构的存储方式。 下面就介绍用数组实现
的 静态链表 完成的插入排序。
8.2.4 表插入排序
当希望在排序过程中不移动记录时，
我们可以借助链表增删节点时的思想，
用数组来实现链表的特征 。在链表中，
每个节点都由数据域和地址域两部分组
成。类似的,让数组元素也由数据域和
地址域组成。一个元素地址域中记录的
是逻辑上该元素直接后继的下标值 。也
就说,数组中物理地址相邻的两个元素
在逻辑上不一定前后相接 。
72 1578 8192712
15 7227 1219788
0 64 5321
-
0 1 2 3 4 5 6 7下标:
-
7
0 1 2 3 4 5 6 7下标:
15 7227 1219788
∧
头指针:
数据域:
地址域:
( a ) 用数组存储
( b ) 用单链表存储
( c ) 用静态链表存储
图8, 3 存储线性表 L=(72,12,27,19,78,8,15) 的三种方法
地址域中
表示的先
后关系
//静态链表节点 （ 数组元素 ） 的类型声明
struct SLNode
{ int value; //假定数据为整型
int next; //记录下一元素的地址下标
};
//静态链表插入排序 。
//数组 rec为待排序的序列, count为排序元素的个数
void insertSortStaticTable(int rec[],int
count)
{ SLNode tmp=new SLNode[count+1];
//数据元素从 1号下标开始存储
int inx;
for(inx=1; inx<=count; inx++)
tmp[inx].value＝ rec[inx];
tmp[0].next=1;
//有序表中仅有一个元素, 该元素下标为 1，
//tmp[0].next为头指针
tmp[1].next =0; //地址域为零表示该元素为尾元
int curr,pre;//存数组下标的变量, 起指针变量的作用
for(inx=2; inx<=count; inx++)
{ pre=0; curr=tmp[0].next;
//curr指向首元, pre为首元的前驱, 用 0表示空
while(curr!=0&&
tmp[curr].value<=tmp[inx])
//有序表中找待插位置
{ pre=curr; curr=tmp[curr].next; }
tmp[inx].next=curr; tmp[pre].next=inx;
//将当前元素插到静态链表中的合适位置
}
for(inx=1,curr=tmp[0].next;inx<=count;inx++)
{ //遍历链表依次将元素移回
rec[inx]=tmp[curr].value;
curr=tmp[curr].next;
}
delete[] tmp;
}
上面的算法中，由于引入了静态链
表这个辅助空间，故空间复杂度为 O(N)。
移动次数就是原数组与辅助数组之
间的两次互相赋值，故为 2N；
在关键字比较的操作上，效率与前
述算法一致，故时间复杂度为 O(N2)。
8.2.5 希尔排序
在分析直接插入排序的时间复杂度时，可
以看到：如果数据序列本身已是升序的，那么
时间复杂度为 O(N)。因此，如果能够保证在使
用直接插入排序之前，数据序列已经基本有序，
则时间复杂度就会基本接近 O(N)。借助于这种
思路，我们 希望一个乱序的数据序列在每一轮
操作中，较大的数据尽快地跳到序列较后的部
分，而较小的数据尽快地跃到序列较前的部分。
这样经过几轮之后，序列已经基本有序，在此
基础上再使用一次直接插入排序即可。
为了能够使数据尽快跳到自己应该
在的位置附近，就不能向以前一样：先
依次同位置相近的元素作比较互换等操
作。因为即使换了好几次，元素仍旧停
在原位置附近。我们 应让位置离得较远
的元素进行比较和互换,这样才能达到
前述的要求。
希尔排序（ Shell Sort）又称, 缩小增
量排序, 正是基于上述这种思想进行的排序操
作。
该排序方法将序列中的元素 分成小组,同
组元素之间的跨度称作, 增量, 。对于同组的
元素进行直接插入排序，每一轮对各组元素都
进行一遍直接插入排序。 每轮之后，都会缩小
增量，减少组数 。当经过几轮之后，数据 各元
素已经基本有序，这时候将增量缩小至 1，也
就是说所有元素都成了一组，在最后这一轮操
作中，使用直接插入排序对所有元素进行排序
即可。
44 5794 12421255- 766 44
44 5794 12421255- 766 44
12 5794 44421255- 766 44
12 5794 44421255- 766 44
12 5794 4442655- 7612 44
12 5794 4442655- 7612 44
12 5776 4442655- 9412 44
初始状态
第一轮
增量为5
12 5776 4442655- 9412 44
6 5744 44421255- 9412 76
6 5744 44421212- 9455 76
6 5744 44421212- 9455 76
6 5544 44421212- 9457 76
第二轮
增量为2
第三轮
增量为1
由上面排序的实例，可以看出希尔排
序 不是稳定 的排序方法。
如果在 N个元素进行排序时，增量
inc按照规则
（ inc0=N/3,inci+1=inci/2）
取值，那么希尔算法的实现如下：
//希尔插入排序
//数组 rec为待排序的序列, count为排序元素的个数
void insertSortShell(int rec[],int count)
{ int hold,curr;
//可以在下面的算法中用 rec[0]作临时变量, 代替 hold
for(int inc=count/3; inc>=1; inc/=2)
//当增量为 1时, 作最后一次插入操作
for(int inx=inc+1; inx<=count; inx++)
{ hold=rec[inx]; curr=inx-inc;
while(curr>=1 && hold<rec[curr])
{ rec[curr+inc]=rec[curr];
curr-=inc;
}
rec[curr+inc]=hold;
//将待插入元素插到合适的位置
}
}
}
关于增量的选择，有很多经验与看
法，这里不再叙述。希尔排序所用的时
间是一系列增量的函数，增量序列的不
同，会导致时间复杂度略微不一样。有
经验数据表明，希尔排序时间复杂度为
O(N5/4)。
8.3 选择排序
选择排序是指在排序过程中的
每一轮, 按照某种方法选择出当前未
排序部分中的最小值, 把它放在已排
序部分的首部, 随着排序过程的进行,
已排序部分变大, 未排序部分变小 。
直到比较 N-1轮之后, 所有元素都在
有序部分内, 排序过程结束 。
8.3.1 直接选择排序 (Straight
selection sort)
直接选择排序，又称简单选择排序
N个元素进行直接选择排序的过程如下：
在第一轮,从下标为 1的数组元素开始选出最
小的元素，把它与数组下标为 1的元素互换，这
时已排序部分长度为 1；
第二轮,从下标为 2的数组元素开始在剩余
的 N-1个元素中选出最小的元素，让它与数组下
标为 2的元素互换，这时已排序部分长度为 2；
……
从下标为 N-1的数组元素开始,
在剩下的两个元素中选出最小值，将
最小值放在下标为 N-1的数组元素中。
由于 N个元素中 N-1个元素都已经放到
了合适的位置，所以第 N个元素也已
经放到了合适的位置。
整个过程只需 N-1轮 。
//直接选择排序
//数组 rec为待排序的序列, count为排序元素的个数
void selectSortSimple(int rec[],int count)
{ int min,temp; //min存放当前轮的最小元素下标；
//temp是用于交换的临时变量
for(int inx=1; inx<count; inx++)
{ min=inx; //设该轮中未排序部分的首元为最小值
for(int curr=inx+1; curr<=count; curr++)
//找出该轮中未排序部分真正的最小值
if(rec[curr]<rec[min]) min=curr;
if(min!=inx)
//如果未排序部分的首元不是最小值, 做交换操作
{ temp=rec[inx]; rec[inx]=rec[min];
rec[min]=temp;
}
}
}
算法中：
每一轮一般都要在最后做交换操作。
一次交换涉及到 3个赋值语句，所以有
3(N-1)次赋值操作。而比较操作执行的
次数为 (N-1)+…+2+1，所以 时间复杂度
仍为 O(N2)。
算法中在作交换操作时借用了一个
辅助变量 temp，故 空间复杂度 为 O(1)。
8.3.2 堆排序 (Heap Sort)
最大堆 与 最小堆
如果 完全二叉树 各节点的关键字之间满
足以下的关系, 我们就称其为 最大堆 。
K≥ Kleft和 K≥ Kright
其中 K为某节点的关键字, Kleft为该
节点左子 （ 如果左子存在 ） 的关键字,
Kright为该节点右子 （ 如果右子存在 ） 的
关键字 。
类似的，可以得到 最小堆 的定义：
如果 完全二叉树 各节点的关键字之
间满足以下的关系，我们就称其为最小
堆。
K≤ Kleft和 K≤ Kright
其中 K为某节点的关键字,Kleft为
该节点左子（如果左子存在）的关键字
,Kright为该节点右子（如果右子存在
）的关键字。
由 最大堆 的定义能够知道,
一个二叉树如果是最大堆，那么其 根
的关键字 一定是该二叉树中所有节点关键
字中的 最大值 。
72
7112219
27 12
8
78
15 19
3
625
4 1
( a ) 最大堆 ( b ) 最小堆 ( c ) 该完全二叉树不是堆
如果用 一维数组 （数组下标为 0的空间不用，
从下标为 1的空间开始）来存储最大堆，那么
当前节点 的数组下标 R与其左子、右子 （假设
左子、右子存在）对应的数组下标 Rleft、
Rright之间的关系满足：
Rleft=2R,Rright=2R+1
17
11
161514
12 13 11 1715 16141312-
1 7654320
当把 一维数组 中各元素看成是一个
完全二叉树 中各节点时,
我们通过一定的方法，把数组 调整
成最大堆（堆的初始建立），这样最大
的元素就位于下标为 1的地方，之后让
其与下标为 N的元素互换，也就是让最
大元素放在了它该放的地方。
排序 第一轮 结束。
由于数组 1号下标的位置换进了新元
素，所以 原来的最大堆可能遭到了破坏，
我们再按照某种方法对其进行调整（ 堆的
调整 ），将数组前 N-1个元素再次构成一
个 最大堆,调整后下标为 1的位置中存储
的是 N-1个元素中的最大值，把它与数组
下标为 N-1的元素互换，这样整个序列的
次大元素也放到了该放的地方,
排序 第二轮 结束。
继续按照这种方法进行，直到 N-1轮
全部完成，所有数组元素就会变成有序
的序列。
显然这种思想仍旧属于选择排序的
方法。由于 排序过程中借助了堆,所以
称为 堆排序 。
该方法是 威洛姆斯 在 1964年提出的。
只要解决上面提到的两个问题：
堆的初始建立 与 堆的调整,
我们就可以完成排序。
先来看 第二个问题,在已有的最大堆上
让首元（根）与尾元（最后一个叶子）互换。
互换后,原来的尾元不再归入新一轮的研究
范围内。在新的研究范围内，由于互换使得
新首元不一定是最大值，所以要对其进行向
下的调整，使得新研究范围内所涉及到的节
点构成最大堆。
96
94238
83 27
( a ) 最大堆
9
964238
83 27
( b ) 准备调整
83
964238
9 27
( c ) 与其左子互换
83
96938
42 27
( d ) 与其右子互换
堆调整的算法
算法中尽量避免互换操作，而是在调整过
程中只让较大的元素上浮，同时记住下降位置
的下标，直到停止调整时，一次将待调整元素
赋值到相应位置。
//在考察范围内,low为待调整元素的下标 (考察范围的起始下
//标 ),high为考察范围的终止下标
void reHeap(int rec[],int low,int high)
{ int curr=rec[low];
//将待调整元素存入临时变量 curr中
int bigger=2*low; //先设定待调整元素左子为较大者
while(bigger<=high) //若仍在考虑范围内
{ if(bigger<high
&& rec[bigger]<rec[bigger+1])
//若右子存在, 且较左子大
while(bigger<=high) //若仍在考虑范围内
{ if(bigger<high
&& rec[bigger]<rec[bigger+1])
//若右子存在, 且较左子大
bigger++; //bigger为左子右子中较大者下标
if(curr>=rec[bigger]) break;
//带调整元素已经找到最后位置, 不用继续下降
else //上浮较大者,为下一次迭代作准备
{ rec[low]=rec[bigger];
low=bigger;
bigger=2*bigger;
}
}
rec[low]=curr; //将待调整元素存入到合适位置
}
接下来讨论前述的第一个问题,
如何把乱序的一维数组调成最大堆。
数组所有元素对应一棵完全二叉树。
二叉树中 叶子节点 不需要进行调整，所以
只考虑树中那些非叶子节点。
由于堆也是递归结构，当左子树与右子树
已经是堆时，再对根进行调整才是有效的，所
以我们调整的次序是从 最后一个非叶子节点 开
始处理，按照数组下标 从后往前 进行，直到最
后再处理根节点。
因为最后一个叶子节点的父节点就是最后
一个非叶子节点，所以讨论最后一个非叶子节
点的下标值。
N个元素的数组（ 0号下标空间不用），
最后一个节点下标为 N,如果 它是父节点的右
儿子（ N为奇数），则父节点下标为 (N-1)/2；
如果 它是父节点的左儿子（ N为偶数），则父
节点下标为 N/2。
注意, C++语言中整除运算只取商，故对
于 N个元素的完全二叉树来说，其最后一个非叶
子节点在数组中的下标对应的 C++语言表达式为,
（ N/2）
堆初始建立的算法
//建堆操作,数组 rec为待建堆的序列, count为元
素的个数
void buildHeap(int rec[],int count)
{ for(int inx=count/2; inx>=1; inx--)
reHeap(rec,low,count);
}
//堆排序
//数组 rec为待排序的序列, count为排序元素的个数
void selectSortHeap(int rec[],int count)
{ int temp; //用于变量互换,可以用 rec[0]代替
buildHeap(rec,count);
//堆的初始建立, 选出最大元
for(int round=count; round>1; round--)
//做 count-1轮
{ temp=rec[round];
rec[round]=rec[1];
rec[1]=temp; //本轮最大元放入正确位置
reHeap(rec,1,round-1); //在新范围内调整堆
}
}
在算法中可以看到，
时间主要耗费在 建堆 与 对堆的调整
上。
可以证得，堆在最坏的情况下，时
间复杂度为 O(N*log2N)，这已经是排
序的最好效率了。
空间复杂度仍为 O(1)。
8.4 交换排序
交换排序的基本方法是：
两两比较待排序元素, 并交换不满足
顺序要求的那些偶对, 直到全部满足为止 。
这里介绍两种交换排序, 一种是最简
单的冒泡排序 (Bubble Sort),另一种是
效率很高的快速排序 (Quick Sort)。
8.4.1 冒泡排序
8.4.2 分治法与快速排序
冒泡排序的过程很简单，首先将第 1个数
据的关键字和第 2个数据的关键字进行比较，
若为逆序（前大后小），则将两个记录交换之。
再比较第 2个和第 3个数据的关键字，依此类推，
直到第 N-1个数据和第 N个数据进行比较、交
换为止。如此经过一轮排序，使得关键字最大
的数据被安置到数组最后一个位置上。
然后，对前 N-1个数据进行同样的操作，
则具有次大关键字的数据被安置在数组中倒数
第二个位置上。
重复以上过程直至没有记录需要交换为止。
8.4.1 冒泡排序（起泡排序）
20
30
10
40
20
0
20
30
10
40
20
0
20
10
30
40
20
0
20
10
30
40
20
0
20
10
30
20
40
0
20
10
30
20
0
40
20
10
30
20
0
40
10
20
30
20
0
40
10
20
30
20
0
40
10
20
20
30
0
40
10
20
20
0
30
40
( a ) 第1 轮排序 ( b ) 第2 轮排序
10
20
20
0
30
40
10
20
20
0
30
40
10
20
0
20
30
40
10
20
0
20
30
40
10
20
0
20
30
40
10
20
0
20
30
40
10
0
20
20
30
40
10
0
20
20
30
40
0
10
20
20
30
40
( c ) 第3 轮排序 ( d ) 第4 轮排序 ( e ) 第5 轮排序
//冒泡排序
//数组 rec为待排序的序列, count为排序元素的个数
void exchangeSortBubble(int rec[],int count)
{ int temp;
//用于交换的临时变量,可以用 rec[0]代替
bool isChanged=true; //设为 true,进入循环
for(int round=1; isChanged && round<count;
round++)
{ isChanged=false; //假定本轮没有逆序的偶对
for(int inx=1; inx<=count-round; inx++)
if(rec[inx]<rec[inx+1]) //逆序的偶对
{ temp=rec[inx];
rec[inx]=rec[inx+1];
rec[inx+1]=temp;
isChanged=true; //本轮出现了逆序偶对
}
}
}
算法中，每一轮中相邻元素都要进
行比较，只要逆序就进行交换。
最坏情况下,每次比较完都要交换
数据，这时比较与交换的次数都是 (n-
1)+(n-2)+…+1，所以时间复杂度为
O(N2)。
8.4.2 分治法与快速排序
在完成一个比较复杂的任务时，如果不能
直接解决，我们总会将问题分解成若干小问题，
集中精力各个击破。如果每个小问题我们能够
顺利解决，那么整个大问题也随之解决了。
第三章中递归问题 的相关知识，我们可以
看到分治法的影子。
第五章中广义表 的处理以及 第六章树形结
构 中一些操作的实现（如遍历等），都用到了
类似的思想。
同样，在排序算法中，我们仍旧可以采用
分治法,快速排序 就是其中之一。
快速排序的思想是：
通过某种方法在待排序的数据序列中
选取一个数据，并以此数据为基准值，采
用一定的方法进行处理，从而将整个序列
分成三部分。
基准值处于序列中间的某个位置；该
位置之前，数据的关键字都小于该基准值；
该位置之后，数据的关键字都大于或等于
该基准值。这样就已经把基准值放到了正
确的位置上。
第一轮结束之后，按照分治的思想，
解决基准值之前以及基准值之后的两个
子序列，只要这两个子序列完成了排序
工作，整个序列的排序就全部结束了。
显然，两个子序列可以采用 递归 的
方式进行排序。
递归的终止条件：
一种情况 是子序列为空，这时不需
要排序； 另一种情况 是子序列只有一个
元素，也不需要排序。
其实，真正在对较多元素排序时，
前几轮会使用快速排序的方法，而当每
个子序列中元素个数较少时，就会转而
用一些简单的排序方法（如冒泡排序或
直接选择排序等等）
使用快速排序，基准值的选择比较关
键。 当基准值选得好时，其前后两个子序
列长度近似；但当基准值选得不好时，在
极端情况下，一个子序列为空，另一个子
序列是原来序列中除去基准值的所有元素，
这时 前后两个子序列极端不平衡，起不到
,折半, 的目的,效率自然不高。
但由于排序元素大小是随机分布的，
所以没有哪一种基准值的选取规则适于所
有序列，因此,我们只能在一定程度上采
取某些策略，但并不能够保证这些策略在
任何情况下都会起作用。
在下面的算法中，为了使所取的
基准值将来尽量放在数组里居中的位
置上，我们 先选出首元，尾元以及位
置处于数组中间的元素，对这三个数
据先排序，然后取出居中的元素 作为
基准值。
44 5794 82427655- 7686 84
44 5776 82427655- 9486 84
76 5744 82427655- 9486 84
基准值
76 5744 82427655- 9486 84
基准值
wall
curr
76 5744 82427655- 9486 84
基准值
wall
curr
76 5744 82427655- 9486 84
基准值
wall
curr
76 5744 82764255- 9486 84
基准值
wall
curr
76 5776 82444255- 9486 84
基准值
wall
curr
76 5776 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
57 7676 82444255- 9486 84
wall基准值
可以看到，快速排序是 不稳定 的
排序。
//快速排序
//数组 rec为待排序的序列, count为排序元素个数
void exchangeSortQuick(int rec[],int
count)
{ quickSort(rec,1,count);
//调用递归函数, 完成快速排序
}
//递归函数, 完成快速排序
void quickSort(int rec[],int 1ow,int high) {
int pivot; //基准值的位置
if(low<high) {
pivot=partition(rec,low,high);
//将序列分成三部分
quickSort(rec,1,pivot-1);
//递归处理基准值之前的子序列
quickSort(rec,pivot,high);
//递归处理基准值之后的子序列
}
}
//将序列分成三部分,小于基准值的子序列,基准值本身,
大于基准值的子序列
//返回值为,排序后基准值在数组的最终位置
void partition(int rec[],int 1ow,int high)
{
int mid=(low+high)/2;
int temp;
//用于交换的临时变量,可用 rec[0]代替
//首元,位置居中的元素,尾元三个元素从小到大排序
if(rec[low]>rec[mid]) {
temp=rec[low];
rec[low]=rec[mid]; rec[mid]=temp;
}
if(rec[low]>rec[high]) {
temp=rec[low];
rec[low]=rec[high]; rec[high]=temp;
}
if(rec[mid]>rec[high]) {
temp=rec[mid];
rec[mid]=rec[high]; rec[high]=temp;
}
temp=rec[low];
rec[low]=rec[high];
rec[high]=temp; //基准值放在首元位置
int curr; //curr指向当前处理元素
int wall=1ow;
//wall指向已排序部分中小于基准值的最后元素,
//初始值为首元位置
for(curr=low+1; curr<=high; curr++)
if(rec[curr]<rec[low]) {
temp=rec[wall+1];
rec[wall+1]=rec[curr];
rec[curr]=temp; wall++;
}
temp=rec[low];
rec[low]=rec[wall]; rec[wall]=temp;
//将基准值放在最终位置上
return wall;
}
快速排序是目前各种内部排序方法
中速度最快的一种，可以证明其 平均时
间复杂度为 O(N*log2N)。
算法由于使用递归方法，所以其辅
助空间为使用递归时栈空间的最大深度。
最差情况下：每一轮过后基准值前后的
子序列都极端不平衡（一边为空），这
时栈的深度为 N，故 空间复杂度为 O(N)。
8.5 归并排序
快速排序采用了分治与递归的思想：
首先选出基准值，然后将序列分成三部
分，基准值居中，前面都是小于它的元
素，后面都是不小于它的元素，在将基
准值放到最终位置后，再分步解决前后
两个子序列的排序问题。这显然是从大
规模问题向小规模问题转换的思路。
如果换一种角度：在解决问题时，
从较小的规模向较大的规模转换，即，
先有两个已经排好序的子序列前后放
置，然后再集中精力将它们归并成一
个大的有序序列，用这种思路也同样
可以完成排序的任务。
显然，这种归并排序 (Merging
Sort)仍旧是分治与递归思想的应用。
八个元素不断归并的过程,
44 5794 82427655 86
44 5782 94784255 86
42 8657 82785544 94
42 8678 82575544 94
图中第一轮准备归并的初始状态
则是将原序列不断进行分解的结果,
由 8个元素一组分成 4个元素一组，
再分成 2个元素一组，直到分成每个
元素自己一组时，停止分解。
因为此时每组元素本身已经是有
序的。在此基础上，才开始进行归并。
归并过程的具体实现思想在例
2.2中已经介绍过，这里不再重复。
//归并排序 。 数组 rec为待排序的序列,
//count为排序元素的个数
void mergeSort(int rec[],int
count)
{ sortMerging(rec,1,count);
//调用递归函数完成归并排序,结
//果存在 temp数组中
}
//递归函数, 完成归并排序
void sortMerging(int rec[],
int 1ow,int high)
{ if(low<high)
{ int mid=(low+high)/2;
sortMerging(rec,low,mid);
sortMerging(rec,mid+1,high);
merge(rec,low,mid,high);
}
}
//实现两个有序序列的归并操作,
//归并后的序列仍然保持有序
//rec中第一个序列的下标是从 low到 mid,
//第二个序列的下标从 mid+1到 high
void merge(int rec[],int low,int
mid,int high) {
int curr1,curr2,curr;
//分别指向第一个序列, 第二个序列, 目
//标序列的当前元素
int *temp=new int[count+1];
//开辟临时数组,暂存数据 (0号下标不用 )
curr1=low; curr2=mid+1;
//指向两个序列的首元素, 准备开始比较
curr=low;
//为了方便,temp数组也只用一部分,从
//low到 high
//当两个序列都有元素时,经过比较选出小者
while(curr1<=mid && curr2<=high)
if(rec[curr1]<=rec[curr2]) {
temp[curr]=rec[curr1];
curr1++; curr++;
}else {
temp[curr]=rec[curr2];
curr2++; curr++;
}
//第二个序列先处理完后,处理第一个序列中
//剩余元素
while(curr1<=mid) {
temp[curr]=rec[curr1];
curr1++; curr++;
}
//第一个序列先处理完后,处理第二个序列中
//剩余元素
while(curr2<=high) {
temp[curr]=rec[curr2];
curr2++; curr++;
}
//将所有元素拷回到原数组
for(curr=low; curr<=high; curr++)
rec[curr]=temp[curr];
delete[] temp; //释放临时空间
}
归并排序是 稳定 的排序。
N个元素在排序过程中一共要做
log2N轮。每一轮进行合并时，所有元素
都要被比较，故其 时间复杂度为
O(N*log2N)。
使用的辅助空间一方面是在归并过程
中使用的 N个元素的暂存空间，另一方面
是递归操作引起的栈空间开销（最大深度
应为 log2N），所以 空间复杂度为 O(N)。
8.6 基数排序
基数排序 (Radix Sort)是我
们最后讨论的一种内部排序算法，
它与其他的内部排序算法思想有着
很大的不同。前面几节我们介绍的
各种排序方法都是 以关键字的比较
与数据的移动 为主，但基数排序却
主要 借助, 分配, 和, 收集, 两种
操作 来完成排序任务。
利用第三章所讲的队列来做暂
存数据的辅助空间 。
为了简化讨论, 我们假定待排
序的 N个关键字都在 0至 999之间 。
下面叙述排序过程 。
第一步：先初始化十个队列，每个队
列中都存放十进制整数。我们分别命名十
个队列为,0号队列,1号队列,2号队
列,…,9号队列。244 457894 82642176355- 17686 984
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
244 457
89482
642 176355
176
86
984
第二步：依次取出数据，按照
数据的个位数依次插入对应的队列。
如数据 231，其个位数为 1，所以将
它插入 1号队列。所有元素都被分
配到十个队列之后，完成第一次
,分配, 操作。
第三步,按照队列号的大小依次取出
队列中元素存入原数组。
也就是说，先依次取出 0号队列的所
有元素，并从原数组下标为 1处开始，一
个挨一个地存放数据；当 0号队列中的数
据全部被取出后，开始依次取出 1号队列
的所有元素继续放入数组；当 1号队列的
数据被全部取出后，开始依次取出 2号队
列的所有元素继续放入数组； …；直到 9
号队列的所有元素全部被取出并放入数组。
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
244 457
89482
642 176355
176
86
984
642 176984 35589424482- 45786 176
第一次, 收集, 操作结束 。到此为止，所有数据
已经按照末位数的大小，从小到大排好了顺序。
第四步，按照数据的十位数依次插入
对应的队列。
如数据 231，其十位数为 3，所以将
它插入 3号队列。
所有元素都被分配到十个队列之后，
完成第二次, 分配, 操作 。
注意，到此为止，同一个队列中所有
数据的十位数都是一样的，而且末位数是
按照从小到大的顺序存放的。因为在入队
时，个位数字小的元素先进入队列，这是
第三步操作的结果决定的。
642 176984 35589424482- 45786 176
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
642 176
984
355 894
244
82
457
86
176
第五步，按照队列号的大小依次
取出队列中元素存入原数组。操作方
法与第三步完全相同。
第二次, 收集, 操作结束 。到此
为止，所有数据已经按照末两位数的
大小，从小到大排好了顺序。
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
642 176
984
355 894
244
82
457
86
176
642 82176 176457355244- 894984 86
第六步，按照数据的百位数依次插入
对应的队列。
如数据 231，其百位数为 2，所以将
它插入 2号队列。所有元素都被分配到十
个队列之后,完成第三次, 分配, 操作 。
注意,到此为止，同一个队列中所有
数据的百位数都是一样的，而且末两位数
是按照从小到大的顺序存放的。因为在入
队时，末两位数字小的元素先进入队列，
这是第五步操作的结果决定的。
642 82176 176457355244- 894984 86
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
64282 176
176
457355244 894 984
86
第七步，按照队列号的大小依次
取出队列中元素存入原数组。操作方
法与第三步完全相同。 第三次, 收集,
操作结束。
到此为止，所有数据已经按照末
三位数的大小（数据本身值的大小），
从小到大排好了顺序。到此为止，排
序结束。
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
82 457244 35517617686- 984642 894
64282 176
176
457355244 894 984
86
在上面的操作中，开辟的辅助空间就
是十个队列，由于它们最终要容纳下所有
的待排序数据，所以队列所占总空间数为
N。由此得到空间复杂度为 O(N)。
从描述过程看出，排序每一轮都要经
历依次, 分配, 操作和一次, 收集, 操作，
所以每一轮数据经过两次移动；而排序的
轮数是由最大数据关键字的长度 R决定的
（例子中最大数是三位数，故排序共做三
轮），由此知时间复杂度为 O(R*N)。
8.7 外部排序概述
对文件（第十章将专门介绍文件）进
行排序，是文件上十分重要的运算，在许
多地方都要用到。
通常情况下，由于文件很大，无法把
整个文件的所有记录同时调入内存中进行
排序，即：无法直接进行内部排序，从而
需要研究外存设备上（文件）的排序技术，
我们称这种排序为 外部排序 。
外部排序方法与各种外存设备的
特征有关。
外存设备大体上可分为顺序存取
（例如磁带）和直接序取（例如磁盘）
两大类，所以，外部排序通常又可分
为磁盘文件排序和磁带文件排序两大
类。
两类排序的基本步骤相类似，主
要不同之处在于初始归并段在外存储
介质中的分布方式。
一般来说，在外存设备上排序
的最通用方法是 归并排序法,这种
方法基本上由 两个相对独立的阶段
组成 。
首先,按可用内存大小，将外存上含 n个
记录的文件分成若干长度为 L的子文件（或
段），用某种有效的内部排序方法分别将这
些段读入内存进行排序，并将排序后得到的
有序子文件重新写入外存，通常称这些有序
子文件为, 归并段, 或, 顺串, ；
然后,把第一阶段所生成的顺串进行 逐
趟合并 （例如通过若干趟 2路合并），使顺串
（有序的子文件）逐渐由小变大，直至最终
变为一个顺串为止，这时整个文件已经成为
,有序文件, 。
由于在排序过程中，需要读写外部存储设
备当中的文件，而这样的操作显然比较费时，
所以提高外部排序的效率应主要着眼于 减少外
存信息的读 /写次数,而 不是 我们在内部排序中
关注的两个操作：关键字进行的比较次数和数
据互换移动的次数。
针对这样的情况，可以从不同角度减少读
写外存的次数：为了减少归并次数，使用 多路
平衡归并 （可以借助于, 败者树, 完成）；为
了尽量得到较长的, 归并段,,采用 置换选择
排序 的方法，并进一步对所得长度不等的归并
段构造 最佳归并树 等等。
8.8 本章小结
基本内容：
内部排序：
插入排序
选择排序
交换排序
归并排序
基数排序
在内部排序中我们主要关注两类
操作：关键字的比较次数与数据元素
位置的移动与互换次数 。
对于外部排序, 主要使用归并的思
想, 另外考虑到读取外存的时间较计
算与内存访问时间来说非常耗时, 所
以在外部排序中尽量要注意减少外存
读取的次数 。
在各种排序算法中，时间效率较高
的有希尔排序、堆排序和快速排序三种。
基数排序由于采用的是分配收集的
操作，所以它与其他内部排序的算法在
思路上有着较大的差别。
在介绍快速排序与归并排序时，我
们又使用了, 分治法, 的思想，将复杂
的问题化大为小，以便各个击破，分而
治之。
?基本要求：
深刻理解排序的 定义 和各种排序方
法的 特点, 并能加以灵活运用 。
基于, 关键字间的比较, 进行排序
的方法可以按排序过程所依据的不同原
则分为 插入排序, 交换排序, 选择排序,
归并排序 和 基数排序 五类 。 了解各种方
法的排序过程及其依据的原则 。
理解排序方法, 稳定, 和, 不稳定,
的含义, 弄清楚在什么情况下要求应用
的排序方法必须是稳定的 。
掌握各种排序方法的时间复杂度的
分析方法 。 能从, 关键字间的比较次数,
分析排序算法的平均情况和最坏情况的
时间性能 。 按平均时间复杂度划分, 内
部排序可分为三类,O(N2)的 简单排序 方
法, O(N*logN) 的 高 效 排 序 方 法 和
O(R*N )的 基数排序 方法 。
希尔排序, 快速排序, 堆排序
和归并排序等高效方法是本章的学
习重点和难点 。
了解外部排序的两个阶段, 及
外部排序的基本思想 。
进一步掌握, 分治法, 的思想 。
8.1 排序技术概述
8.2 插入排序
8.3 选择排序
8.4 交换排序
8.5 归并排序
8.6 基数排序
8.7 外部排序概述
8.8 本章小结
8.1 排序技术概述
从操作角度看，排序是线性
结构的一种操作。
为了提高排序效率，人们已
对排序进行了许多研究，提出了
许多方法。
排序就是按照某种规则，
为一组给定的对象排列次序。
排序的 主要目的 是：在排好
序的集合中能够快速查找（检索）
一个元素。
所谓, 内部, 排序，就是指整个排
序过程都是在内存中进行的。
如果排序的数据项很多，内存不足
以存放得下全部数据项时，排序过程就
需要对外存进行存取访问，也就是, 外
部, 排序。
本章的内容以内部排序为主，对外
部排序只进行简单地介绍。
我们把查找时关注或使用的数据
叫做关键字（ key），它可以是数据
信息当中的一个属性，也可以是几个
属性的组合。
关键字可以代表其所在的那项数
据信息。在这项数据信息当中，关键
字所取的值叫做键值。
在本章中，为了突出排序
算法本身的内容，我们简化各项
数据的属性个数。
假设待排序的数据都只有
一个属性，这个属性就是关键字，
并且关键字的类型是 整型 。
我们可以把排序看成是一种定
义在某种数据集合上的操作。
本章所讲的各种内部排序，都
可以认为是在一维数组这种线性数
据结构上定义的操作。其功能是将
一组任一排列的数据元素重新排列
成一个按键值有序的序列。
对排序更为确切的定义,
假设 {D1,D2,?,DN}为含有 N项数据
的序列, 其中 Di（ 1≤ i≤ N） 表示序列中
第 i项数据, N项数据对应的键值序列为
{K1,K2,?,KN}。
排序操作是将这些数据重新排列成一
个 按 键 值 有 序 的 新 序 列
{Rp1,Rp2,?,RpN},使得相应的键值满
足条件 p1≤ p2≤ ? ≤ pN（ 此时新序列成
,升序, ） 或 p1≥ p2≥ ? ≥ pN（ 此时新
序列成, 降序, ） 。
注意,在上面定义叙述中所用到
的 ≤ 或 ≥ 这两个比较符号，是通用意义
上的关系比较符。
对于数值型信息，它是表示关系的
小或大；对于字符串来说，它是指在字
典中所排列位置的前或后。
对于不同类型的数据，我们可以规
定不同的比较规则来反映 ≤ 或 ≥ 的含义。
如果在数据序列中，有多个具
有相同键值的数据，在排序前后，
这些数据之间的相对次序保持不变，
这样的排序方法被称作是 稳定 的，
否则被称为是 不稳定 的。
分析算法效率：
1,从空间角度进行：主要是看
执行算法时所需附加空间的数量；
2,从时间角度进行：从两种操
作入手进行分析。
键值的比较次数
数据移动的次数
8.2 插入排序
插入排序 是指在待排序的序列中，分
成两部分：前面为已经排好序的部分，后
面为仍未排好序的部分。
每一轮都从 没有排好序部分 取出首元
素按照大小将其插到前面 已经排好序部分
中的合适位置上。
这样前面已排序部分就多了一个元素，
后面未排序部分同时少了一个元素。该排
序过程不断进行，直到未排序部分的元素
数目为零。
插入排序
将待排序的序列分成两部分：前
面为已经排好序的部分，后面为仍未
排好序的部分。
每一轮都从没有排好序部分取出首
元素按照大小将其插到前面已经排好
序部分中的合适位置上。
这样前面已排序部分就多了一个元
素，后面未排序部分同时少了一个元
素。该排序过程不断进行，直到未排
序部分的元素数目为零。
排序过程如图 8.1所示。
图（ a）为该轮排序前的状态，
图（ b）为该轮排序后的状态，
阴影表示本轮待排序的元素，在图（ b）
中它已经插入到已排好序部分的合适位
置上。
本轮待插入元素
未排好序部分已排好序部分
插入到合
适位置
( a ) 本轮插入前序列状态
未排好序部分已排好序部分
( b ) 本轮插入后序列状态
注意,
在排序过程开始时，直接把序
列中第一个元素认为是已排好序部
分。另外，用整型数组代表排序的
数据元素序列，数组下标为零的元
素我们当作辅助空间，所以从数组
下标是 1的空间开始存储元素序列。
在把待插入元素从未排序部分移入已
排好序部分时，有多种方法，下面逐一介
绍。
8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 2_路插入排序
8.2.4 表插入排序
8.2.5 希尔排序
8.2.1 直接插入排序
直接插入排序
又称简单插入排序。排序过程
中，待插入元素先放在临时空间
hold中，依次让它和前面的元素作
比较，直到发现其应插入的位置，将
其插入。
//不带哨兵的直接插入排序 。
//数组 rec为待排序的序列,
//count为排序元素的个数
void insertSortSimple(int rec[],
int count)
{ int curr,hold;
for(int inx=2; inx<=count;
inx++)
//从第二个元素起依次做插入排序
{ hold=rec[inx]; curr=inx-1;
//从已排好序部分的尾元素开始向前
//查找待插入位置
while(curr>=1 &&
hold<rec[curr])
{ rec[curr+1]=rec[curr];
curr--;
}
rec[curr+1]=hold;
//将待插入元素插到合适的位置
}
}
算法中,while语句的条件表达式由两部
分组成,curr>=1保证数组下标不会越界
（ curr不会被减到低于零,rec[curr]保证
有意义），但这样做就会增加一次条件判断。
为了提高效率，我们把待插入元素先放在
临时空间 rec[0]中，依次让它和前面的元素
作比较，直到发现其应插入的位置，将其插入。
注意 rec[0]起到了, 哨兵, 的作用。因
为 while语句的条件表达式使得 curr不会被
减到低于零。
//改进后的直接插入排序
//数组 rec为待排序的序列, count为排序元
//素的个数
insertSortSimple(int rec[],int
count)
{ int curr;
for(int inx=2; inx<=count;
inx++)
//从第二个元素起依次做插入排序
{ rec[0]=rec[inx];
curr=inx-1;
//从已排好序部分的尾元素开始向前
//查找待插入位置
while(rec[0]<rec[curr])
{ rec[curr+1]=rec[curr];
curr--;
}
rec[curr+1]=rec[0];
//将待插入元素插到合适的位置
}
}
从 while语句的条件表达式得知直接插入
排序是 稳定 的排序算法 。
分析算法中元素比较与移动的次数
如果每轮待插入的元素都是在已排好序
部分中的最大元素，那么每轮比较次数只有
一次（只和已排好序部分的尾元比较一次），
而且不用移动元素。 N个元素的序列只做了
N-1轮的操作，所以标准操作次数 Tmin=(N-
1)*1+(N-1)*0=N-1=O(N)，显然这种方
式对应的情况是原序列已经是升序。
如果原序列是降序, 而最终结果应该是升
序, 故每一轮中待插入元素要和所有已排好
序的元素进行比较 （ 包括哨兵在内 ）, 而且
这些元素都要依次后移 （ 哨兵不后移 ）, 以
便将首元位置空出, 让待插元素插到最前面
的位置 。 这样,
比较次数为：
Tcompare=2+3+…+N=(N+2)*(N-1)/2
移动次数 为：
Tshift=1+2+…+(N-1)=N*(N-1)/2
所以标准操作次数：
Tmax=Tcompare+Tshift=O(N2)。
注意,
上面计算移动记录次数的过程中，并没有
考虑以下两个赋值操作：给哨兵赋值的操作和
将待插元素插到正确位置的赋值操作。
如果将这两项计算在内，那么移动次数都
应再加上 2(N-1)的值。考虑到排序序列中各
元素值是随机取值的，所以它们之间大小排列
也是随机的，因此各种排列概率相同，我们取
最差时间效率与最好时间效率的平均值做为直
接插入排序的平均时间复杂度，为 O(N2)。在
算法中我们多开了一个辅助空间，故空间复杂
度为 O(1)。
8.2.2 折半 插入排序
在向有序表中插入元素的过程中，
直接插入排序采用的方法是：从后向前
依次与有序表中元素作比较。没有充分
利用, 前部分已经有序, 的特性，这种
方法 效率较低 。
考虑 改进 的方法：
设定有序表长度为 L，那么让待插元素 x和
处于 有序表中间位置 的元素 y作比较：
如果待插元素 x大于或等于 y，则说明插入
的位置一定在有序表的后半部分；
如果待插元素 x较小，则说明插入的位置
一定在有序表的前半部分。
无论哪种情况，我们都可以将可能插入的
位置所在的空间长度降至原来长度的一半，故
称, 折半, 插入排序。
对于长度为 L的有序表，大约需要
log2L次的比较就可以确定出待插元素的
位置。因此对于 N个元素的序列来说，进
行 N-1轮的所有比较次数为 O(N*log2N)，
显然优于直接插入法中平均情况下的比
较次数 O(N2)。但是在确定了待插位置之
后，元素移动的次数并没有降下来，所
以时间复杂度仍为有 O(N2)。
算法中仍旧多开了一个辅助空间，
故空间复杂度为 O(1)，保持不变。
void insertSortBinary(int rec[],
int count)
{ int hold; //当前正处理的元素
int btm,top,mid;
for(int inx=2; inx<=count;
inx++)
//从第二个元素起依次做插入排序
{ hold=rec[inx];
btm=1;top=inx-1;
//从已排好序部分的尾元素开始向前
//查找待插入位置
while(btm<=top)
{ mid=(btm+top)/2;
if(rec[mid]<hold)
btm=mid+1;
else top=mid-1;
}
for(int i=inx-1;i>=btm;i--)
rec[i+1]=rec[i];
rec[btm]=hold;
//将待插入元素插到合适的位置
}
}
8.2.3 2_路插入排序
在折半插入排序的基础上，再
针对数据元素的移动进行算法的改
进，就得到 2_路插入排序算法。
我们开设一个辅助数组 temp，其大小为
待排序元素的个数，把它当作是 循环数组 。
将第一个元素放在数组 temp[0]中，并
把它当作是有序表中 处于中间位置 的元素。
从第二个元素开始，每个元素在做插入的
时候，都先与 temp[0]进行比较。
若是 小于 temp[0]，则往它 前面 的有序
表中插； 否则,往其 后面 的有序表中插。
有序表首元素和尾元素的下标分别用
first与 last表示。显然，开始状态下，有
序表中 仅有 temp[0]，所以 first=last=0。
由于多开了辅助数组，所以该算法的空间
复杂度为 O(N)。
- 1242 94125544 57
44
r e c 数组
t e m p 数组
first last
44 55
first last
44 1255
firstlast
44 421255
firstlast
44 42129455
firstlast
44 4212 129455
firstlast
44 4212 12945755
firstlast
将r e c [ 1 ] 直接拷入t e m p [ 0 ]
处理r e c [ 2 ],修改l a s t
处理r e c [ 3 ],修改f i r s t
处理r e c [ 4 ],修改f i r s t
处理r e c [ 5 ],修改l a s t
处理r e c [ 6 ],修改f i r s t
处理r e c [ 7 ],修改l a s t
图8,2 示例2 _ 路插入排序的过程
//2_路插入排序
//数组 rec为待排序的序列, count为排序元素的个数
void insertSortBinary(int rec[],int count)
{ int *temp=new int[count]; //分配辅助空间
temp[0]=rec[1];
//第一个元素直接放入辅助数组, 形成初始的有序表
int first=last=0; //有序表首元和尾元的下标
for(int inx=2; inx<=count; inx++)
//从第二个元素起依次做插入排序
{ if(rec[inx]<temp[0]) {
//新插元素比有序表中间元素还小
for(int i=first; temp[i]<=rec[inx];
i=(i+1)%count )
temp[(i-1+count)%count]=temp[i];
temp[(i-1+count)%count]=rec[inx];
//插入待插元素
first=(first-1+count)%count;
}else { //新插元素比有序表表中间元素还大
for(int i=last;temp[i]>rec[inx];i--)
temp[i+1]=temp[i];
temp[i+1]=rec[inx]; //插入待插元素
last++;
}
}
for(int inx=0; inx<count; inx++)
rec[inx+1]=temp[inx]; //复制回原数组
delete[] temp; //释放空间
}
在上面的算法中，确实在一定程度
上减少了数据移动的次数，但仍旧没有
完全解决数据移动的问题。由第二章线
性表中的知识，我们知道：要想 彻底提
高数据移动的效率，就应该使用链表结
构的存储方式。 下面就介绍用数组实现
的 静态链表 完成的插入排序。
8.2.4 表插入排序
当希望在排序过程中不移动记录时，
我们可以借助链表增删节点时的思想，
用数组来实现链表的特征 。在链表中，
每个节点都由数据域和地址域两部分组
成。类似的,让数组元素也由数据域和
地址域组成。一个元素地址域中记录的
是逻辑上该元素直接后继的下标值 。也
就说,数组中物理地址相邻的两个元素
在逻辑上不一定前后相接 。
72 1578 8192712
15 7227 1219788
0 64 5321
-
0 1 2 3 4 5 6 7下标:
-
7
0 1 2 3 4 5 6 7下标:
15 7227 1219788
∧
头指针:
数据域:
地址域:
( a ) 用数组存储
( b ) 用单链表存储
( c ) 用静态链表存储
图8, 3 存储线性表 L=(72,12,27,19,78,8,15) 的三种方法
地址域中
表示的先
后关系
//静态链表节点 （ 数组元素 ） 的类型声明
struct SLNode
{ int value; //假定数据为整型
int next; //记录下一元素的地址下标
};
//静态链表插入排序 。
//数组 rec为待排序的序列, count为排序元素的个数
void insertSortStaticTable(int rec[],int
count)
{ SLNode tmp=new SLNode[count+1];
//数据元素从 1号下标开始存储
int inx;
for(inx=1; inx<=count; inx++)
tmp[inx].value＝ rec[inx];
tmp[0].next=1;
//有序表中仅有一个元素, 该元素下标为 1，
//tmp[0].next为头指针
tmp[1].next =0; //地址域为零表示该元素为尾元
int curr,pre;//存数组下标的变量, 起指针变量的作用
for(inx=2; inx<=count; inx++)
{ pre=0; curr=tmp[0].next;
//curr指向首元, pre为首元的前驱, 用 0表示空
while(curr!=0&&
tmp[curr].value<=tmp[inx])
//有序表中找待插位置
{ pre=curr; curr=tmp[curr].next; }
tmp[inx].next=curr; tmp[pre].next=inx;
//将当前元素插到静态链表中的合适位置
}
for(inx=1,curr=tmp[0].next;inx<=count;inx++)
{ //遍历链表依次将元素移回
rec[inx]=tmp[curr].value;
curr=tmp[curr].next;
}
delete[] tmp;
}
上面的算法中，由于引入了静态链
表这个辅助空间，故空间复杂度为 O(N)。
移动次数就是原数组与辅助数组之
间的两次互相赋值，故为 2N；
在关键字比较的操作上，效率与前
述算法一致，故时间复杂度为 O(N2)。
8.2.5 希尔排序
在分析直接插入排序的时间复杂度时，可
以看到：如果数据序列本身已是升序的，那么
时间复杂度为 O(N)。因此，如果能够保证在使
用直接插入排序之前，数据序列已经基本有序，
则时间复杂度就会基本接近 O(N)。借助于这种
思路，我们 希望一个乱序的数据序列在每一轮
操作中，较大的数据尽快地跳到序列较后的部
分，而较小的数据尽快地跃到序列较前的部分。
这样经过几轮之后，序列已经基本有序，在此
基础上再使用一次直接插入排序即可。
为了能够使数据尽快跳到自己应该
在的位置附近，就不能向以前一样：先
依次同位置相近的元素作比较互换等操
作。因为即使换了好几次，元素仍旧停
在原位置附近。我们 应让位置离得较远
的元素进行比较和互换,这样才能达到
前述的要求。
希尔排序（ Shell Sort）又称, 缩小增
量排序, 正是基于上述这种思想进行的排序操
作。
该排序方法将序列中的元素 分成小组,同
组元素之间的跨度称作, 增量, 。对于同组的
元素进行直接插入排序，每一轮对各组元素都
进行一遍直接插入排序。 每轮之后，都会缩小
增量，减少组数 。当经过几轮之后，数据 各元
素已经基本有序，这时候将增量缩小至 1，也
就是说所有元素都成了一组，在最后这一轮操
作中，使用直接插入排序对所有元素进行排序
即可。
44 5794 12421255- 766 44
44 5794 12421255- 766 44
12 5794 44421255- 766 44
12 5794 44421255- 766 44
12 5794 4442655- 7612 44
12 5794 4442655- 7612 44
12 5776 4442655- 9412 44
初始状态
第一轮
增量为5
12 5776 4442655- 9412 44
6 5744 44421255- 9412 76
6 5744 44421212- 9455 76
6 5744 44421212- 9455 76
6 5544 44421212- 9457 76
第二轮
增量为2
第三轮
增量为1
由上面排序的实例，可以看出希尔排
序 不是稳定 的排序方法。
如果在 N个元素进行排序时，增量
inc按照规则
（ inc0=N/3,inci+1=inci/2）
取值，那么希尔算法的实现如下：
//希尔插入排序
//数组 rec为待排序的序列, count为排序元素的个数
void insertSortShell(int rec[],int count)
{ int hold,curr;
//可以在下面的算法中用 rec[0]作临时变量, 代替 hold
for(int inc=count/3; inc>=1; inc/=2)
//当增量为 1时, 作最后一次插入操作
for(int inx=inc+1; inx<=count; inx++)
{ hold=rec[inx]; curr=inx-inc;
while(curr>=1 && hold<rec[curr])
{ rec[curr+inc]=rec[curr];
curr-=inc;
}
rec[curr+inc]=hold;
//将待插入元素插到合适的位置
}
}
}
关于增量的选择，有很多经验与看
法，这里不再叙述。希尔排序所用的时
间是一系列增量的函数，增量序列的不
同，会导致时间复杂度略微不一样。有
经验数据表明，希尔排序时间复杂度为
O(N5/4)。
8.3 选择排序
选择排序是指在排序过程中的
每一轮, 按照某种方法选择出当前未
排序部分中的最小值, 把它放在已排
序部分的首部, 随着排序过程的进行,
已排序部分变大, 未排序部分变小 。
直到比较 N-1轮之后, 所有元素都在
有序部分内, 排序过程结束 。
8.3.1 直接选择排序 (Straight
selection sort)
直接选择排序，又称简单选择排序
N个元素进行直接选择排序的过程如下：
在第一轮,从下标为 1的数组元素开始选出最
小的元素，把它与数组下标为 1的元素互换，这
时已排序部分长度为 1；
第二轮,从下标为 2的数组元素开始在剩余
的 N-1个元素中选出最小的元素，让它与数组下
标为 2的元素互换，这时已排序部分长度为 2；
……
从下标为 N-1的数组元素开始,
在剩下的两个元素中选出最小值，将
最小值放在下标为 N-1的数组元素中。
由于 N个元素中 N-1个元素都已经放到
了合适的位置，所以第 N个元素也已
经放到了合适的位置。
整个过程只需 N-1轮 。
//直接选择排序
//数组 rec为待排序的序列, count为排序元素的个数
void selectSortSimple(int rec[],int count)
{ int min,temp; //min存放当前轮的最小元素下标；
//temp是用于交换的临时变量
for(int inx=1; inx<count; inx++)
{ min=inx; //设该轮中未排序部分的首元为最小值
for(int curr=inx+1; curr<=count; curr++)
//找出该轮中未排序部分真正的最小值
if(rec[curr]<rec[min]) min=curr;
if(min!=inx)
//如果未排序部分的首元不是最小值, 做交换操作
{ temp=rec[inx]; rec[inx]=rec[min];
rec[min]=temp;
}
}
}
算法中：
每一轮一般都要在最后做交换操作。
一次交换涉及到 3个赋值语句，所以有
3(N-1)次赋值操作。而比较操作执行的
次数为 (N-1)+…+2+1，所以 时间复杂度
仍为 O(N2)。
算法中在作交换操作时借用了一个
辅助变量 temp，故 空间复杂度 为 O(1)。
8.3.2 堆排序 (Heap Sort)
最大堆 与 最小堆
如果 完全二叉树 各节点的关键字之间满
足以下的关系, 我们就称其为 最大堆 。
K≥ Kleft和 K≥ Kright
其中 K为某节点的关键字, Kleft为该
节点左子 （ 如果左子存在 ） 的关键字,
Kright为该节点右子 （ 如果右子存在 ） 的
关键字 。
类似的，可以得到 最小堆 的定义：
如果 完全二叉树 各节点的关键字之
间满足以下的关系，我们就称其为最小
堆。
K≤ Kleft和 K≤ Kright
其中 K为某节点的关键字,Kleft为
该节点左子（如果左子存在）的关键字
,Kright为该节点右子（如果右子存在
）的关键字。
由 最大堆 的定义能够知道,
一个二叉树如果是最大堆，那么其 根
的关键字 一定是该二叉树中所有节点关键
字中的 最大值 。
72
7112219
27 12
8
78
15 19
3
625
4 1
( a ) 最大堆 ( b ) 最小堆 ( c ) 该完全二叉树不是堆
如果用 一维数组 （数组下标为 0的空间不用，
从下标为 1的空间开始）来存储最大堆，那么
当前节点 的数组下标 R与其左子、右子 （假设
左子、右子存在）对应的数组下标 Rleft、
Rright之间的关系满足：
Rleft=2R,Rright=2R+1
17
11
161514
12 13 11 1715 16141312-
1 7654320
当把 一维数组 中各元素看成是一个
完全二叉树 中各节点时,
我们通过一定的方法，把数组 调整
成最大堆（堆的初始建立），这样最大
的元素就位于下标为 1的地方，之后让
其与下标为 N的元素互换，也就是让最
大元素放在了它该放的地方。
排序 第一轮 结束。
由于数组 1号下标的位置换进了新元
素，所以 原来的最大堆可能遭到了破坏，
我们再按照某种方法对其进行调整（ 堆的
调整 ），将数组前 N-1个元素再次构成一
个 最大堆,调整后下标为 1的位置中存储
的是 N-1个元素中的最大值，把它与数组
下标为 N-1的元素互换，这样整个序列的
次大元素也放到了该放的地方,
排序 第二轮 结束。
继续按照这种方法进行，直到 N-1轮
全部完成，所有数组元素就会变成有序
的序列。
显然这种思想仍旧属于选择排序的
方法。由于 排序过程中借助了堆,所以
称为 堆排序 。
该方法是 威洛姆斯 在 1964年提出的。
只要解决上面提到的两个问题：
堆的初始建立 与 堆的调整,
我们就可以完成排序。
先来看 第二个问题,在已有的最大堆上
让首元（根）与尾元（最后一个叶子）互换。
互换后,原来的尾元不再归入新一轮的研究
范围内。在新的研究范围内，由于互换使得
新首元不一定是最大值，所以要对其进行向
下的调整，使得新研究范围内所涉及到的节
点构成最大堆。
96
94238
83 27
( a ) 最大堆
9
964238
83 27
( b ) 准备调整
83
964238
9 27
( c ) 与其左子互换
83
96938
42 27
( d ) 与其右子互换
堆调整的算法
算法中尽量避免互换操作，而是在调整过
程中只让较大的元素上浮，同时记住下降位置
的下标，直到停止调整时，一次将待调整元素
赋值到相应位置。
//在考察范围内,low为待调整元素的下标 (考察范围的起始下
//标 ),high为考察范围的终止下标
void reHeap(int rec[],int low,int high)
{ int curr=rec[low];
//将待调整元素存入临时变量 curr中
int bigger=2*low; //先设定待调整元素左子为较大者
while(bigger<=high) //若仍在考虑范围内
{ if(bigger<high
&& rec[bigger]<rec[bigger+1])
//若右子存在, 且较左子大
while(bigger<=high) //若仍在考虑范围内
{ if(bigger<high
&& rec[bigger]<rec[bigger+1])
//若右子存在, 且较左子大
bigger++; //bigger为左子右子中较大者下标
if(curr>=rec[bigger]) break;
//带调整元素已经找到最后位置, 不用继续下降
else //上浮较大者,为下一次迭代作准备
{ rec[low]=rec[bigger];
low=bigger;
bigger=2*bigger;
}
}
rec[low]=curr; //将待调整元素存入到合适位置
}
接下来讨论前述的第一个问题,
如何把乱序的一维数组调成最大堆。
数组所有元素对应一棵完全二叉树。
二叉树中 叶子节点 不需要进行调整，所以
只考虑树中那些非叶子节点。
由于堆也是递归结构，当左子树与右子树
已经是堆时，再对根进行调整才是有效的，所
以我们调整的次序是从 最后一个非叶子节点 开
始处理，按照数组下标 从后往前 进行，直到最
后再处理根节点。
因为最后一个叶子节点的父节点就是最后
一个非叶子节点，所以讨论最后一个非叶子节
点的下标值。
N个元素的数组（ 0号下标空间不用），
最后一个节点下标为 N,如果 它是父节点的右
儿子（ N为奇数），则父节点下标为 (N-1)/2；
如果 它是父节点的左儿子（ N为偶数），则父
节点下标为 N/2。
注意, C++语言中整除运算只取商，故对
于 N个元素的完全二叉树来说，其最后一个非叶
子节点在数组中的下标对应的 C++语言表达式为,
（ N/2）
堆初始建立的算法
//建堆操作,数组 rec为待建堆的序列, count为元
素的个数
void buildHeap(int rec[],int count)
{ for(int inx=count/2; inx>=1; inx--)
reHeap(rec,low,count);
}
//堆排序
//数组 rec为待排序的序列, count为排序元素的个数
void selectSortHeap(int rec[],int count)
{ int temp; //用于变量互换,可以用 rec[0]代替
buildHeap(rec,count);
//堆的初始建立, 选出最大元
for(int round=count; round>1; round--)
//做 count-1轮
{ temp=rec[round];
rec[round]=rec[1];
rec[1]=temp; //本轮最大元放入正确位置
reHeap(rec,1,round-1); //在新范围内调整堆
}
}
在算法中可以看到，
时间主要耗费在 建堆 与 对堆的调整
上。
可以证得，堆在最坏的情况下，时
间复杂度为 O(N*log2N)，这已经是排
序的最好效率了。
空间复杂度仍为 O(1)。
8.4 交换排序
交换排序的基本方法是：
两两比较待排序元素, 并交换不满足
顺序要求的那些偶对, 直到全部满足为止 。
这里介绍两种交换排序, 一种是最简
单的冒泡排序 (Bubble Sort),另一种是
效率很高的快速排序 (Quick Sort)。
8.4.1 冒泡排序
8.4.2 分治法与快速排序
冒泡排序的过程很简单，首先将第 1个数
据的关键字和第 2个数据的关键字进行比较，
若为逆序（前大后小），则将两个记录交换之。
再比较第 2个和第 3个数据的关键字，依此类推，
直到第 N-1个数据和第 N个数据进行比较、交
换为止。如此经过一轮排序，使得关键字最大
的数据被安置到数组最后一个位置上。
然后，对前 N-1个数据进行同样的操作，
则具有次大关键字的数据被安置在数组中倒数
第二个位置上。
重复以上过程直至没有记录需要交换为止。
8.4.1 冒泡排序（起泡排序）
20
30
10
40
20
0
20
30
10
40
20
0
20
10
30
40
20
0
20
10
30
40
20
0
20
10
30
20
40
0
20
10
30
20
0
40
20
10
30
20
0
40
10
20
30
20
0
40
10
20
30
20
0
40
10
20
20
30
0
40
10
20
20
0
30
40
( a ) 第1 轮排序 ( b ) 第2 轮排序
10
20
20
0
30
40
10
20
20
0
30
40
10
20
0
20
30
40
10
20
0
20
30
40
10
20
0
20
30
40
10
20
0
20
30
40
10
0
20
20
30
40
10
0
20
20
30
40
0
10
20
20
30
40
( c ) 第3 轮排序 ( d ) 第4 轮排序 ( e ) 第5 轮排序
//冒泡排序
//数组 rec为待排序的序列, count为排序元素的个数
void exchangeSortBubble(int rec[],int count)
{ int temp;
//用于交换的临时变量,可以用 rec[0]代替
bool isChanged=true; //设为 true,进入循环
for(int round=1; isChanged && round<count;
round++)
{ isChanged=false; //假定本轮没有逆序的偶对
for(int inx=1; inx<=count-round; inx++)
if(rec[inx]<rec[inx+1]) //逆序的偶对
{ temp=rec[inx];
rec[inx]=rec[inx+1];
rec[inx+1]=temp;
isChanged=true; //本轮出现了逆序偶对
}
}
}
算法中，每一轮中相邻元素都要进
行比较，只要逆序就进行交换。
最坏情况下,每次比较完都要交换
数据，这时比较与交换的次数都是 (n-
1)+(n-2)+…+1，所以时间复杂度为
O(N2)。
8.4.2 分治法与快速排序
在完成一个比较复杂的任务时，如果不能
直接解决，我们总会将问题分解成若干小问题，
集中精力各个击破。如果每个小问题我们能够
顺利解决，那么整个大问题也随之解决了。
第三章中递归问题 的相关知识，我们可以
看到分治法的影子。
第五章中广义表 的处理以及 第六章树形结
构 中一些操作的实现（如遍历等），都用到了
类似的思想。
同样，在排序算法中，我们仍旧可以采用
分治法,快速排序 就是其中之一。
快速排序的思想是：
通过某种方法在待排序的数据序列中
选取一个数据，并以此数据为基准值，采
用一定的方法进行处理，从而将整个序列
分成三部分。
基准值处于序列中间的某个位置；该
位置之前，数据的关键字都小于该基准值；
该位置之后，数据的关键字都大于或等于
该基准值。这样就已经把基准值放到了正
确的位置上。
第一轮结束之后，按照分治的思想，
解决基准值之前以及基准值之后的两个
子序列，只要这两个子序列完成了排序
工作，整个序列的排序就全部结束了。
显然，两个子序列可以采用 递归 的
方式进行排序。
递归的终止条件：
一种情况 是子序列为空，这时不需
要排序； 另一种情况 是子序列只有一个
元素，也不需要排序。
其实，真正在对较多元素排序时，
前几轮会使用快速排序的方法，而当每
个子序列中元素个数较少时，就会转而
用一些简单的排序方法（如冒泡排序或
直接选择排序等等）
使用快速排序，基准值的选择比较关
键。 当基准值选得好时，其前后两个子序
列长度近似；但当基准值选得不好时，在
极端情况下，一个子序列为空，另一个子
序列是原来序列中除去基准值的所有元素，
这时 前后两个子序列极端不平衡，起不到
,折半, 的目的,效率自然不高。
但由于排序元素大小是随机分布的，
所以没有哪一种基准值的选取规则适于所
有序列，因此,我们只能在一定程度上采
取某些策略，但并不能够保证这些策略在
任何情况下都会起作用。
在下面的算法中，为了使所取的
基准值将来尽量放在数组里居中的位
置上，我们 先选出首元，尾元以及位
置处于数组中间的元素，对这三个数
据先排序，然后取出居中的元素 作为
基准值。
44 5794 82427655- 7686 84
44 5776 82427655- 9486 84
76 5744 82427655- 9486 84
基准值
76 5744 82427655- 9486 84
基准值
wall
curr
76 5744 82427655- 9486 84
基准值
wall
curr
76 5744 82427655- 9486 84
基准值
wall
curr
76 5744 82764255- 9486 84
基准值
wall
curr
76 5776 82444255- 9486 84
基准值
wall
curr
76 5776 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
76 7657 82444255- 9486 84
基准值
wall
curr
57 7676 82444255- 9486 84
wall基准值
可以看到，快速排序是 不稳定 的
排序。
//快速排序
//数组 rec为待排序的序列, count为排序元素个数
void exchangeSortQuick(int rec[],int
count)
{ quickSort(rec,1,count);
//调用递归函数, 完成快速排序
}
//递归函数, 完成快速排序
void quickSort(int rec[],int 1ow,int high) {
int pivot; //基准值的位置
if(low<high) {
pivot=partition(rec,low,high);
//将序列分成三部分
quickSort(rec,1,pivot-1);
//递归处理基准值之前的子序列
quickSort(rec,pivot,high);
//递归处理基准值之后的子序列
}
}
//将序列分成三部分,小于基准值的子序列,基准值本身,
大于基准值的子序列
//返回值为,排序后基准值在数组的最终位置
void partition(int rec[],int 1ow,int high)
{
int mid=(low+high)/2;
int temp;
//用于交换的临时变量,可用 rec[0]代替
//首元,位置居中的元素,尾元三个元素从小到大排序
if(rec[low]>rec[mid]) {
temp=rec[low];
rec[low]=rec[mid]; rec[mid]=temp;
}
if(rec[low]>rec[high]) {
temp=rec[low];
rec[low]=rec[high]; rec[high]=temp;
}
if(rec[mid]>rec[high]) {
temp=rec[mid];
rec[mid]=rec[high]; rec[high]=temp;
}
temp=rec[low];
rec[low]=rec[high];
rec[high]=temp; //基准值放在首元位置
int curr; //curr指向当前处理元素
int wall=1ow;
//wall指向已排序部分中小于基准值的最后元素,
//初始值为首元位置
for(curr=low+1; curr<=high; curr++)
if(rec[curr]<rec[low]) {
temp=rec[wall+1];
rec[wall+1]=rec[curr];
rec[curr]=temp; wall++;
}
temp=rec[low];
rec[low]=rec[wall]; rec[wall]=temp;
//将基准值放在最终位置上
return wall;
}
快速排序是目前各种内部排序方法
中速度最快的一种，可以证明其 平均时
间复杂度为 O(N*log2N)。
算法由于使用递归方法，所以其辅
助空间为使用递归时栈空间的最大深度。
最差情况下：每一轮过后基准值前后的
子序列都极端不平衡（一边为空），这
时栈的深度为 N，故 空间复杂度为 O(N)。
8.5 归并排序
快速排序采用了分治与递归的思想：
首先选出基准值，然后将序列分成三部
分，基准值居中，前面都是小于它的元
素，后面都是不小于它的元素，在将基
准值放到最终位置后，再分步解决前后
两个子序列的排序问题。这显然是从大
规模问题向小规模问题转换的思路。
如果换一种角度：在解决问题时，
从较小的规模向较大的规模转换，即，
先有两个已经排好序的子序列前后放
置，然后再集中精力将它们归并成一
个大的有序序列，用这种思路也同样
可以完成排序的任务。
显然，这种归并排序 (Merging
Sort)仍旧是分治与递归思想的应用。
八个元素不断归并的过程,
44 5794 82427655 86
44 5782 94784255 86
42 8657 82785544 94
42 8678 82575544 94
图中第一轮准备归并的初始状态
则是将原序列不断进行分解的结果,
由 8个元素一组分成 4个元素一组，
再分成 2个元素一组，直到分成每个
元素自己一组时，停止分解。
因为此时每组元素本身已经是有
序的。在此基础上，才开始进行归并。
归并过程的具体实现思想在例
2.2中已经介绍过，这里不再重复。
//归并排序 。 数组 rec为待排序的序列,
//count为排序元素的个数
void mergeSort(int rec[],int
count)
{ sortMerging(rec,1,count);
//调用递归函数完成归并排序,结
//果存在 temp数组中
}
//递归函数, 完成归并排序
void sortMerging(int rec[],
int 1ow,int high)
{ if(low<high)
{ int mid=(low+high)/2;
sortMerging(rec,low,mid);
sortMerging(rec,mid+1,high);
merge(rec,low,mid,high);
}
}
//实现两个有序序列的归并操作,
//归并后的序列仍然保持有序
//rec中第一个序列的下标是从 low到 mid,
//第二个序列的下标从 mid+1到 high
void merge(int rec[],int low,int
mid,int high) {
int curr1,curr2,curr;
//分别指向第一个序列, 第二个序列, 目
//标序列的当前元素
int *temp=new int[count+1];
//开辟临时数组,暂存数据 (0号下标不用 )
curr1=low; curr2=mid+1;
//指向两个序列的首元素, 准备开始比较
curr=low;
//为了方便,temp数组也只用一部分,从
//low到 high
//当两个序列都有元素时,经过比较选出小者
while(curr1<=mid && curr2<=high)
if(rec[curr1]<=rec[curr2]) {
temp[curr]=rec[curr1];
curr1++; curr++;
}else {
temp[curr]=rec[curr2];
curr2++; curr++;
}
//第二个序列先处理完后,处理第一个序列中
//剩余元素
while(curr1<=mid) {
temp[curr]=rec[curr1];
curr1++; curr++;
}
//第一个序列先处理完后,处理第二个序列中
//剩余元素
while(curr2<=high) {
temp[curr]=rec[curr2];
curr2++; curr++;
}
//将所有元素拷回到原数组
for(curr=low; curr<=high; curr++)
rec[curr]=temp[curr];
delete[] temp; //释放临时空间
}
归并排序是 稳定 的排序。
N个元素在排序过程中一共要做
log2N轮。每一轮进行合并时，所有元素
都要被比较，故其 时间复杂度为
O(N*log2N)。
使用的辅助空间一方面是在归并过程
中使用的 N个元素的暂存空间，另一方面
是递归操作引起的栈空间开销（最大深度
应为 log2N），所以 空间复杂度为 O(N)。
8.6 基数排序
基数排序 (Radix Sort)是我
们最后讨论的一种内部排序算法，
它与其他的内部排序算法思想有着
很大的不同。前面几节我们介绍的
各种排序方法都是 以关键字的比较
与数据的移动 为主，但基数排序却
主要 借助, 分配, 和, 收集, 两种
操作 来完成排序任务。
利用第三章所讲的队列来做暂
存数据的辅助空间 。
为了简化讨论, 我们假定待排
序的 N个关键字都在 0至 999之间 。
下面叙述排序过程 。
第一步：先初始化十个队列，每个队
列中都存放十进制整数。我们分别命名十
个队列为,0号队列,1号队列,2号队
列,…,9号队列。244 457894 82642176355- 17686 984
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
244 457
89482
642 176355
176
86
984
第二步：依次取出数据，按照
数据的个位数依次插入对应的队列。
如数据 231，其个位数为 1，所以将
它插入 1号队列。所有元素都被分
配到十个队列之后，完成第一次
,分配, 操作。
第三步,按照队列号的大小依次取出
队列中元素存入原数组。
也就是说，先依次取出 0号队列的所
有元素，并从原数组下标为 1处开始，一
个挨一个地存放数据；当 0号队列中的数
据全部被取出后，开始依次取出 1号队列
的所有元素继续放入数组；当 1号队列的
数据被全部取出后，开始依次取出 2号队
列的所有元素继续放入数组； …；直到 9
号队列的所有元素全部被取出并放入数组。
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
244 457
89482
642 176355
176
86
984
642 176984 35589424482- 45786 176
第一次, 收集, 操作结束 。到此为止，所有数据
已经按照末位数的大小，从小到大排好了顺序。
第四步，按照数据的十位数依次插入
对应的队列。
如数据 231，其十位数为 3，所以将
它插入 3号队列。
所有元素都被分配到十个队列之后，
完成第二次, 分配, 操作 。
注意，到此为止，同一个队列中所有
数据的十位数都是一样的，而且末位数是
按照从小到大的顺序存放的。因为在入队
时，个位数字小的元素先进入队列，这是
第三步操作的结果决定的。
642 176984 35589424482- 45786 176
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
642 176
984
355 894
244
82
457
86
176
第五步，按照队列号的大小依次
取出队列中元素存入原数组。操作方
法与第三步完全相同。
第二次, 收集, 操作结束 。到此
为止，所有数据已经按照末两位数的
大小，从小到大排好了顺序。
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
642 176
984
355 894
244
82
457
86
176
642 82176 176457355244- 894984 86
第六步，按照数据的百位数依次插入
对应的队列。
如数据 231，其百位数为 2，所以将
它插入 2号队列。所有元素都被分配到十
个队列之后,完成第三次, 分配, 操作 。
注意,到此为止，同一个队列中所有
数据的百位数都是一样的，而且末两位数
是按照从小到大的顺序存放的。因为在入
队时，末两位数字小的元素先进入队列，
这是第五步操作的结果决定的。
642 82176 176457355244- 894984 86
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
64282 176
176
457355244 894 984
86
第七步，按照队列号的大小依次
取出队列中元素存入原数组。操作方
法与第三步完全相同。 第三次, 收集,
操作结束。
到此为止，所有数据已经按照末
三位数的大小（数据本身值的大小），
从小到大排好了顺序。到此为止，排
序结束。
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9
82 457244 35517617686- 984642 894
64282 176
176
457355244 894 984
86
在上面的操作中，开辟的辅助空间就
是十个队列，由于它们最终要容纳下所有
的待排序数据，所以队列所占总空间数为
N。由此得到空间复杂度为 O(N)。
从描述过程看出，排序每一轮都要经
历依次, 分配, 操作和一次, 收集, 操作，
所以每一轮数据经过两次移动；而排序的
轮数是由最大数据关键字的长度 R决定的
（例子中最大数是三位数，故排序共做三
轮），由此知时间复杂度为 O(R*N)。
8.7 外部排序概述
对文件（第十章将专门介绍文件）进
行排序，是文件上十分重要的运算，在许
多地方都要用到。
通常情况下，由于文件很大，无法把
整个文件的所有记录同时调入内存中进行
排序，即：无法直接进行内部排序，从而
需要研究外存设备上（文件）的排序技术，
我们称这种排序为 外部排序 。
外部排序方法与各种外存设备的
特征有关。
外存设备大体上可分为顺序存取
（例如磁带）和直接序取（例如磁盘）
两大类，所以，外部排序通常又可分
为磁盘文件排序和磁带文件排序两大
类。
两类排序的基本步骤相类似，主
要不同之处在于初始归并段在外存储
介质中的分布方式。
一般来说，在外存设备上排序
的最通用方法是 归并排序法,这种
方法基本上由 两个相对独立的阶段
组成 。
首先,按可用内存大小，将外存上含 n个
记录的文件分成若干长度为 L的子文件（或
段），用某种有效的内部排序方法分别将这
些段读入内存进行排序，并将排序后得到的
有序子文件重新写入外存，通常称这些有序
子文件为, 归并段, 或, 顺串, ；
然后,把第一阶段所生成的顺串进行 逐
趟合并 （例如通过若干趟 2路合并），使顺串
（有序的子文件）逐渐由小变大，直至最终
变为一个顺串为止，这时整个文件已经成为
,有序文件, 。
由于在排序过程中，需要读写外部存储设
备当中的文件，而这样的操作显然比较费时，
所以提高外部排序的效率应主要着眼于 减少外
存信息的读 /写次数,而 不是 我们在内部排序中
关注的两个操作：关键字进行的比较次数和数
据互换移动的次数。
针对这样的情况，可以从不同角度减少读
写外存的次数：为了减少归并次数，使用 多路
平衡归并 （可以借助于, 败者树, 完成）；为
了尽量得到较长的, 归并段,,采用 置换选择
排序 的方法，并进一步对所得长度不等的归并
段构造 最佳归并树 等等。
8.8 本章小结
基本内容：
内部排序：
插入排序
选择排序
交换排序
归并排序
基数排序
在内部排序中我们主要关注两类
操作：关键字的比较次数与数据元素
位置的移动与互换次数 。
对于外部排序, 主要使用归并的思
想, 另外考虑到读取外存的时间较计
算与内存访问时间来说非常耗时, 所
以在外部排序中尽量要注意减少外存
读取的次数 。
在各种排序算法中，时间效率较高
的有希尔排序、堆排序和快速排序三种。
基数排序由于采用的是分配收集的
操作，所以它与其他内部排序的算法在
思路上有着较大的差别。
在介绍快速排序与归并排序时，我
们又使用了, 分治法, 的思想，将复杂
的问题化大为小，以便各个击破，分而
治之。
?基本要求：
深刻理解排序的 定义 和各种排序方
法的 特点, 并能加以灵活运用 。
基于, 关键字间的比较, 进行排序
的方法可以按排序过程所依据的不同原
则分为 插入排序, 交换排序, 选择排序,
归并排序 和 基数排序 五类 。 了解各种方
法的排序过程及其依据的原则 。
理解排序方法, 稳定, 和, 不稳定,
的含义, 弄清楚在什么情况下要求应用
的排序方法必须是稳定的 。
掌握各种排序方法的时间复杂度的
分析方法 。 能从, 关键字间的比较次数,
分析排序算法的平均情况和最坏情况的
时间性能 。 按平均时间复杂度划分, 内
部排序可分为三类,O(N2)的 简单排序 方
法, O(N*logN) 的 高 效 排 序 方 法 和
O(R*N )的 基数排序 方法 。
希尔排序, 快速排序, 堆排序
和归并排序等高效方法是本章的学
习重点和难点 。
了解外部排序的两个阶段, 及
外部排序的基本思想 。
进一步掌握, 分治法, 的思想 。
