第 9章 排序
数据结构（ C++描述）
目录
9,1 基本概念
9,2 插入排序
9,3 交换排序
9,4 选择排序
9,5 归并排序
*9,6 分配排序
退出
9,1 基本概念
9.1.1 排序介绍
排序 （ Sorting） 是数据处理中一种很重要的运算,
同时也是很常用的运算, 一般数据处理工作 25%的
时间都在进行排序 。 简单地说, 排序就是把一组记
录 （ 元素 ） 按照某个域的值的递增 （ 即由小到大 ）
或递减 （ 即由大到小 ） 的次序重新排列的过程 。
表 9-1 学生档案表
学号 姓名 年龄 性别
99001 王晓佳 18 男
99002 林一鹏 19 男
99003 谢宁 17 女
99004 张丽娟 18 女
99005 周涛 20 男
99006 李小燕 16 女
例如, 在表 9-1中, 若以每个记录的学号为关键字, 按
排序码年龄的递增 （ 由小到大 ） 排序, 则所有记录的排
序结果可简记为：
{（ 99006,16）, （ 99003,17）, （ 99001,18）,
（ 99004,18）, （ 99002,19）, （ 99005,20） }；
也可能为：
{（ 99006,16）, （ 99003,17）, （ 99004,18）,
（ 99001,18）, （ 99002,19）, （ 99005,20） }；
这两个结果都是表 9-1按年龄的递增排序结果 。 若按排序
码姓名来进行递增排序, 则得到的排序结果为：
{（ 99006,李小燕 ）, （ 99002,林一鹏 ）, （ 99001，
王晓佳 ）, （ 99003,谢宁 ）, （ 99004,张丽娟 ）,
（ 99005,周涛 ） }
当然, 我们还可以按排序码性别来进行递增排序, 在此
不再作进一步的分析 。
9.1.2 基本概念
1．排序码（ Sort Key）
作为排序依据的记录中的一个属性。它可以是任何一种
可比的有序数据类型，它可以是记录的关键字，也可以
是任何非关键字。如上例中的学生年龄。在此我们认为
对任何一种记录都可找到一个取得它排序码的函数
Skey(一个或个关键字的组合 )。
2,有序表与无序表
一组记录按排序码的递增或递减次序排列得到的结果被
称之为有序表, 相应地, 把排序前的状态称为无序表 。
3,正序表与逆序表
若有序表是按排序码升序排列的, 则称为升序表或正序
表, 否则称为降序表或逆序表 。 不失普遍性, 我们一般
只讨论正序表 。
4,排序定义
若给定一组记录序列 r1, r2, …, rn,其排序码分别
为 s1,s2, …, sn, 将这些记录排成顺序为 rk1,
rk2, …, rkn的一个序列 R’,满足条件 sk1≤sk2≤ … ≤skn，
获得这些记录排成顺序为 rp1, rp2, …, rpn的一个序
列 R”,满足条件 sp1≤sp2≤ … ≤spn的过程称为排序 。
也可以说，将一组记录按某排序码递增或递减排列的
过程，称为排序。
5,稳定与不稳定
因为排序码可以不是记录的关键字，同一排序码值可能对应
多个记录。对于具有同一排序码的多个记录来说，若采用的
排序方法使排序后记录的相对次序不变，则称此排序方法是
稳定的，否则称为不稳定的。在上例中（见表 9-1，按年龄排
序），如果一种排序方法使排序后的结果必为前一个结果，
则称此方法是稳定的；若一种排序方法使排序后的结果可能
为后一个结果，则称此方法是不稳定的。
6,内排序与外排序
按照排序过程中使用内外存的不同将排序方法分为内排序
和外排序 。 若排序过程全部在内存中进行, 则称为内排序；
若排序过程需要不断地进行内存和外存之间的数据交换,
则称为外排序 。 内排序大致可分为五类：插入排序, 交换
排序, 选择排序, 归并排序和分配排序 。 本章仅讨论内排
序 。
7,排序的时间复杂性
排序过程主要是对记录的排序码进行比较和记录的移动过
程 。 因此排序的时间复杂性可以算法执行中的数据比较次
数及数据移动次数来衡量 。 当一种排序方法使排序过程在
最坏或平均情况下所进行的比较和移动次数越少, 则认为
该方法的时间复杂性就越好, 分析一种排序方法, 不仅要
分析它的时间复杂性, 而且要分析它的空间复杂性, 稳定
性和简单性等 。
为了以后讨论方便，我们直接将排序码写成一个一维数
组的形式，具体类型设为 Elemtype，并且在没有声明的情
形下，所有排序都按排序码的值递增排列。
排序
插入排序（直插排序、二分排序、希尔排序）
交换排序（冒泡排序、快速排序）
选择排序 （直选排序、树型排序、堆排序）
归并排序（二路归并排序、多路归并排序）
分配排序 （多关键字排序、基数排序）
9,2 插入排序
9.2.1直接插入排序
1．直接插入排序的基本思想
直接插入排序 （ Straight Insertion Sorting） 的基本思想是：把
n个待排序的元素看成为一个有序表和一个无序表, 开始时
有序表中只包含一个元素, 无序表中包含有 n-1个元素, 排序
过程中每次从无序表中取出第一个元素, 把它的排序码依次
与有序表元素的排序码进行比较, 将它插入到有序表中的适
当位置, 使之成为新的有序表 。
2．直接插入的算法实现
void insertsort(ElemType R[],int n)
//待排序元素用一个数组 R表示, 数组有 n个元素
{ for ( int i=1; i<n; i++) //i表示插入次数, 共进行 n-1次
插入
{ ElemType temp=R[i]; //把待排序元素赋给 temp
int j=i-1;
while ((j>=0)&& (temp<R[j]))
{ R[j+1]=R[j]; j--; } // 顺序比较和移动
R[j+1]=temp;}
}
例如, n=6,数组 R的六个排序码分别为,17,3,25，
14,20,9。 它的直接插入排序的执行过程如图 9-1所
示 。
R[0 ] R[1 ] R[2 ] R[3 ] R[4 ] R[5 ]
初始状态 (1 7 ) 3 25 14 20 9
第一次插入 (3 17 ) 25 14 20 9
第二次插入 (3 17 25 ) 14 20 9
第三次插入 (3 14 17 25 ) 20 9
第四次插入 (3 14 17 20 25 ) 9
第五次插入 (3 9 14 17 20 25 )
图 9 - 1 直接插入排序示例
3,直接插入排序的效率分析从上面的叙述可以看出, 直接插入排序算法十分简单 。
那么它的效率如何呢？ 首先从空间来看, 它只需要一个
元素的辅助空间, 用于元素的位置交换 。 从时间分析,
首先外层循环要进行 n-1次插入, 每次插入最少比较一次
（ 正序 ）, 移动两次；最多比较 i次, 移动 i＋ 2次 （ 逆序 ）
（ i=1,2,…, n-1） 。 若分别用 Cmin, Cmax 和 Cave表示
元素的总比较次数的最小值, 最大值和平均值, 用 Mmin,
Mmax 和 Mave表示元素的总移动次数的最小值, 最大值和
平均值, 则上述直接插入算法对应的这些量为：
Cmin=n-1 M min=2（ n-1）
Cmax=1+2+… +n-1=（ n2-n） /2 M max=3+4+… +n+1=
（ n2+3n-4） /2
Cave=（ n2+n-2） /4 M max=（ n2+7n-8） /4
因此, 直接插入排序的时间复杂度为 O（ n2） 。
直接插入算法的元素移动是顺序的, 该方法是稳定的 。
9.2.2二分插入排序
1,二分插入排序的基本思想
二分插入排序 （ Binary Insert Sort） 的基本思想是：
在有序表中采用二分查找的方法查找待排元素的插
入位置 。
其处理过程：先将第一个元素作为有序序列, 进行 n-
1次插入, 用二分查找的方法查找待排元素的插入位
置, 将待排元素插入 。
3,二分插入排序的效率分析
二分插入算法与直接插入算法相比, 需要辅助空间与直接
插入排序基本一致；时间上, 前者的比较次数比直接插入
查找的最坏情况好, 最好的情况坏, 两种方法的元素的移
动次数相同, 因此二分插入排序的时间复杂度仍为 O
（ n2） 。
二分插入算法与直接插入算法的元素移动一样是顺序的,
因此该方法也是稳定的 。
2,二分插入排序的算法实现
其算法如下：
void BinaryInsertSort(ElemType R[],int n)
{ for(int i=1; i<n; i++) //共进行 n-1次插入
{ int left=0,right=i-1;ElemType temp=R[i];
while(left<=right)
{ int middle=(left+right)/2; //取中点
if(temp<R[middle]) right=middle-1; //取左区间
else left=middle+1; } //取右区间
for(int j=i-1;j>=left;j--)
R[j+1]=R[j]; //元素后移空出插入位
R[left]=temp; }}
9.2.3希尔排序
1,希尔排序的基本思想
希尔排序 （ Shell Sort） 又称为, 缩小增量排序, 。 是
1959年由 D.L.Shell提出来的 。 该方法的基本思想是：先
将整个待排元素序列分割成若干个子序列 （ 由相隔某个
,增量, 的元素组成的 ） 分别进行直接插入排序, 待整
个序列中的元素基本有序 （ 增量足够小 ） 时, 再对全体
元素进行一次直接插入排序 。 因为直接插入排序在元素
基本有序的情况下 （ 接近最好情况 ）, 效率是很高的,
因此希尔排序在时间效率上比前两种方法有较大提高 。
3,希尔排序的效率分析
虽然我们给出的算法是三层循环, 最外层循环为 log2n数
量级, 中间的 for循环是 n数量级的, 内循环远远低于 n数
量级, 因为当分组较多时, 组内元素较少；此循环次数
少；当分组较少时, 组内元素增多, 但已接近有序, 循
环次数并不增加 。 因此, 希尔排序的时间复杂性在 O
（ nlog2n） 和 O（ n2 ） 之间, 大致为 O（ n1,3） 。
例如, n=8,数组 R的八个元素分别为,17,3,30，
25,14,17,20,9。 下面用图 9-2给出希尔排序算法
的执行过程 。
17 3 30 25 14 17 20 9 初始状态,I =4
14 3 17 9 20 17 30 25 第二趟结果,I =1
3 9 14 17 17 20 25 30 第三趟结果
14 3 20 9 17 17 30 25 第一趟结果,I =2
图 9 - 2 希尔排序算法的执行过程
由于希尔排序对每个子序列单独比较, 在比较时进行元
素移动, 有可能改变相同排序码元素的原始顺序, 因此
希尔排序是不稳定的 。 例如, 给定排序码 3,4,2,2，
则希尔排序的结果变成 2,2,3,4 。
9,3 交换排序
9.3.1 冒泡排序
1．冒泡排序的基本思想
冒泡排序 （ Bubble Sorting） 的基本思想是：是通过对
待排序序列从后向前 （ 从下标较大的元素开始 ）, 依
次比较相邻元素的排序码, 若发现逆序则交换, 使排
序码较小的元素逐渐从后部移向前部 （ 从下标较大的
单元移向下标较小的单元 ）, 就象水底下的气泡一样
逐渐向上冒 。
因为排序的过程中, 各元素不断接近自己的位置, 如
果一趟比较下来没有进行过交换, 就说明序列有序,
因此要在排序过程中设置一个标志 flag判断元素是否进
行过交换 。 从而减少不必要的比较 。
2,冒泡排序的算法实现
下面给出冒泡排序算法 。
void Bubblesort(ElemType R[],int n)
{ int flag=1; //当 flag为 0则停止排序
for (int i=1; i<n; i++)
{ //i表示趟数, 最多 n-1趟
flag=0;//开始时元素未交换
for (int j=n-1; j>=i; j--)
if (R[j]<R[j-1]) { //发生逆序 ElemType t=R[j];
R[j]=R[j-1];
R[j-1]=t;flag=1; } //交换, 并标记发生了交换
if(flag==0)return; }}
例如, n=6,数组 R的六个排序码分别为,17,3,25,14，
20,9。 下面用图 9-3给出冒泡排序算法的执行过程 。
图 9 - 3 冒泡排序示例
R[0] R[1] R[2] R[3] R[4] R[5]
第一趟排序 3 (17 9 2 5 1 4 2 0 )
第二趟排序 3 9 (17 1 4 2 5 2 0 )
第三趟排序 3 9 1 4 (17 2 0 2 5 )
第 四趟排序 3 9 1 4 1 7 2 0 2 5
初始状态 （ 17 3 25 14 2 0 9 )
3,冒泡排序的效率分析
从上面的例子可以看出, 当进行完第三趟排序时, 数
组已经有序, 所以第四趟排序的交换标志为 0,即没进
行交换, 所以不必进行第四趟排序 。
从冒泡排序的算法可以看出, 若待排序的元素为正序,
则只需进行一趟排序, 比较次数为 （ n-1） 次, 移动元
素次数为 0；若待排序的元素为逆序, 则需进行 n-1趟
排序, 比较次数为 (n2-n)/2,移动次数为 3(n2-n )/2,因
此冒泡排序算法的时间复杂度为 O（ n2） 。 由于其中的
元素移动较多, 所以属于内排序中速度较慢的一种 。
因为冒泡排序算法只进行元素间的顺序移动, 所以是
一个稳定的算法 。
9.3.2 快速排序
1,快速排序的基本思想
快速排序（ Quick Sorting）是迄今为止所有内排序算
法中速度最快的一种。它的基本思想是：任取待排序
序列中的某个元素作为基准（一般取第一个元素），
通过一趟排序，将待排元素分为左右两个子序列，左
子序列元素的排序码均小于或等于基准元素的排序码，
右子序列的排序码则大于基准元素的排序码，然后分
别对两个子序列继续进行排序，直至整个序列有序。
快速排序是对冒泡排序的一种改进方法，算法中元素
的比较和交换是从两端向中间进行的，排序码较大的
元素一次就能够交换到后面单元，排序码较小的记录
一次就能够交换到前面单元，记录每次移动的距离较
远，因而总的比较和移动次数较少。
快速排序的过程为：把待排序区间按照第一个元素
（ 即基准元素 ） 的排序码分为左右两个子序列的过程
叫做一次划分 。 设待排序序列为 R[left]～ R[right],其
中 left为下限, right为上限, left＜ right,R[left]为该序
列的基准元素, 为了实现一次划分, 令 i,j的初值分别
为 left和 right。 在划分过程中, 首先让 j从它的初值开
始, 依次向前取值, 并将每一元素 R[j]的排序码同
R[left]的排序码进行比较, 直到 R[j]<R[left]时, 交换
R[j]与 R[left]的值, 使排序码相对较小的元素交换到左
子序列, 然后让 i从 i＋ 1开始, 依次向后取值, 并使每
一元素 R[i]的排序码同 R[j]的排序码 （ 此时 R[j]为基准
元素 ） 进行比较, 直到 R[i]＞ R[j]时, 交换 R[i]与 R[j]
的值, 使排序码大的元素交换到后面子区间；再接着
让 j从 j-1开始, 依次向前取值, 重复上述过程, 直到 i
等于 j,即指向同一位置为止, 此位置就是基准元素最
终被存放的位置 。 此次划分得到的前后两个待排序的
子序列分别为 R[left]～ R[i-1]和 R[i+1]～ R[right]。
例如, 给定排序码为,（ 46,55,13,42,94,05,17，
70）, 具体划分如图 9-4所示 。
[ 46 55 13 42 94 05 17 70 ]
i
j
[ 46 55 13 42 94 05 17 70 ]
i
j
[ 17 55 13 42 94 05 46 70 ]
i
j
[ 17 46 13 42 94 05 55 70 ]
i
j
[ 17 05 13 42 94 46 55 70 ]
i
j
[ 17 05 13 42 94 46 55 70 ]
i j
[ 17 05 13 42 94 46 55 70 ]
i
j
[ 17 05 13 42 94 ] 46 [ 55 70 ]
i j
图 9 - 4 快速排序的一次划分
从图 9-4可知, 通过一次划分, 将一个区间以基准值分成
两个子区间, 左子区间的值小于等于基准值, 右子区间
的值大于基准值 。 对剩下的子区间重复此划分步骤, 则
可以得到快速排序的结果 。
2,快速排序的算法实现
下面给出快速排序算法的递归算法如下：
void quicksort(ElemType R[],int left,int right)
{ int i=left,j=right; ElemType temp=R[i];
while (i<j)
{ while ((R[j]>temp)&&(j>i)) j=j-1;
if (j>i) { R[i]=R[j]; i=i+1; }
while ((R[i]<=temp)&&(j>i)) i=i+1;
if (i<j) { R[j]=R[i]; j=j-1; } }
//一次划分得到基准值的正确位置
R[i]=temp;
if (left<i-1) quicksort(R,left,i-1); //递归调用左子区间
if (i+1<right) quicksort(R,i+1,right); }//递归调用右子区间
3,快速排序的效率分析
若快速排序出现最好的情形 （ 左, 右子区间的长度大致
相等 ）, 则结点数 n 与二叉树深度 h 应满足
log2n<h<log2n+1, 所以总的比较次数不会超过 (n+1)
log2n。 因此, 快速排序的最好时间复杂度应为 O
（ nlog2n） 。 而且在理论上已经证明, 快速排序的平均
时间复杂度也为 O（ nlog2n） 。
若快速排序出现最坏的情形 （ 每次能划分成两个子区间,
但其中一个是空 ）, 则这时得到的二叉树是一棵单分枝
树, 得到的非空子区间包含有 n-i个 (i代表二叉树的层数
（ 1≤i≤n） 元素, 每层划分需要比较 n-i+2次, 所以总的
比较次数为 （ n2+3n-4） /2。 因此, 快速排序的最坏时间
复杂度为 O(n2)。
快速排序所占用的辅助空间为栈的深度, 故最好的空间
复杂度为 O（ log2n）, 最坏的空间复杂度为 O(n)。
快速排序是一种不稳定的排序方法。
9,4 选择排序
9.4.1 直接选择排序
1,直接选择排序的基本思想
直接选择排序 （ straight select sorting） 也是一种简单的
排序方法 。 它的基本思想是：第一次从 R[0]~R[n-1]中选
取最小值, 与 R[0]交换, 第二次从 R[1]~R[n-1]中选取最
小值, 与 R[1]交换, 第三次从 R[2]~R[n-1]中选取最小值,
与 R[2]交换, …, 第 i次从 R[i-1]~R[n-1]中选取最小值,
与 R[i-1]交换, …,第 n-1次从 R[n-2]~R[n-1]中选取最小值,
与 R[n-2]交换, 总共通过 n-1次, 得到一个按排序码从小
到大排列的有序序列 。
例如, 给定 n=8,数组 R中的 8个元素的排序码为,（ 8，
3,2,1,7,4,6,5）, 则直接选择排序过程如图 9-5
所示 。
初始状态 [ 8 3 2 1 7 4 6 5 ]
第一次 [ 1 3 2 8 7 4 6 5 ]
第二次 [ 1 2 3 8 7 4 6 5 ]
第三次 [ 1 2 3 8 7 4 6 5 ]
第四次 [ 1 2 3 4 7 8 6 5 ]
第五次 [ 1 2 3 4 5 8 6 7 ]
第六次 [ 1 2 3 4 5 6 8 7 ]
第七次 [ 1 2 3 4 5 6 7 8 ]
图 9 - 5 直接选择排序的过程示例
3,直接选择排序的效率分析
在直接选择排序中, 共需要进行 n-1次选择和交换, 每次
选择需要进行 n-i次比较 （ 1≤i≤n-1）, 而每次交换最
多需 3次移动, 因此, 总的比较次数 C= =(n2-n)/2，
总的移动次数 M= =3(n-1)。 由此可知, 直接选择
排序的时间复杂度为 O(n2)数量级, 所以当记录占用的字
节数较多时, 通常比直接插入排序的执行速度要快一些 。
由于在直接选择排序中存在着不相邻元素之间的互换,
因此, 直接选择排序是一种不稳定的排序方法 。 例如,
给定排序码为 3,7,3,2,1,排序后的结果为 1,2,3，
3,7。
??
?
?1
1
)(n
i
in
??
?
1
1
3
n
i
9.4.2 树形选择排序
从直接选择排序可知, 在 n个排序码中, 找出最小值需 n-
1次比较, 找出第二小值需 n-2次比较, 找出第三小值需
n-3次比较, 其余依此类推 。 所以, 总的比较次数为：
(n-1)+(n-2)+… +3+2+1= (n2-n)/2,那么, 能否对直接选择
排序算法加以改进, 使总的比较次数比 (n2-n)/2小呢？ 显
然, 在 n个排序码中选出最小值, 至少进行 n-1次比较,
但是, 继续在剩下的 n-1个关键字中选第二小的值, 就并
非一定要进行 n-2次比较, 若能利用前面 n-1次比较所得
信息, 则可以减少以后各趟选择排序中所用的比较次数,
比如 8个运动员中决出前三名, 不需要 7+6+5=18场比赛
（ 前提是, 若甲胜乙, 而乙胜丙, 则认为甲胜丙 ）, 最
多需要 11场比赛即可 （ 通过 7场比赛产生冠军后, 第二
名只能在输给冠军的三个对中产生, 需 2场比赛, 而第
三名只能在输给亚军的三个对中产生, 也需 2场比赛,
总共 11场比赛 ） 。 具体见图 9-6所示 。
A
A E
A
A
C
C D B F
B
B
G H
G
(a) 8 个队决出冠军的情形（共 7 场比赛）
B
* E
E
C
C
C D B F
B
B
G H
G
(b ) 决出亚军的情形（共 2 场比赛，少于 6 场）
C
* E
E
C
C
C D * F
F
F
G H
G
(c) 决出第三名的情形（共 2 场比赛，少于 6 场）
图 9 - 6 决出比赛前三名的过程示意图
从图 9-6（ a）可知,8个队经过 4场比赛，获胜的 4个队
进入半决赛，再经过 2场半决赛和 1场决赛即可知道冠军
属谁（共 7场比赛）按照锦标赛的传递关糸，亚军只能
产生于分别在决赛，半决赛和第一轮比赛中输给冠军的
选取手中，于是亚军只能在 b,c,e这 3个队中产生（见
图 9-6（ b）），即进行 2场比赛（ e 与 c一场,e与 c的胜
队与 b一场）后，即可知道亚军属谁。同理，第三名只
需在 c,f,g这 3个队产生（见图 9-6（ c））即进 2场比赛
（ f与 g一场,f与 g的胜队与 c一场）即可知道第三名属谁。
树形选择排序 （ tree selection sorting）, 又称锦标赛排序
（ tournament sorting）, 是一种按照锦标赛的思想进行
选择排序的方法 。 首先对 n个记录的排序码进行两两比
较, 然后在其中 ?n/2? 个较小者之间再进行两两比较, 如
此重复, 直到选出最小排序码为止 。
例如，给定排序码头 50,37,66,98,75,12,26,49，
树形选择排序过程见图 9-7。
6 6
12
50
37
3 7
12 26
12
37 6 6 98 75 12 26 49
(a ) 经过 7 次比较得到最小值 12
6 6
26
50
37
3 7
75 26
26
37 6 6 98 75 ∞ 26 49
(b) 输出 12 后，经过 2 次比较得到第二小值 26
6 6
49
50
37
3 7
75 49
37
37 6 6 98 75 ∞ ∞ 49
(c) 输出 12, 26 后，经过 2 次比较得到第三小值 37
6 6
49
50
50
50
75 49
49
∞ 6 6 98 75 ∞ ∞ 49
（ d ）输出 12,2 6,3 7 后，经过 2 次比较得到第四小值 49
6 6
75
50
50
50
75 ∞
50
∞ 6 6 98 75 ∞ ∞ ∞
(e) 输出 12,26,37,49 后，经过 1 次比较得到第五小值 50
6 6
75
∞
∞
66
75 ∞
66
∞ 6 6 98 75 ∞ ∞ ∞
(f) 输出 12,26,37,49,50 后，经过 1 次比较得到第六小值 66
98
75
∞
∞
98
75 ∞
75
∞ ∞ 98 75 ∞ ∞ ∞
( g ) 输出 12,2 6,3 7,4 9,5 0,6 6 后，经过 1 次比较得到第七小值 75
98
∞
∞
∞
98
∞ ∞
98
∞ ∞ 98 ∞ ∞ ∞ ∞
( h ) 输出 12,2 6,3 7,4 9,5 0,6 6,7 5 后，经过 1 次比较得到第八小值 98
图 9 - 7 树形选择排序示意过程
9.4.3 堆排序
1,堆的定义
若有 n个元素的排序码 k1,k2,k3,…, kn,当满足如下
条件：
ki≤k2i ki≥k2i
（ 1） ki≤k2i+1 或 (2) ki≥k2i+1 其中
i=1,2,…,?n/2?
则称此 n个元素的排序码 k1,k2,k3,…, kn为一个堆 。
若将此排序码按顺序组成一棵完全二叉树, 则 （ 1） 称为
小根堆 （ 二叉树的所有根结点值小于或等于左右孩子的
值 ）, （ 2） 称为大根堆 （ 二叉树的所有根结点值大于或
等于左右孩子的值 ） 。
若 n个元素的排序码 k1,k2,k3,…, kn满足堆, 且让结
点按 1,2,3,…, n顺序编号, 根据完全二叉树的性质
（ 若 i为根结点, 则左孩子为 2i,右孩子为 2i+1） 可知,
堆排序实际与一棵完全二叉树有关 。 若将排序码初始序
列组成一棵完全二叉树, 则堆排序可以包含建立初始堆
（ 使排序码变成能符合堆的定义的完全二叉树 ） 和利用
堆进行排序两个阶段 。
2,堆排序的基本思想
将排序码 k1,k2,k3,…, kn表示成一棵完全二叉树，
然后从第 ?n/2? 个排序码开始筛选，使由该结点作根结
点组成的子二叉树符合堆的定义，然后从第 ?n/2? -1个排
序码重复刚才操作，直到第一个排序码止。这时候，该
二叉树符合堆的定义，初始堆已经建立。
接着, 可以按如下方法进行堆排序：将堆中第一个结点
（ 二叉树根结点 ） 和最后一个结点的数据进行交换 （ k1与
kn）, 再将 k1~kn-1重新建堆, 然后 k1和 kn-1交换, 再将
k1~kn-2重新建堆, 然后 k1和 kn-2交换, 如此重复下去, 每次
重新建堆的元素个数不断减 1,直到重新建堆的元素个数
仅剩一个为止 。 这时堆排序已经完成, 则排序码 k1,k2，
k3,…, kn已排成一个有序序列 。
若排序是从小到大排列, 则可以用建立大根堆实现堆排
序, 若排序是从大到小排列, 则可以用建立小根堆实现
堆排序 。
例如, 给定排序码 46,55,13,42,94,05,17,70，
建立初始堆的过程如图 9-8所示 。
4 6
5 5
42 94
7 0
1 3
05 17
4 6
5 5
70 94
42
1 3
05 17
4 6
5 5
7 0 94
42
17
05 13
4 6
94
70 55
42
17
05 13
94
7 0
4 6 55
42
17
05 13
图 9 - 8 建立初始大根堆的过程示意图
（ e ）成堆
（ c ）将以 5 5 为根的子 树调整成堆
（ d ）将以 4 6 为根的子树调整成堆
（ a ）初始无序的结点，从 42 开始调整
（ b ）将以 13 为根的子树调整成堆
对排序码 46,55,13,42,94,05,17,70,建成如图 9-
8(e)所示的大根堆后, 堆排序过程如图 9-9所示 。 94
7 0
4 6 55
42
17
05 13
42
7 0
4 6 55
94
17
05 13
( a) 初始堆 ( b ) 94 与 42 交换
70
55
4 6 42
94
17
05 13
13
55
4 6 42
94
17
05 70
(c) 前 7 个排序码重新建成堆 (d) 70 和 13 交换
55
46
13 42
94
17
05 70
05
46
13 42
94
17
55 70
(e) 前 6 个排序码重新建成堆 (f) 55 和 05 交换 46
42
13 05
94
17
55 70
05
42
13 46
94
17
55 70
( g ) 前 5 个排序码重新建成堆 (h) 46 和 05 交换
42
13
05 46
94
17
55 70
05
13
42 46
94
17
55 70
(i) 前 4 个排序码重新建成堆 (j) 42 和 05 交换
17
13
42 46
94
05
55 70
05
13
42 46
94
17
55 70
( k) 前 3 个排序码重新建成堆 ( l) 1 7 和 05 交换
13
05
42 46
94
17
55 70
05
13
42 46
94
17
55 70
(m ) 前 2 个排序码重新建成堆 ( n ) 13 和 05 交换
图 9 - 9 堆排序过程示意图
从图 9-9（ n） 可知, 将其结果按完全二叉树形式输出,
则得到结果为,05,13,17,42,46,55,70,94,即
为堆排序的结果 。
4,堆排序的效率分析
在整个堆排序中, 共需要进行 n+?n/2? -1次筛选运算, 每次
筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动
次数都不会超过完全二叉树的深度, 所以, 每次筛选运算的
时间复杂度为 O(log2n),故整个堆排序过程的时间复杂度为
O(nlog2n)。
堆排序占用的辅助空间为 1（ 供交换元素用 ）, 故它
的空间复杂度为 O（ 1） 。
堆排序是一种不稳定的排序方法, 例如, 给定排序码：
2,1,2,它的排序结果为,1,2,2。
9,5 归并排序
9.5.1 二路归并排序
二路归并排序的基本思想
二路归并排序的基本思想是：将两个有序子区间 （ 有序表 ）
合并成一个有序子区间, 一次合并完成后, 有序子区间的
数目减少一半, 而区间的长度增加一倍, 当区间长度从 1
增加到 n（ 元素个数 ） 时, 整个区间变为一个, 则该区间
中的有序序列即为我们所需的排序结果 。
例如, 给定排序码 46,55,13,42,94,05,17,70,二
路归并排序过程如图 9-10所示 。
三趟归并,[0 5 13 17 42 46 55 70 94 ]
二趟归并,[1 3 42 46 55] [0 5 17 70 94 ]
一趟归并,[4 6 55] [1 3 42 ] [0 5 94] [1 7 70]
初始状态,[4 6] [5 5] [1 3] [4 2] [9 4] [0 5] [1 7] [7 0]
图 9 - 10 二路归并排序过程示意图
3,二路归并排序的效率分析
二路归并排序的时间复杂度等于归并趟数与每一趟时间复
杂度的乘积 。 而归并趟数为 ?log2n? (当 ?log2n? 为奇数时, 则
为 ?log2n? +1)。 因为每一趟归并就是将两两有序子区间合并
成一个有序子区间, 而每一对有序子区间归并时, 记录的
比较次数均小于等于记录的移动次数 （ 即由一个数组复制
到另一个数组中的记录个数 ）, 而记录的移动次数等于这
一对有序表的长度之和, 所以, 每一趟归并的移动次数均
等于数组中记录的个数 n,即每一趟归并的时间复杂度为
O(n)。 因此, 二路归并排序的时间复杂度为 O(nlog2n)。
利用二路归并排序时, 需要利用与待排序数组相同的
辅助数组作临时单元, 故该排序方法的空间复杂度为
O(n),比前面介绍的其它排序方法占用的空间大 。
由于二路归并排序中, 每两个有序表合并成一个有序表
时, 若分别在两个有序表中出现有相同排序码, 则会使
前一个有序表中相同排序码先复制, 后一有序表中相同
排序码后复制, 从而保持它们的相对次序不会改变 。 所
以, 二路归并排序是一种稳定的排序方法 。
*9.5.2 多路归并排序
将三个或三个以上有序子区间合并成一个有序子区间
的排序, 称为多路归并排序 。 常见的有三路归并排序
（ 三个有序子区间合并成一个有序子区间 ）, 四路归
并排序 （ 四个有序子区间合并成一个有序子区间 ） 等,
具体实现的方法与二路归并排序类似, 在此, 不再赘
述 。
*9,6 分配排序
9.6.1 多关键字排序
在实际应用中, 有时的排序会需要按几种不同排序码来
排序 。 例如, 描述一个单位的职工信息, 既要按出生日
期排序, 又要按工资排序, 则是一种典型的多关键字排
序 。 又如, 将一副扑克牌中 52张牌按从小到大排列,
（ 规定花色大小为：梅花 <方块 <红桃 <黑桃, 面值大小
规定为,2<3<4<… <10<J<Q<K<A）, 则一副扑克牌的
排序也是多关键字排序 。
对于多关键字排序 （ 假设有 d个关键字 ）, 则可以按第 1、
2,…, d个关键字的顺序排序, 也可以按第 d,d-1,d-
2,…, 2,1个关键字的顺序排序 。 例如, 刚才的扑克
牌排序, 可以先按花色排成 4 堆, 然后将每一堆再按面
值排序, 则可以得到 52张牌的有序序列 。 具体实现不再
介绍 。
9.6.2链式基数排序
1．基数排序的基本思想
基数排序 （ radix sorting） 是和前面所述各类排序方法完
全不同的一种排序方法 。 在前面几节中, 实现排序主要
是通过排序码之间的比较和移动两项操作来进行的, 而
基数排序不需要进行排序码的比较, 它是一种借助多关
键字 （ 多个排序码 ） 排序的思想来实现单关键字排序的
排序方法 。
具体实现时, 假设每个元素有 d个排序码, 则可以先按
第 1个排序码对每个元素排序, 然后再按第 2个排序码排
序, …, 最后再按第 d个排序码排序 。 最后的结果即为
基数排序的结果 。
例如, 给定排序码序列 123,78,65,9,108,7,8,3，
68,309,基数排序的步骤见图 9-11。
初始状态,123 78 65 9 108 7 8 3 68 309
一趟（按个位）,123 3 65 7 78 108 8 68 9 309
三趟（按百位）,3 7 8 9 65 68 78 108 123 309
二趟（按十位）,3 7 8 9 108 309 123 65 68 78
图 9 - 1 1 基 数排序的步骤
具体实现时, 基数排序包含分配和收集, 分配是将第 k
（ 1≤k≤d） 个排序码相同的元素放到一个队列中 （ 按第 k
个排序码排序 ）, 收集是得到这一趟的排序结果 。 例如,
对刚才图 9-11的初始排序码, 分配和收集过程见图 9-12。
123 65 78 9 108 7 3 8 68 309
(a) 初始状态
3
123
65
7
68
8
108
78
309
9
e[ 0] e[ 1] e[ 2] e[ 3] e[ 4] e[ 5] e [ 6] e[ 7] e[ 8] e[ 9]
f[0 ] f[1 ] f[2 ] f[3 ] f[4 ] f[5 ] f[6 ] f[7 ] f[8 ] f[9 ]
（ b ）第一趟分配（按个位，有十个队列）
123 65 3 7 78 108 68 8 9 309
(c) 第一趟收集
e [ 0 ] e [ 1 ] e [ 2 ] e [ 3 ] e [ 4 ] e [ 5 ] e [ 6 ] e [ 7 ] e [ 8 ] e [ 9 ]
309
108
9
8
7
3
123
68
65
78
f[ 0 ] f[ 1 ] f[ 2 ] f[ 3 ] f[ 4 ] f[ 5 ] f[ 6 ] f[ 7 ] f[ 8 ] f[ 9 ]
(d) 第二趟分配（按十位，有十个队列）
3 8 7 9 108 309 65 123 68 78
(e ) 第二趟收集
e[ 0] e[ 1] e[ 2] e[ 3] e[ 4] e[ 5] e[ 6] e[ 7] e[ 8] e[ 9]
78
68
65
9
8
7
3
123
108 309
f[0 ] f[1 ] f[2 ] f[3 ] f[4 ] f[5 ] f[6 ] f[7 ] f[8 ] f[9 ]
(f) 第三趟分配（按百位，有十个队列）
3 8 7 9 65 68 108 78 123 30 9
(g) 第三趟收集
图 9 - 1 2 基数排序过程示意图
3.基数排序的效率分析
对于含有 n个元素的关键字 （ 每个关键字有 d个排序码,
每个排序码的取值范围从 c1到 crd）, 每一趟分配和
收集的时间复杂度为 O(n+crd-c1+1),由于有 d个排序
码, 故需进行 d趟分配和收集, 因此, 基数排序的时
间复杂度为 O(d(n+crd-c1+1))。
在基数排序中, 由于每个排序码的取值范围从 c1到
crd,故需要 crd-c1+1个队头和队尾指针, 故它的空间
复杂度为 O(n+crd-c1+1)。
由于基数排序中值相同的元素的相对位置在分配和收
集中，不会发生变化，所以基数排序是一种稳定的排
序方法。
9,7 各种内排序方法的比较和选择
9.7.1 各种内排序方法的比较
1,从时间复杂度比较
从平均时间复杂度来考虑, 直接插入排序, 冒泡排序,
直接选择排序是三种简单的排序方法, 时间复杂度都为
O(n2),而快速排序, 堆排序, 二路归并排序的时间复杂
度都为 O(nlog2n),希尔排序的复杂度介于这两者之间 。
若从最好的时间复杂度考虑, 则直接插入排序和冒泡排
序的时间复杂度最好, 为 O(n),其它的最好情形同平均情
形相同 。 若从最坏的时间复杂度考虑, 则快速排序的为
O(n2),直接插入排序, 冒泡排序, 希尔排序同平均情形
相同, 但系数大约增加一倍, 所以运行速度将降低一半,
最坏情形对直接选择排序, 堆排序和归并排序影响不大 。
2,从空间复杂度比较
归并排序的空间复杂度最大，为 O(n)，快速排序的空间复
杂度为 O(log2n)，其它排序的空间复杂度为 O（ 1）。
3.从稳定性比较
直接插入排序, 冒泡排序, 归并排序是稳定的排序方法,
而直接选择排序, 希尔排序, 快速排序, 堆排序是不稳定
的排序方法 。
4,从算法简单性比较
直接插入排序、冒泡排序、直接选择排序都是简单的排
序方法，算法简单，易于理解，而希尔排序、快速排序、
堆排序、归并排序都是改进型的排序方法，算法比简单
排序要复杂得多，也难于理解。
9.7.2 各种内排序方法的选择
1,从时间复杂度选择
对元素个数较多的排序, 可以选快速排序, 堆排序, 归
并排序, 元素个数较少时, 可以选简单的排序方法 。
2,从空间复杂度选择
尽量选空间复杂度为 O（ 1）的排序方法，其次选空间复
杂度为 O(log2n)的快速排序方法，最后才选空间复杂度为
O（ n）二路归并排序的排序方法。
3,一般选择规则
（ 1） 当待排序元素的个数 n较大, 排序码分布是
随机, 而对稳定性不做要求时, 则采用快速排序为宜 。
（ 2)当待排序元素的个数 n大, 内存空间允许, 且要求
排序稳定时, 则采用二路归并排序为宜 。
（ 3） 当待排序元素的个数 n大, 排序码分布
可能会出现正序或逆序的情形, 且对稳定性不做要求
时, 则采用堆排序或二路归并排序为宜 。
（ 4)当待排序元素的个数 n小, 元素基本有序或分布较
随机, 且要求稳定时, 则采用直接插入排序为宜 。
(5)当待排序元素的个数 n小, 对稳定性不做要求时,
则采用直接选择排序为宜, 若排序码不接近逆序, 也
可以采用直接插入排序 。 冒泡排序一般很少采用 。
数据结构（ C++描述）
目录
9,1 基本概念
9,2 插入排序
9,3 交换排序
9,4 选择排序
9,5 归并排序
*9,6 分配排序
退出
9,1 基本概念
9.1.1 排序介绍
排序 （ Sorting） 是数据处理中一种很重要的运算,
同时也是很常用的运算, 一般数据处理工作 25%的
时间都在进行排序 。 简单地说, 排序就是把一组记
录 （ 元素 ） 按照某个域的值的递增 （ 即由小到大 ）
或递减 （ 即由大到小 ） 的次序重新排列的过程 。
表 9-1 学生档案表
学号 姓名 年龄 性别
99001 王晓佳 18 男
99002 林一鹏 19 男
99003 谢宁 17 女
99004 张丽娟 18 女
99005 周涛 20 男
99006 李小燕 16 女
例如, 在表 9-1中, 若以每个记录的学号为关键字, 按
排序码年龄的递增 （ 由小到大 ） 排序, 则所有记录的排
序结果可简记为：
{（ 99006,16）, （ 99003,17）, （ 99001,18）,
（ 99004,18）, （ 99002,19）, （ 99005,20） }；
也可能为：
{（ 99006,16）, （ 99003,17）, （ 99004,18）,
（ 99001,18）, （ 99002,19）, （ 99005,20） }；
这两个结果都是表 9-1按年龄的递增排序结果 。 若按排序
码姓名来进行递增排序, 则得到的排序结果为：
{（ 99006,李小燕 ）, （ 99002,林一鹏 ）, （ 99001，
王晓佳 ）, （ 99003,谢宁 ）, （ 99004,张丽娟 ）,
（ 99005,周涛 ） }
当然, 我们还可以按排序码性别来进行递增排序, 在此
不再作进一步的分析 。
9.1.2 基本概念
1．排序码（ Sort Key）
作为排序依据的记录中的一个属性。它可以是任何一种
可比的有序数据类型，它可以是记录的关键字，也可以
是任何非关键字。如上例中的学生年龄。在此我们认为
对任何一种记录都可找到一个取得它排序码的函数
Skey(一个或个关键字的组合 )。
2,有序表与无序表
一组记录按排序码的递增或递减次序排列得到的结果被
称之为有序表, 相应地, 把排序前的状态称为无序表 。
3,正序表与逆序表
若有序表是按排序码升序排列的, 则称为升序表或正序
表, 否则称为降序表或逆序表 。 不失普遍性, 我们一般
只讨论正序表 。
4,排序定义
若给定一组记录序列 r1, r2, …, rn,其排序码分别
为 s1,s2, …, sn, 将这些记录排成顺序为 rk1,
rk2, …, rkn的一个序列 R’,满足条件 sk1≤sk2≤ … ≤skn，
获得这些记录排成顺序为 rp1, rp2, …, rpn的一个序
列 R”,满足条件 sp1≤sp2≤ … ≤spn的过程称为排序 。
也可以说，将一组记录按某排序码递增或递减排列的
过程，称为排序。
5,稳定与不稳定
因为排序码可以不是记录的关键字，同一排序码值可能对应
多个记录。对于具有同一排序码的多个记录来说，若采用的
排序方法使排序后记录的相对次序不变，则称此排序方法是
稳定的，否则称为不稳定的。在上例中（见表 9-1，按年龄排
序），如果一种排序方法使排序后的结果必为前一个结果，
则称此方法是稳定的；若一种排序方法使排序后的结果可能
为后一个结果，则称此方法是不稳定的。
6,内排序与外排序
按照排序过程中使用内外存的不同将排序方法分为内排序
和外排序 。 若排序过程全部在内存中进行, 则称为内排序；
若排序过程需要不断地进行内存和外存之间的数据交换,
则称为外排序 。 内排序大致可分为五类：插入排序, 交换
排序, 选择排序, 归并排序和分配排序 。 本章仅讨论内排
序 。
7,排序的时间复杂性
排序过程主要是对记录的排序码进行比较和记录的移动过
程 。 因此排序的时间复杂性可以算法执行中的数据比较次
数及数据移动次数来衡量 。 当一种排序方法使排序过程在
最坏或平均情况下所进行的比较和移动次数越少, 则认为
该方法的时间复杂性就越好, 分析一种排序方法, 不仅要
分析它的时间复杂性, 而且要分析它的空间复杂性, 稳定
性和简单性等 。
为了以后讨论方便，我们直接将排序码写成一个一维数
组的形式，具体类型设为 Elemtype，并且在没有声明的情
形下，所有排序都按排序码的值递增排列。
排序
插入排序（直插排序、二分排序、希尔排序）
交换排序（冒泡排序、快速排序）
选择排序 （直选排序、树型排序、堆排序）
归并排序（二路归并排序、多路归并排序）
分配排序 （多关键字排序、基数排序）
9,2 插入排序
9.2.1直接插入排序
1．直接插入排序的基本思想
直接插入排序 （ Straight Insertion Sorting） 的基本思想是：把
n个待排序的元素看成为一个有序表和一个无序表, 开始时
有序表中只包含一个元素, 无序表中包含有 n-1个元素, 排序
过程中每次从无序表中取出第一个元素, 把它的排序码依次
与有序表元素的排序码进行比较, 将它插入到有序表中的适
当位置, 使之成为新的有序表 。
2．直接插入的算法实现
void insertsort(ElemType R[],int n)
//待排序元素用一个数组 R表示, 数组有 n个元素
{ for ( int i=1; i<n; i++) //i表示插入次数, 共进行 n-1次
插入
{ ElemType temp=R[i]; //把待排序元素赋给 temp
int j=i-1;
while ((j>=0)&& (temp<R[j]))
{ R[j+1]=R[j]; j--; } // 顺序比较和移动
R[j+1]=temp;}
}
例如, n=6,数组 R的六个排序码分别为,17,3,25，
14,20,9。 它的直接插入排序的执行过程如图 9-1所
示 。
R[0 ] R[1 ] R[2 ] R[3 ] R[4 ] R[5 ]
初始状态 (1 7 ) 3 25 14 20 9
第一次插入 (3 17 ) 25 14 20 9
第二次插入 (3 17 25 ) 14 20 9
第三次插入 (3 14 17 25 ) 20 9
第四次插入 (3 14 17 20 25 ) 9
第五次插入 (3 9 14 17 20 25 )
图 9 - 1 直接插入排序示例
3,直接插入排序的效率分析从上面的叙述可以看出, 直接插入排序算法十分简单 。
那么它的效率如何呢？ 首先从空间来看, 它只需要一个
元素的辅助空间, 用于元素的位置交换 。 从时间分析,
首先外层循环要进行 n-1次插入, 每次插入最少比较一次
（ 正序 ）, 移动两次；最多比较 i次, 移动 i＋ 2次 （ 逆序 ）
（ i=1,2,…, n-1） 。 若分别用 Cmin, Cmax 和 Cave表示
元素的总比较次数的最小值, 最大值和平均值, 用 Mmin,
Mmax 和 Mave表示元素的总移动次数的最小值, 最大值和
平均值, 则上述直接插入算法对应的这些量为：
Cmin=n-1 M min=2（ n-1）
Cmax=1+2+… +n-1=（ n2-n） /2 M max=3+4+… +n+1=
（ n2+3n-4） /2
Cave=（ n2+n-2） /4 M max=（ n2+7n-8） /4
因此, 直接插入排序的时间复杂度为 O（ n2） 。
直接插入算法的元素移动是顺序的, 该方法是稳定的 。
9.2.2二分插入排序
1,二分插入排序的基本思想
二分插入排序 （ Binary Insert Sort） 的基本思想是：
在有序表中采用二分查找的方法查找待排元素的插
入位置 。
其处理过程：先将第一个元素作为有序序列, 进行 n-
1次插入, 用二分查找的方法查找待排元素的插入位
置, 将待排元素插入 。
3,二分插入排序的效率分析
二分插入算法与直接插入算法相比, 需要辅助空间与直接
插入排序基本一致；时间上, 前者的比较次数比直接插入
查找的最坏情况好, 最好的情况坏, 两种方法的元素的移
动次数相同, 因此二分插入排序的时间复杂度仍为 O
（ n2） 。
二分插入算法与直接插入算法的元素移动一样是顺序的,
因此该方法也是稳定的 。
2,二分插入排序的算法实现
其算法如下：
void BinaryInsertSort(ElemType R[],int n)
{ for(int i=1; i<n; i++) //共进行 n-1次插入
{ int left=0,right=i-1;ElemType temp=R[i];
while(left<=right)
{ int middle=(left+right)/2; //取中点
if(temp<R[middle]) right=middle-1; //取左区间
else left=middle+1; } //取右区间
for(int j=i-1;j>=left;j--)
R[j+1]=R[j]; //元素后移空出插入位
R[left]=temp; }}
9.2.3希尔排序
1,希尔排序的基本思想
希尔排序 （ Shell Sort） 又称为, 缩小增量排序, 。 是
1959年由 D.L.Shell提出来的 。 该方法的基本思想是：先
将整个待排元素序列分割成若干个子序列 （ 由相隔某个
,增量, 的元素组成的 ） 分别进行直接插入排序, 待整
个序列中的元素基本有序 （ 增量足够小 ） 时, 再对全体
元素进行一次直接插入排序 。 因为直接插入排序在元素
基本有序的情况下 （ 接近最好情况 ）, 效率是很高的,
因此希尔排序在时间效率上比前两种方法有较大提高 。
3,希尔排序的效率分析
虽然我们给出的算法是三层循环, 最外层循环为 log2n数
量级, 中间的 for循环是 n数量级的, 内循环远远低于 n数
量级, 因为当分组较多时, 组内元素较少；此循环次数
少；当分组较少时, 组内元素增多, 但已接近有序, 循
环次数并不增加 。 因此, 希尔排序的时间复杂性在 O
（ nlog2n） 和 O（ n2 ） 之间, 大致为 O（ n1,3） 。
例如, n=8,数组 R的八个元素分别为,17,3,30，
25,14,17,20,9。 下面用图 9-2给出希尔排序算法
的执行过程 。
17 3 30 25 14 17 20 9 初始状态,I =4
14 3 17 9 20 17 30 25 第二趟结果,I =1
3 9 14 17 17 20 25 30 第三趟结果
14 3 20 9 17 17 30 25 第一趟结果,I =2
图 9 - 2 希尔排序算法的执行过程
由于希尔排序对每个子序列单独比较, 在比较时进行元
素移动, 有可能改变相同排序码元素的原始顺序, 因此
希尔排序是不稳定的 。 例如, 给定排序码 3,4,2,2，
则希尔排序的结果变成 2,2,3,4 。
9,3 交换排序
9.3.1 冒泡排序
1．冒泡排序的基本思想
冒泡排序 （ Bubble Sorting） 的基本思想是：是通过对
待排序序列从后向前 （ 从下标较大的元素开始 ）, 依
次比较相邻元素的排序码, 若发现逆序则交换, 使排
序码较小的元素逐渐从后部移向前部 （ 从下标较大的
单元移向下标较小的单元 ）, 就象水底下的气泡一样
逐渐向上冒 。
因为排序的过程中, 各元素不断接近自己的位置, 如
果一趟比较下来没有进行过交换, 就说明序列有序,
因此要在排序过程中设置一个标志 flag判断元素是否进
行过交换 。 从而减少不必要的比较 。
2,冒泡排序的算法实现
下面给出冒泡排序算法 。
void Bubblesort(ElemType R[],int n)
{ int flag=1; //当 flag为 0则停止排序
for (int i=1; i<n; i++)
{ //i表示趟数, 最多 n-1趟
flag=0;//开始时元素未交换
for (int j=n-1; j>=i; j--)
if (R[j]<R[j-1]) { //发生逆序 ElemType t=R[j];
R[j]=R[j-1];
R[j-1]=t;flag=1; } //交换, 并标记发生了交换
if(flag==0)return; }}
例如, n=6,数组 R的六个排序码分别为,17,3,25,14，
20,9。 下面用图 9-3给出冒泡排序算法的执行过程 。
图 9 - 3 冒泡排序示例
R[0] R[1] R[2] R[3] R[4] R[5]
第一趟排序 3 (17 9 2 5 1 4 2 0 )
第二趟排序 3 9 (17 1 4 2 5 2 0 )
第三趟排序 3 9 1 4 (17 2 0 2 5 )
第 四趟排序 3 9 1 4 1 7 2 0 2 5
初始状态 （ 17 3 25 14 2 0 9 )
3,冒泡排序的效率分析
从上面的例子可以看出, 当进行完第三趟排序时, 数
组已经有序, 所以第四趟排序的交换标志为 0,即没进
行交换, 所以不必进行第四趟排序 。
从冒泡排序的算法可以看出, 若待排序的元素为正序,
则只需进行一趟排序, 比较次数为 （ n-1） 次, 移动元
素次数为 0；若待排序的元素为逆序, 则需进行 n-1趟
排序, 比较次数为 (n2-n)/2,移动次数为 3(n2-n )/2,因
此冒泡排序算法的时间复杂度为 O（ n2） 。 由于其中的
元素移动较多, 所以属于内排序中速度较慢的一种 。
因为冒泡排序算法只进行元素间的顺序移动, 所以是
一个稳定的算法 。
9.3.2 快速排序
1,快速排序的基本思想
快速排序（ Quick Sorting）是迄今为止所有内排序算
法中速度最快的一种。它的基本思想是：任取待排序
序列中的某个元素作为基准（一般取第一个元素），
通过一趟排序，将待排元素分为左右两个子序列，左
子序列元素的排序码均小于或等于基准元素的排序码，
右子序列的排序码则大于基准元素的排序码，然后分
别对两个子序列继续进行排序，直至整个序列有序。
快速排序是对冒泡排序的一种改进方法，算法中元素
的比较和交换是从两端向中间进行的，排序码较大的
元素一次就能够交换到后面单元，排序码较小的记录
一次就能够交换到前面单元，记录每次移动的距离较
远，因而总的比较和移动次数较少。
快速排序的过程为：把待排序区间按照第一个元素
（ 即基准元素 ） 的排序码分为左右两个子序列的过程
叫做一次划分 。 设待排序序列为 R[left]～ R[right],其
中 left为下限, right为上限, left＜ right,R[left]为该序
列的基准元素, 为了实现一次划分, 令 i,j的初值分别
为 left和 right。 在划分过程中, 首先让 j从它的初值开
始, 依次向前取值, 并将每一元素 R[j]的排序码同
R[left]的排序码进行比较, 直到 R[j]<R[left]时, 交换
R[j]与 R[left]的值, 使排序码相对较小的元素交换到左
子序列, 然后让 i从 i＋ 1开始, 依次向后取值, 并使每
一元素 R[i]的排序码同 R[j]的排序码 （ 此时 R[j]为基准
元素 ） 进行比较, 直到 R[i]＞ R[j]时, 交换 R[i]与 R[j]
的值, 使排序码大的元素交换到后面子区间；再接着
让 j从 j-1开始, 依次向前取值, 重复上述过程, 直到 i
等于 j,即指向同一位置为止, 此位置就是基准元素最
终被存放的位置 。 此次划分得到的前后两个待排序的
子序列分别为 R[left]～ R[i-1]和 R[i+1]～ R[right]。
例如, 给定排序码为,（ 46,55,13,42,94,05,17，
70）, 具体划分如图 9-4所示 。
[ 46 55 13 42 94 05 17 70 ]
i
j
[ 46 55 13 42 94 05 17 70 ]
i
j
[ 17 55 13 42 94 05 46 70 ]
i
j
[ 17 46 13 42 94 05 55 70 ]
i
j
[ 17 05 13 42 94 46 55 70 ]
i
j
[ 17 05 13 42 94 46 55 70 ]
i j
[ 17 05 13 42 94 46 55 70 ]
i
j
[ 17 05 13 42 94 ] 46 [ 55 70 ]
i j
图 9 - 4 快速排序的一次划分
从图 9-4可知, 通过一次划分, 将一个区间以基准值分成
两个子区间, 左子区间的值小于等于基准值, 右子区间
的值大于基准值 。 对剩下的子区间重复此划分步骤, 则
可以得到快速排序的结果 。
2,快速排序的算法实现
下面给出快速排序算法的递归算法如下：
void quicksort(ElemType R[],int left,int right)
{ int i=left,j=right; ElemType temp=R[i];
while (i<j)
{ while ((R[j]>temp)&&(j>i)) j=j-1;
if (j>i) { R[i]=R[j]; i=i+1; }
while ((R[i]<=temp)&&(j>i)) i=i+1;
if (i<j) { R[j]=R[i]; j=j-1; } }
//一次划分得到基准值的正确位置
R[i]=temp;
if (left<i-1) quicksort(R,left,i-1); //递归调用左子区间
if (i+1<right) quicksort(R,i+1,right); }//递归调用右子区间
3,快速排序的效率分析
若快速排序出现最好的情形 （ 左, 右子区间的长度大致
相等 ）, 则结点数 n 与二叉树深度 h 应满足
log2n<h<log2n+1, 所以总的比较次数不会超过 (n+1)
log2n。 因此, 快速排序的最好时间复杂度应为 O
（ nlog2n） 。 而且在理论上已经证明, 快速排序的平均
时间复杂度也为 O（ nlog2n） 。
若快速排序出现最坏的情形 （ 每次能划分成两个子区间,
但其中一个是空 ）, 则这时得到的二叉树是一棵单分枝
树, 得到的非空子区间包含有 n-i个 (i代表二叉树的层数
（ 1≤i≤n） 元素, 每层划分需要比较 n-i+2次, 所以总的
比较次数为 （ n2+3n-4） /2。 因此, 快速排序的最坏时间
复杂度为 O(n2)。
快速排序所占用的辅助空间为栈的深度, 故最好的空间
复杂度为 O（ log2n）, 最坏的空间复杂度为 O(n)。
快速排序是一种不稳定的排序方法。
9,4 选择排序
9.4.1 直接选择排序
1,直接选择排序的基本思想
直接选择排序 （ straight select sorting） 也是一种简单的
排序方法 。 它的基本思想是：第一次从 R[0]~R[n-1]中选
取最小值, 与 R[0]交换, 第二次从 R[1]~R[n-1]中选取最
小值, 与 R[1]交换, 第三次从 R[2]~R[n-1]中选取最小值,
与 R[2]交换, …, 第 i次从 R[i-1]~R[n-1]中选取最小值,
与 R[i-1]交换, …,第 n-1次从 R[n-2]~R[n-1]中选取最小值,
与 R[n-2]交换, 总共通过 n-1次, 得到一个按排序码从小
到大排列的有序序列 。
例如, 给定 n=8,数组 R中的 8个元素的排序码为,（ 8，
3,2,1,7,4,6,5）, 则直接选择排序过程如图 9-5
所示 。
初始状态 [ 8 3 2 1 7 4 6 5 ]
第一次 [ 1 3 2 8 7 4 6 5 ]
第二次 [ 1 2 3 8 7 4 6 5 ]
第三次 [ 1 2 3 8 7 4 6 5 ]
第四次 [ 1 2 3 4 7 8 6 5 ]
第五次 [ 1 2 3 4 5 8 6 7 ]
第六次 [ 1 2 3 4 5 6 8 7 ]
第七次 [ 1 2 3 4 5 6 7 8 ]
图 9 - 5 直接选择排序的过程示例
3,直接选择排序的效率分析
在直接选择排序中, 共需要进行 n-1次选择和交换, 每次
选择需要进行 n-i次比较 （ 1≤i≤n-1）, 而每次交换最
多需 3次移动, 因此, 总的比较次数 C= =(n2-n)/2，
总的移动次数 M= =3(n-1)。 由此可知, 直接选择
排序的时间复杂度为 O(n2)数量级, 所以当记录占用的字
节数较多时, 通常比直接插入排序的执行速度要快一些 。
由于在直接选择排序中存在着不相邻元素之间的互换,
因此, 直接选择排序是一种不稳定的排序方法 。 例如,
给定排序码为 3,7,3,2,1,排序后的结果为 1,2,3，
3,7。
??
?
?1
1
)(n
i
in
??
?
1
1
3
n
i
9.4.2 树形选择排序
从直接选择排序可知, 在 n个排序码中, 找出最小值需 n-
1次比较, 找出第二小值需 n-2次比较, 找出第三小值需
n-3次比较, 其余依此类推 。 所以, 总的比较次数为：
(n-1)+(n-2)+… +3+2+1= (n2-n)/2,那么, 能否对直接选择
排序算法加以改进, 使总的比较次数比 (n2-n)/2小呢？ 显
然, 在 n个排序码中选出最小值, 至少进行 n-1次比较,
但是, 继续在剩下的 n-1个关键字中选第二小的值, 就并
非一定要进行 n-2次比较, 若能利用前面 n-1次比较所得
信息, 则可以减少以后各趟选择排序中所用的比较次数,
比如 8个运动员中决出前三名, 不需要 7+6+5=18场比赛
（ 前提是, 若甲胜乙, 而乙胜丙, 则认为甲胜丙 ）, 最
多需要 11场比赛即可 （ 通过 7场比赛产生冠军后, 第二
名只能在输给冠军的三个对中产生, 需 2场比赛, 而第
三名只能在输给亚军的三个对中产生, 也需 2场比赛,
总共 11场比赛 ） 。 具体见图 9-6所示 。
A
A E
A
A
C
C D B F
B
B
G H
G
(a) 8 个队决出冠军的情形（共 7 场比赛）
B
* E
E
C
C
C D B F
B
B
G H
G
(b ) 决出亚军的情形（共 2 场比赛，少于 6 场）
C
* E
E
C
C
C D * F
F
F
G H
G
(c) 决出第三名的情形（共 2 场比赛，少于 6 场）
图 9 - 6 决出比赛前三名的过程示意图
从图 9-6（ a）可知,8个队经过 4场比赛，获胜的 4个队
进入半决赛，再经过 2场半决赛和 1场决赛即可知道冠军
属谁（共 7场比赛）按照锦标赛的传递关糸，亚军只能
产生于分别在决赛，半决赛和第一轮比赛中输给冠军的
选取手中，于是亚军只能在 b,c,e这 3个队中产生（见
图 9-6（ b）），即进行 2场比赛（ e 与 c一场,e与 c的胜
队与 b一场）后，即可知道亚军属谁。同理，第三名只
需在 c,f,g这 3个队产生（见图 9-6（ c））即进 2场比赛
（ f与 g一场,f与 g的胜队与 c一场）即可知道第三名属谁。
树形选择排序 （ tree selection sorting）, 又称锦标赛排序
（ tournament sorting）, 是一种按照锦标赛的思想进行
选择排序的方法 。 首先对 n个记录的排序码进行两两比
较, 然后在其中 ?n/2? 个较小者之间再进行两两比较, 如
此重复, 直到选出最小排序码为止 。
例如，给定排序码头 50,37,66,98,75,12,26,49，
树形选择排序过程见图 9-7。
6 6
12
50
37
3 7
12 26
12
37 6 6 98 75 12 26 49
(a ) 经过 7 次比较得到最小值 12
6 6
26
50
37
3 7
75 26
26
37 6 6 98 75 ∞ 26 49
(b) 输出 12 后，经过 2 次比较得到第二小值 26
6 6
49
50
37
3 7
75 49
37
37 6 6 98 75 ∞ ∞ 49
(c) 输出 12, 26 后，经过 2 次比较得到第三小值 37
6 6
49
50
50
50
75 49
49
∞ 6 6 98 75 ∞ ∞ 49
（ d ）输出 12,2 6,3 7 后，经过 2 次比较得到第四小值 49
6 6
75
50
50
50
75 ∞
50
∞ 6 6 98 75 ∞ ∞ ∞
(e) 输出 12,26,37,49 后，经过 1 次比较得到第五小值 50
6 6
75
∞
∞
66
75 ∞
66
∞ 6 6 98 75 ∞ ∞ ∞
(f) 输出 12,26,37,49,50 后，经过 1 次比较得到第六小值 66
98
75
∞
∞
98
75 ∞
75
∞ ∞ 98 75 ∞ ∞ ∞
( g ) 输出 12,2 6,3 7,4 9,5 0,6 6 后，经过 1 次比较得到第七小值 75
98
∞
∞
∞
98
∞ ∞
98
∞ ∞ 98 ∞ ∞ ∞ ∞
( h ) 输出 12,2 6,3 7,4 9,5 0,6 6,7 5 后，经过 1 次比较得到第八小值 98
图 9 - 7 树形选择排序示意过程
9.4.3 堆排序
1,堆的定义
若有 n个元素的排序码 k1,k2,k3,…, kn,当满足如下
条件：
ki≤k2i ki≥k2i
（ 1） ki≤k2i+1 或 (2) ki≥k2i+1 其中
i=1,2,…,?n/2?
则称此 n个元素的排序码 k1,k2,k3,…, kn为一个堆 。
若将此排序码按顺序组成一棵完全二叉树, 则 （ 1） 称为
小根堆 （ 二叉树的所有根结点值小于或等于左右孩子的
值 ）, （ 2） 称为大根堆 （ 二叉树的所有根结点值大于或
等于左右孩子的值 ） 。
若 n个元素的排序码 k1,k2,k3,…, kn满足堆, 且让结
点按 1,2,3,…, n顺序编号, 根据完全二叉树的性质
（ 若 i为根结点, 则左孩子为 2i,右孩子为 2i+1） 可知,
堆排序实际与一棵完全二叉树有关 。 若将排序码初始序
列组成一棵完全二叉树, 则堆排序可以包含建立初始堆
（ 使排序码变成能符合堆的定义的完全二叉树 ） 和利用
堆进行排序两个阶段 。
2,堆排序的基本思想
将排序码 k1,k2,k3,…, kn表示成一棵完全二叉树，
然后从第 ?n/2? 个排序码开始筛选，使由该结点作根结
点组成的子二叉树符合堆的定义，然后从第 ?n/2? -1个排
序码重复刚才操作，直到第一个排序码止。这时候，该
二叉树符合堆的定义，初始堆已经建立。
接着, 可以按如下方法进行堆排序：将堆中第一个结点
（ 二叉树根结点 ） 和最后一个结点的数据进行交换 （ k1与
kn）, 再将 k1~kn-1重新建堆, 然后 k1和 kn-1交换, 再将
k1~kn-2重新建堆, 然后 k1和 kn-2交换, 如此重复下去, 每次
重新建堆的元素个数不断减 1,直到重新建堆的元素个数
仅剩一个为止 。 这时堆排序已经完成, 则排序码 k1,k2，
k3,…, kn已排成一个有序序列 。
若排序是从小到大排列, 则可以用建立大根堆实现堆排
序, 若排序是从大到小排列, 则可以用建立小根堆实现
堆排序 。
例如, 给定排序码 46,55,13,42,94,05,17,70，
建立初始堆的过程如图 9-8所示 。
4 6
5 5
42 94
7 0
1 3
05 17
4 6
5 5
70 94
42
1 3
05 17
4 6
5 5
7 0 94
42
17
05 13
4 6
94
70 55
42
17
05 13
94
7 0
4 6 55
42
17
05 13
图 9 - 8 建立初始大根堆的过程示意图
（ e ）成堆
（ c ）将以 5 5 为根的子 树调整成堆
（ d ）将以 4 6 为根的子树调整成堆
（ a ）初始无序的结点，从 42 开始调整
（ b ）将以 13 为根的子树调整成堆
对排序码 46,55,13,42,94,05,17,70,建成如图 9-
8(e)所示的大根堆后, 堆排序过程如图 9-9所示 。 94
7 0
4 6 55
42
17
05 13
42
7 0
4 6 55
94
17
05 13
( a) 初始堆 ( b ) 94 与 42 交换
70
55
4 6 42
94
17
05 13
13
55
4 6 42
94
17
05 70
(c) 前 7 个排序码重新建成堆 (d) 70 和 13 交换
55
46
13 42
94
17
05 70
05
46
13 42
94
17
55 70
(e) 前 6 个排序码重新建成堆 (f) 55 和 05 交换 46
42
13 05
94
17
55 70
05
42
13 46
94
17
55 70
( g ) 前 5 个排序码重新建成堆 (h) 46 和 05 交换
42
13
05 46
94
17
55 70
05
13
42 46
94
17
55 70
(i) 前 4 个排序码重新建成堆 (j) 42 和 05 交换
17
13
42 46
94
05
55 70
05
13
42 46
94
17
55 70
( k) 前 3 个排序码重新建成堆 ( l) 1 7 和 05 交换
13
05
42 46
94
17
55 70
05
13
42 46
94
17
55 70
(m ) 前 2 个排序码重新建成堆 ( n ) 13 和 05 交换
图 9 - 9 堆排序过程示意图
从图 9-9（ n） 可知, 将其结果按完全二叉树形式输出,
则得到结果为,05,13,17,42,46,55,70,94,即
为堆排序的结果 。
4,堆排序的效率分析
在整个堆排序中, 共需要进行 n+?n/2? -1次筛选运算, 每次
筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动
次数都不会超过完全二叉树的深度, 所以, 每次筛选运算的
时间复杂度为 O(log2n),故整个堆排序过程的时间复杂度为
O(nlog2n)。
堆排序占用的辅助空间为 1（ 供交换元素用 ）, 故它
的空间复杂度为 O（ 1） 。
堆排序是一种不稳定的排序方法, 例如, 给定排序码：
2,1,2,它的排序结果为,1,2,2。
9,5 归并排序
9.5.1 二路归并排序
二路归并排序的基本思想
二路归并排序的基本思想是：将两个有序子区间 （ 有序表 ）
合并成一个有序子区间, 一次合并完成后, 有序子区间的
数目减少一半, 而区间的长度增加一倍, 当区间长度从 1
增加到 n（ 元素个数 ） 时, 整个区间变为一个, 则该区间
中的有序序列即为我们所需的排序结果 。
例如, 给定排序码 46,55,13,42,94,05,17,70,二
路归并排序过程如图 9-10所示 。
三趟归并,[0 5 13 17 42 46 55 70 94 ]
二趟归并,[1 3 42 46 55] [0 5 17 70 94 ]
一趟归并,[4 6 55] [1 3 42 ] [0 5 94] [1 7 70]
初始状态,[4 6] [5 5] [1 3] [4 2] [9 4] [0 5] [1 7] [7 0]
图 9 - 10 二路归并排序过程示意图
3,二路归并排序的效率分析
二路归并排序的时间复杂度等于归并趟数与每一趟时间复
杂度的乘积 。 而归并趟数为 ?log2n? (当 ?log2n? 为奇数时, 则
为 ?log2n? +1)。 因为每一趟归并就是将两两有序子区间合并
成一个有序子区间, 而每一对有序子区间归并时, 记录的
比较次数均小于等于记录的移动次数 （ 即由一个数组复制
到另一个数组中的记录个数 ）, 而记录的移动次数等于这
一对有序表的长度之和, 所以, 每一趟归并的移动次数均
等于数组中记录的个数 n,即每一趟归并的时间复杂度为
O(n)。 因此, 二路归并排序的时间复杂度为 O(nlog2n)。
利用二路归并排序时, 需要利用与待排序数组相同的
辅助数组作临时单元, 故该排序方法的空间复杂度为
O(n),比前面介绍的其它排序方法占用的空间大 。
由于二路归并排序中, 每两个有序表合并成一个有序表
时, 若分别在两个有序表中出现有相同排序码, 则会使
前一个有序表中相同排序码先复制, 后一有序表中相同
排序码后复制, 从而保持它们的相对次序不会改变 。 所
以, 二路归并排序是一种稳定的排序方法 。
*9.5.2 多路归并排序
将三个或三个以上有序子区间合并成一个有序子区间
的排序, 称为多路归并排序 。 常见的有三路归并排序
（ 三个有序子区间合并成一个有序子区间 ）, 四路归
并排序 （ 四个有序子区间合并成一个有序子区间 ） 等,
具体实现的方法与二路归并排序类似, 在此, 不再赘
述 。
*9,6 分配排序
9.6.1 多关键字排序
在实际应用中, 有时的排序会需要按几种不同排序码来
排序 。 例如, 描述一个单位的职工信息, 既要按出生日
期排序, 又要按工资排序, 则是一种典型的多关键字排
序 。 又如, 将一副扑克牌中 52张牌按从小到大排列,
（ 规定花色大小为：梅花 <方块 <红桃 <黑桃, 面值大小
规定为,2<3<4<… <10<J<Q<K<A）, 则一副扑克牌的
排序也是多关键字排序 。
对于多关键字排序 （ 假设有 d个关键字 ）, 则可以按第 1、
2,…, d个关键字的顺序排序, 也可以按第 d,d-1,d-
2,…, 2,1个关键字的顺序排序 。 例如, 刚才的扑克
牌排序, 可以先按花色排成 4 堆, 然后将每一堆再按面
值排序, 则可以得到 52张牌的有序序列 。 具体实现不再
介绍 。
9.6.2链式基数排序
1．基数排序的基本思想
基数排序 （ radix sorting） 是和前面所述各类排序方法完
全不同的一种排序方法 。 在前面几节中, 实现排序主要
是通过排序码之间的比较和移动两项操作来进行的, 而
基数排序不需要进行排序码的比较, 它是一种借助多关
键字 （ 多个排序码 ） 排序的思想来实现单关键字排序的
排序方法 。
具体实现时, 假设每个元素有 d个排序码, 则可以先按
第 1个排序码对每个元素排序, 然后再按第 2个排序码排
序, …, 最后再按第 d个排序码排序 。 最后的结果即为
基数排序的结果 。
例如, 给定排序码序列 123,78,65,9,108,7,8,3，
68,309,基数排序的步骤见图 9-11。
初始状态,123 78 65 9 108 7 8 3 68 309
一趟（按个位）,123 3 65 7 78 108 8 68 9 309
三趟（按百位）,3 7 8 9 65 68 78 108 123 309
二趟（按十位）,3 7 8 9 108 309 123 65 68 78
图 9 - 1 1 基 数排序的步骤
具体实现时, 基数排序包含分配和收集, 分配是将第 k
（ 1≤k≤d） 个排序码相同的元素放到一个队列中 （ 按第 k
个排序码排序 ）, 收集是得到这一趟的排序结果 。 例如,
对刚才图 9-11的初始排序码, 分配和收集过程见图 9-12。
123 65 78 9 108 7 3 8 68 309
(a) 初始状态
3
123
65
7
68
8
108
78
309
9
e[ 0] e[ 1] e[ 2] e[ 3] e[ 4] e[ 5] e [ 6] e[ 7] e[ 8] e[ 9]
f[0 ] f[1 ] f[2 ] f[3 ] f[4 ] f[5 ] f[6 ] f[7 ] f[8 ] f[9 ]
（ b ）第一趟分配（按个位，有十个队列）
123 65 3 7 78 108 68 8 9 309
(c) 第一趟收集
e [ 0 ] e [ 1 ] e [ 2 ] e [ 3 ] e [ 4 ] e [ 5 ] e [ 6 ] e [ 7 ] e [ 8 ] e [ 9 ]
309
108
9
8
7
3
123
68
65
78
f[ 0 ] f[ 1 ] f[ 2 ] f[ 3 ] f[ 4 ] f[ 5 ] f[ 6 ] f[ 7 ] f[ 8 ] f[ 9 ]
(d) 第二趟分配（按十位，有十个队列）
3 8 7 9 108 309 65 123 68 78
(e ) 第二趟收集
e[ 0] e[ 1] e[ 2] e[ 3] e[ 4] e[ 5] e[ 6] e[ 7] e[ 8] e[ 9]
78
68
65
9
8
7
3
123
108 309
f[0 ] f[1 ] f[2 ] f[3 ] f[4 ] f[5 ] f[6 ] f[7 ] f[8 ] f[9 ]
(f) 第三趟分配（按百位，有十个队列）
3 8 7 9 65 68 108 78 123 30 9
(g) 第三趟收集
图 9 - 1 2 基数排序过程示意图
3.基数排序的效率分析
对于含有 n个元素的关键字 （ 每个关键字有 d个排序码,
每个排序码的取值范围从 c1到 crd）, 每一趟分配和
收集的时间复杂度为 O(n+crd-c1+1),由于有 d个排序
码, 故需进行 d趟分配和收集, 因此, 基数排序的时
间复杂度为 O(d(n+crd-c1+1))。
在基数排序中, 由于每个排序码的取值范围从 c1到
crd,故需要 crd-c1+1个队头和队尾指针, 故它的空间
复杂度为 O(n+crd-c1+1)。
由于基数排序中值相同的元素的相对位置在分配和收
集中，不会发生变化，所以基数排序是一种稳定的排
序方法。
9,7 各种内排序方法的比较和选择
9.7.1 各种内排序方法的比较
1,从时间复杂度比较
从平均时间复杂度来考虑, 直接插入排序, 冒泡排序,
直接选择排序是三种简单的排序方法, 时间复杂度都为
O(n2),而快速排序, 堆排序, 二路归并排序的时间复杂
度都为 O(nlog2n),希尔排序的复杂度介于这两者之间 。
若从最好的时间复杂度考虑, 则直接插入排序和冒泡排
序的时间复杂度最好, 为 O(n),其它的最好情形同平均情
形相同 。 若从最坏的时间复杂度考虑, 则快速排序的为
O(n2),直接插入排序, 冒泡排序, 希尔排序同平均情形
相同, 但系数大约增加一倍, 所以运行速度将降低一半,
最坏情形对直接选择排序, 堆排序和归并排序影响不大 。
2,从空间复杂度比较
归并排序的空间复杂度最大，为 O(n)，快速排序的空间复
杂度为 O(log2n)，其它排序的空间复杂度为 O（ 1）。
3.从稳定性比较
直接插入排序, 冒泡排序, 归并排序是稳定的排序方法,
而直接选择排序, 希尔排序, 快速排序, 堆排序是不稳定
的排序方法 。
4,从算法简单性比较
直接插入排序、冒泡排序、直接选择排序都是简单的排
序方法，算法简单，易于理解，而希尔排序、快速排序、
堆排序、归并排序都是改进型的排序方法，算法比简单
排序要复杂得多，也难于理解。
9.7.2 各种内排序方法的选择
1,从时间复杂度选择
对元素个数较多的排序, 可以选快速排序, 堆排序, 归
并排序, 元素个数较少时, 可以选简单的排序方法 。
2,从空间复杂度选择
尽量选空间复杂度为 O（ 1）的排序方法，其次选空间复
杂度为 O(log2n)的快速排序方法，最后才选空间复杂度为
O（ n）二路归并排序的排序方法。
3,一般选择规则
（ 1） 当待排序元素的个数 n较大, 排序码分布是
随机, 而对稳定性不做要求时, 则采用快速排序为宜 。
（ 2)当待排序元素的个数 n大, 内存空间允许, 且要求
排序稳定时, 则采用二路归并排序为宜 。
（ 3） 当待排序元素的个数 n大, 排序码分布
可能会出现正序或逆序的情形, 且对稳定性不做要求
时, 则采用堆排序或二路归并排序为宜 。
（ 4)当待排序元素的个数 n小, 元素基本有序或分布较
随机, 且要求稳定时, 则采用直接插入排序为宜 。
(5)当待排序元素的个数 n小, 对稳定性不做要求时,
则采用直接选择排序为宜, 若排序码不接近逆序, 也
可以采用直接插入排序 。 冒泡排序一般很少采用 。
