返回本章首页
下一页
上一页
第九章查找与排序
顺序查找是一种最基本和最简单的查找方法。它
的思路是，从表中的第一个元素开始，将给定
的值与表中逐个元素的关键字进行比较，直到
两者相符，查到所要找的元素为止。否则就是
表中没有要找的元素，查找不成功。对于表中
记录的关键字是无序的表，只能采用这种方法。
描述顺序查找的算法见框图 8-1。其中 n是表 r的
长度,k是要查的元素的关键字,i查到的元素
的序号。
上一章
下一章
返回目录
返回本章首页
下一页
上一页
折半查找又称二分查找, 是针对有序表进行查找的简单,
有效而又较常用的方法 。 所谓 有序表, 即要求表中的
各元素按关键字的值有序 （ 升序或降序 ） 存放 。
折半查找不像顺序查找那样, 从第一个记录开始逐个顺
序搜索, 其基本思想是：首先选取表中间位置的记录,
将其关键字与给定关键字 k进行比较, 若相等, 则查找
成功；否则, 若 k值比该关键字值大, 则要找的元素一
定在表的后半部分 （ 或称右子表 ）, 则继续对右子表
进行折半查找；若 k值比该关键字值小, 则要找的元素
一定在表的前半部分 （ 左子表 ）, 同样应继续对左子
表进行折半查找 。 每进行一次比较, 要么找到要查找
的元素, 要么将查找的范围缩小一半 。 如此递推, 直
到查找成功或把要查找的范围缩小为空 （ 查找失败 ） 。
设表的长度为 n，表的被查找部分的头为 low，尾为 high，
初始时,low=1,high=n,k为关键字的值。
返回本章首页
下一页
上一页
（ 2） 若 k=r[mid].key,成功, 否则：
若 k<r[mid].key,则 high=mid― 1,重复 （ 1） ；
若 k>r[mid].key,则 low=mid+1,重复 （ 1） ；
直到成功或不成功 （ 此时 low>high） 。
具体算法如下：
Void binsrch(struct node r[ ],int n,int k)
{ int mid,low,high,find;
low=1; high=n;find=0; /*置区间初值 */
while ((low<=high) && (!find))
{ mid=(low+high)/2; /*求中点 */
if (k= = r[mid].key)
find=1; /*已查到 */
else if(k>r[mid].key )
low=mid+1; /*在后半区间查找 */
else high=mid-1; /*在前半区间查找 */
}
if (find)
return (mid); /*查找成功, 返回找到元素的位置 */
else return (0); /*查找不成功, 返回 0标记 */
}
返回本章首页
下一页
上一页
采用折半查找, 当查找成功时, 最少比较次数为
一次, 如在上例中查找关键字值为 18的结点,
只需一次比较 。 最多经过 log2n次比较之后, 待
查找子表要么为空, 要么只剩下一个结点, 所
以要确定查找失败需要 log2n次或 log2n+1次比
较 。 可以证明, 折半查找的平均查找长度是：
从折半查找的平均查找长度 ASL来看，当表的长
度 n很大时，该方法尤其能显示出其时间效率。
但由于折半查找的表仍是线性表，若经常要进
行插入、删除操作，则元素排列费时太多，因
此折半查找比较适合于一经建立就很少改动而
又需要经常查找的线性表，较少查找而又经常
需要改动的线性表可以采用链接存储，使用顺
序查找。
返回本章首页
下一页
上一页
分块查找
在处理线性表时, 如果既希望能够快速查找, 又要经常
动态变化, 则可以采用分块查找方法 。 分块查找又称
索引顺序查找, 要求将待查的元素均匀的分成块, 块
间按大小排序, 块内不排序 。 因此需要建立一个块的
最大 （ 或最小 ） 关键字表, 称之为, 索引表, 。
具体而言，假设我们按结点元素关键字升序方式组织表
中各块，则要求第一块中任一结点的关键字值都小于
第二块中所有结点的关键字值；第二块中任一结点的
关键字值都小于第三块中所有结点的关键字值；如此
类推。然后选择每块中的最大（或最小）关键字值组
成索引表。换言之，索引表中的结点个数等于线性表
被分割的块数。
返回本章首页
下一页
上一页
例如要找关键字为 k的元素, 则先用折半查找法由索引表查出 k所在的块, 再
用顺序查找法在对应的块中找出 k。 在图 8-2中若要找关键字值为 41的元
素, 则先由索引表查出 41在第二块中 （ 29<41<64）, 再在第二块中找到
41。
由此我们可以总结：分块查找分两步进行, 第一步确定要查找结点在表中的
哪一块, 第二步在确定的块中找到该结点 。
分块查找的平均查找长度为：
ASL=ASLb+ASLe
其中 ASLb是折半查找的平均查找长度, ASLe是用顺序查找法查块内元素的
平均查找长度 。 设每块中有 s个元素, 可以近似的得到：
可以看出分块查找的平均查找长度位于顺序查找和折半查找之间 。
下面我们简单的对以上几种查找方法做出比较：
（ 1） 平均查找长度：折半查找最小, 分块查找次之, 顺序查找最大；
（ 2） 表的结构：顺序查找对有序表, 无序表均适用；折半查找仅适用于有
序表；分块查找要求表中元素是逐段有序的, 就是块与块之间的记录按
关键字有序；
（ 3）存储结构：顺序查找和分块查找对向量和线性链表结构均适用；折半
查找只适用于向量存储结构的表，因而要求表中元素基本不变，而在需
要插入或删除运算时，要移动元素，才能保持表的有序性，所以影响了
查找效率。
返回本章首页
下一页
上一页
哈希法
哈希法又名散列法,因其英文单词 Hash而得名,是一种完全不同的查找方法 。
前面我们所介绍的三种查找方法的共同特点在于：通过对关键字的一系
列比较, 逐步缩小查找范围, 直到确定结点的存储位置或确定查找失败 。
而哈希法则希望不经过任何比较, 一次存取就能得到所查元素, 因此必
须在记录的存储位置和它的关键字之间建立一个确定的对应关系, 使得
每个关键字和结构中一个唯一的存储位置相对应, 这样查找时只需对结
点的关键字进行某种运算就能确定结点在表中的位置 。 因此哈希法的平
均比较次数和表中所含结点的个数无关 。
打个比方让我们更清楚的认识哈希法的不同。假定某教室有 35个座位，如果
不加限定让学生任意就座，则要找某个学生时就要将待找学生与当前座
位上的学生一一做比较，这就是我们前面所介绍的查找方法的大致思路。
而哈希法则要限定学生所坐的位置，比如可规定学生座位的编号应与其
学号的末两位相同，则学号为 993605的学生应坐编号为 5的座位。这样我
们要找某个学生时只需根据其学号的末两位到相应座位上去找即可，不
必一一比较了。在这个例子里，学生好比记录，学号则为关键字，对关
键字进行的操作则是取其末两位，用以确定记录的位置。
返回本章首页
下一页
上一页
哈希函数的构造方法
一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内, 以尽可能减
少冲突 。 但鉴于实际问题中关键字的不同, 没法构造出统一的哈希函数 。 从而构
造哈希函数的方法多种多样, 这里只介绍一些比较常用的, 计算较为简便的方法 。
1,自身函数
关键字自身作为哈希函数, 即 H（ k） =k,也可自身加上一个常数作为哈希函数, 即
H(k)=k+c。 例如上例中建立的哈希函数 H(学号 )=学号 -9900采用的就是这样的方法 。
但这种函数只适用于给定的一组关键字为关键字集合中的全体元素的情况, 故不
常用 。
2,除余法
选择一个适当的正整数 m,用 m去除关键字, 取其余数作为散列地址, 即 H（ key）
=key%m。 上例中后来所设定的函数 H(学号 )=学号 %10采用的就是除余法 。
但是在这种方法中, m的选择是值得研究的 。 如果选择关键字内部代码基数的幂次来
除关键字, 其结果必定是关键字的低位数字均匀性较差 。 若取 m为任意偶数, 则
当关键字内部代码为偶数时, 得到的哈希函数值为偶数；若关键字内部代码为奇
数, 则哈希函数值为奇数 。 因此, m为偶数也是不好的 。 理论分析和试验结果均
证明 m应取小于存储区容量的素数 。
返回本章首页
下一页
上一页
查找,根据给定的某个值, 在表中确定一个关键字等于给定值的记录或数据
元素 。
关键字 (Keyword)：一个或一组能唯一标识该记录的数据项称为该记录的关
键字 。
平均查找长度 （ Average Search Length）,为确定记录在表中的位置所进行
的和关键字的比较的次数的期望值称之为查找算法的平均查找长度, 简
称 ASL。
有序表,表中的各元素按关键字的值有序 （ 升序或降序 ） 存放 。
哈希表,将结点的关键字 key作为自变量, 通过一个确定的函数关系 H,计算
出相应的函数值 H(key),然后以 H(key)作为该结点的存储单元地址 。 用这
种方式建立起来的线性表称为哈希表或叫散列表
哈希函数,把结点关键字转换为该结点存储单元地址的函数 H称为哈希函数
或叫散列函数 。
在学习这些概念的基础上，我们先后学习了三种基于将待查元素的关键字和
表中元素的关键字进行比较的查找算法，即顺序查找、折半查找和分块
查找，并对它们做出比较。我们也学习了一种不同的查找算法，即哈希
法，它的基本思路是：在记录的存储位置和它的关键字之间建立一个确
定的对应关系，使得每个关键字和结构中一个唯一的存储位置相对应，
这样查找时只需对结点的关键字进行某种运算就能确定结点在表中的位
置，其间我们知道了如何构造哈希函数和如何解决冲突问题。读者应熟
悉各种查找算法的思路、算法及性能分析，以灵活应用于各种实际问题
中。
返回本章首页
下一页
上一页
排序
排序 （ sorting） 是计算机程序设计中的一种重要操作, 它
的功能是将一个数据元素 （ 或记录 ） 的任意序列, 重
新排列成一个按关键字有序的序列 。
由于待排序的记录数量不同，使得排序过程中涉及的存
储器不同，可将排序方法分为两大类：一类是内部排
序，指的是待排序记录存放在计算机存储器中进行的
排序过程；另一类是外部排序，指的是待排序记录的
数量很大，以致内存一次不能容纳全部记录，在排序
过程中对外存进行访问的排序过程。
返回本章首页
下一页
上一页
插入排序
线性插入排序的基本思想是：第 1遍，将初始文
件中的记录 R1看作有序子文件，将 R2插入这个
子文件中。若 R2的关键字小于 R1的关键字，则
R2插在 R1的前面，否则 R2插在 R1的后面。第 2
遍，将 R3插入前面的两个记录的有序子文件中，
得到 3个记录的有序子文件。依此类推，继续
进行下去，直到将 Rn插入到前面的 n-1个记录的
有序子文件中，最后得到 n个记录的有序文件。
返回本章首页
下一页
上一页
线性插入排序的基本思想是：第 1遍, 将
初始文件中的记录 R1看作有序子文件,
将 R2插入这个子文件中 。 若 R2的关键
字小于 R1的关键字, 则 R2插在 R1的前
面, 否则 R2插在 R1的后面 。 第 2遍,
将 R3插入前面的两个记录的有序子文
件中, 得到 3个记录的有序子文件 。
依此类推, 继续进行下去, 直到将 Rn
插入到前面的 n-1个记录的有序子文
件中, 最后得到 n个记录的有序文件 。
图 9-1所示为线性插入排序的例子 。
为了避免检测是否应插在 R1的前面，在
R1的前面设立记录 R0，它既是中间变
量，又是监视哨。设（ R1,R2,…,
Ri-1）是已排序的有序子文件，则插
入 Ri的步骤是：首先将 Ri存放到 Ro中，
然后将 Ko（即原 Ri的关键字 Ki）依
次与 Ki-1,Ki-2,… 比较，若 Ko<Kj
（ j=i-1,i-2,…, 1），则 Rj后移一
个位置，否则停止比较和移动；最后，
将 Ro（即原来待插入的记录 Ri）移到
j+1的位置上。由于 Ri的前面有监视
哨 Ro，因此不必每次判断下标 j是否
出界。算法描述如下：
返回本章首页
下一页
上一页
void insertsort(struct node r[ n+1],int n)
/* r[n+1]为一维数组, 其中 r[0]为监视哨, r[1]到 r[n]为待
排序的 n个记录, 排序好的记录仍放在 r中 */
{ for(i=2;i<=n;i++) /*共进行 n-1趟 */
{ r[0]=r[i]; /*r[0]为监视哨, 也可
做下边循环结束标志 */
j=i-1;
while(r[j].key>r[0].key)
{ r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
}
返回本章首页
下一页
上一页
折半插入排序
在线性插入排序中, 我们采用顺序查找法来确定记录的插入位置 。 由于 （ R1,R2,…, Ri-1） 是有
序子文件, 我们可以采用折半查找法来确定 R1的插入位置, 这种排序称为折半插入排序 。 其
算法可写出如下：
void binarysort(struct node r[ n+1],int n)
/*按关键字递增的次序对记录 r[1],r[2],……,r[n]进行折半插入排序 */
{ for(i=2;i<=n;i++)
{ r[0]=r[i];
l=1;
h=i-1;
while(l<=h)
{ mid=(l+h)/2;
if(r[0].key<r[mid].key)
h=mid-1;
else l=mid+1;
}
for(j=i-1;j>=l;j--)
r[j+1]=r[j];
r[l]=r[0];
}
}
在上面的算法中，每插入一个 R1，平均比较次数为 log2i。
返回本章首页
下一页
上一页
希尔排序
希尔排序 （ Shell’s Method） 又称, 缩小增量排序, （ Diminishing Increment Sort）,
是由 D.L.Shell在 1959年提出来的 。 它的作法是：先取定一个小于 n的整数 d1作为第
一个增量, 把文件的全部记录分成 d1个组, 所有距离为 d1的倍数的记录放在同一
个组中, 在各组内进行直接插入排序；然后, 到第二个增量 d2<d1重复上述分组和
排序, 直至所取的增量 dt=1（ dt<dt-1<… <d2<d1）, 即所有记录放在同一组中进行
直接插入排序为止 。
先从一个具体的例子来看希尔排序 。 假设待排序文件有 10个记录, 其关键字分别是：
49,38,65,97,76,13,27,49/,55,04。 增量序列取值依次为,5,3,1。
第一趟排序时, d1=5,整个文件被分成 5组,（ R1,R6）, （ R2,R7）, …, （ R5，
R10） 各组中的第 1个记录都自成一个有序区, 我们依次将各组的第 2个记录 R6，
R7,… R10分别插入到各组的有序区中, 使文件的各组均是有序的, 其结果见图 9-
2的第七行 。
第二趟排序时, d2=3,整个文件分成三组,（ R1,R4,R7,R10）, （ R2,R5,R8）,
（ R3,R6,R9）, 各组的第 1个记录仍自成一个有序区, 然后依次将各组的第 2个
记录 R4,R5,R6分别插入到该组的当前有序区中, 使得 （ R1,R4）, （ R2,R5）,
（ R3,R6） 均变为新的有序区, 接着依次将各组的第 3个记录 R7,R8,R9分别插
入到该组当前的有序区中, 又使得 （ R1,R4,R7）, （ R2,R5,R8）, （ R3,R6，
R9） 均变为新的有序区, 最后将 R10插入到有序区 （ R1,R4,R7） 中就得到第二
趟排序结果 。
最后一趟排序时,d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。
返回本章首页
下一页
上一页
若不设置监视哨，根据上例的分析不难写出希尔排序算
法，请读者自行完成之。下面我们先分析如何设置监
视哨，然后给出具体算法。设某一趟希尔排序的增量
为 h，则整个文件被分成 h组：（ R1,Rh+1,R2h+1,… ），
（ R2,Rh+2,R2h+2,… ）,… （ Rh,R2h,R3h,… ），
因为各组中记录之间的距离均为是 h，故第 1组至第 h组
的哨兵位置依次为 1-h,2-h,…, 0。如果象直接插入
排序算法那样，将待插入记录 Ri（ h+1≤i≤N） 在查找插
入位置之前保存到监视哨中，那么必须先计 Ri属于哪
一组，才能决定使用哪个监视哨来保存 Ri。为了避免
这种计算，我们可以将 Ri保存到另一个辅肋记录 X中，
而将所有监视哨 R1-h,R2-h,…, R0的关键字，设置为
小于文件中的任何关键字即可。因为增量是变化的，
所以，各趟排序中所需的监视哨数目也不相同，但是
我们可以按最大增量 d1来设置监视哨。
返回本章首页
下一页
上一页
rectype R[n+d1]； /* R[d1-1]为 d1个监视哨 */
int d[t]； /* d[0]到 d[t-1]为增量序列 */
SHELLSORT(R,d)
Rectype R[ ]；
int d[ ]；
{int i,j,k,h；
rectype temp;
int maxint=32767； /*机器中最大整数 */
for (i=0； i<d[0]； i++)
R[i].key=-maxint； /*设置哨兵 */
K=0；
Do{
H=d[k]； /*取本趟增量 */
For(i=h+di； i<n+d1； i++) /*R[h+d1]到 R[n+d1-1]插入当前有序区 */
{temp=R[i]}； /*保存待插入记录 R[i]*/
j=i-h；
while(temp.key<R[j].key) /*查找正确的插入位置 */
{R[j+h]=R[j]}； /*后移记录 */
j=j-h； /*得到前一记录位置 */
}
R[j+h]=temp； /*插入 R[i]*/
} /*本趟排序完成 */
k++；
} while (h！ =1)； /*增量为 1排序后终止算法 */
} /*SHELLSORT*/
返回本章首页
下一页
上一页
读者可能看出, 当增量 h=1时, SHELLSORT算法与 INSERTSORT基
本一致 。
对希尔排序的分析提出了许多困难的数学问题, 特别是如何选择增
量序列才能产生最好的排序效果, 至今没有得到解决 。 希尔本为
最初提出取 d1=┗ n/2┛, di+1=┗ di/2┛, dt=1,t=┗ log2n┛ 。 后来又
有人提出其它选择增量序列的方法, 如 di+1=┗ (di-1)/3┛, dt=1，
t=┗ log3n-1┛ ；以及 di+1=┗ (di-1)/2┛, dt=1,t=┗ log2n-1┛ 。
为什么希尔排序的时间性能优于直接插入排序呢？ 我们知道直接插
入排序在文件初态为正序时所需要时间最少, 实际上, 当文件初
基本有序时直接插入排序所需的比较和移动次数均较少 。 另一面,
当 n值较小时, n和 n2的差别也较小, 即直接插入排序的最好时间
复杂度 O(n)和最坏时间复杂度 O(n2)差别不大 。 在希尔排序时增量
较大, 分组较多, 每组的记录数目少, 故各组内直接插入较快,
后来增量 di逐渐缩小, 分组数逐渐减少, 而各组的记录数目逐渐
增多, 但由于已经按 di-1作为距离排过序, 使文件较近于有序状态,
所以新的国趟排序过程也较快 。 因此, 希尔排序在较率上较直接
接入排序有较大的改进 。
希尔排序是不稳定的。参见图 9-2的例子，该例中两个相同关键字 49
在排序前后的相对次序发生了变化。
返回本章首页
下一页
上一页
选择排序
选择排序 （ selection sort） 也是一种简单排序法 。 一个记录最多只需进行一
次交换就可以直接到达它的排序位置 。
设待排序的文件为 （ R1,R2,…, Rn）, 进行选择排序的基本步骤如下：
（ 1） 置 i 为 1；
（ 2） 当 i<n时, 重复下列步骤；
1） 当 (Ri,…, Rn)中选出一个关键字最小的记录 Rmin,若 Rmin不是 Ri,即
Rmin≠i则交换 Ri和 Rmin的位置；否则, 不进行交换 。
2） i的值加 1。
第 1遍扫描时, 在 n个记录中为了选出最小关键字的记录, 需要进行 n-1次比
较, 第 2扫描时, 在余下的 n-1记录中, 再选出具有最小关键字的记录需
要比较 n-2次, …… 第 n-1扫描时, 在最后的 2个记录中, 比较 1次选出最小
关键字的记录 。
返回本章首页
下一页
上一页
堆排序
堆排序 (heap sort)是在选择排序的基础上发展起来的 。 它
比选择排序的效率要高 。 在堆排序中, 把待排序的文
件逻辑上看作是一棵顺序二叉树, 并用到堆的概念 。
在介绍堆排序之前, 先引入堆的概念 。
我们回忆一下，一棵有 n个结点的顺序二叉树可以用一个
长度为 n的向量 (一维数组 )来表示；反过来，一个有 n个
记录的顺序表示的文件，在概念上可以看作是一棵有 n
个结点 (即记录 )的顺序二叉树。例如，一个顺序表示的
文件 (R1,R2,……, R9)，可以看作为图 9-4所示的顺
序二叉树。
返回本章首页
下一页
上一页
当我们把顺序表示的文件 (R1,R2,…, Rn)看作为顺序二叉树时, 由顺序二叉树的性质可知：记
录 Ri(1<i≤n)的双亲是记录 R[i 2]； R1的左孩子是记录 R2i(2i≤n),但若 2i>n,则 Ri的左孩子不存在；
Ri的右孩子是记录 R2i+1(2i+1≤n),但若 2i+1>n,则 Ri的右孩子不存在 。
什么是堆呢?堆是一个具有这样性质的顺序二叉树, 每个非终端结点 (记录 )的关键字大于等于它的
孩子结点的关键字 。 例如, 图 9-5所示的顺序二叉树就是一个堆 。
显然, 在一个堆中, 根结点具有最大值 (指关键字, 下同 ),而且堆中任何一个结点的非空左, 右子
树都是一个堆, 它的根结点到任一叶子的每条路径上的结点都是递减有序的 。
堆排序的基本思想是：首先把待排序的顺序表示 (一维数组 )的文件 (R1,R2,…, Rn)在概念上看作
一棵顺序二叉树, 并将它转换成一个堆 。 这时, 根结点具有最大值, 删去根结点, 然后将剩
下的结点重新调整为一个堆 。 反复进行下去, 直到只剩下一个结点为止 。
堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆 。 初始状态时, 结点是随机排列的, 需
要经过多次调整才能把它转换成一个堆, 这个堆叫做初始堆 。 建成堆之后, 交换根结点和堆
的最后一个结点的位置, 相当于删去了根结点 。 同时, 剩下的结点 (除原堆中的根结点 )又构成
一棵顺序二叉树 。 这时, 根结点的左, 右子树显然仍都是一个堆, 它们的根结点具有最大值
(除上面删去的原堆中的根结点 )。 把这样一棵左, 右子树均是堆的顺序二叉树调整为新堆, 是
很容易实现的 。
例如, 对于图 7-7所示的堆, 交换根结点 63和最后的结点 30之后, 便得到图 9-6(a)所示的顺序二叉
树 (除 63之外 )。 现在, 新的根结点是 30,其左, 右子树仍然都是堆 。 下面讨论如何把这棵二叉
树调整为一个新堆 。
由于堆的根结点应该是具有最大值的结点, 且已知左, 右子树是堆, 因此, 新堆的根结点应该是
这棵二叉树的根结点, 根结点的左孩子, 根结点的右孩子 (若存在的话 )中最大的那个结点 。 于
是, 先找出根结点的左, 右孩子, 比较它们的大小 。 将其中较大的孩子再与根结点比较大小 。
如果这个孩子大于根结点, 则将这个孩子上移到根结点的位置, 而根结点下沉到这个孩子的
位置, 即交换它们的位置 。 在图 9-6(a)中, 根结点 30的左, 右孩子分别是 60,59,由于 60>59，
并且 60>30,于是应交换根结点 30和左孩子 60的位置 。
这时，新的根结点 60的右子树没有改变，仍然是一个堆。但是，由于结点 30下沉到左子树的根上，
使得左子树有可能不再是堆了。按照上面所用的办法，把这棵子树调整为一个堆，显然，结
点 30的左、右子树原来都是堆,30的左、右子树分别是 40,45。由于 40<45，并且 45>30，于
是应交换结点 30和右孩子 45的位置。
返回本章首页
下一页
上一页
void adjust(struct node r[m+1],int m)
/* 将文件 (r[1],r[2],…,r[m])解释为一棵顺序二叉树,将其中以 r[i]为根结点的二叉树调
整
为一个堆,设以 r[i]为根的二叉树的左,右子树已是堆,1≤i≤1[m/2] */
{ x=r[i];j=2*i;
/*求出 r[i]的左孩子 r[2*i],即 r[j] */
while (j<=m) /*有左孩子 */
{ if ((j<m) &&(r[j].key<r[j+1].key)) /*比较左, 右孩子 */
j=j+1; /*左孩子 <右孩子 */
if (x.key<r[j].key) /*比较根结点和它的大孩子 */
{ r[i]=r[j]; /*大孩子上移到它的双亲位置 */
i=j; /*今 r[j]为根结点 */
j=2*i; /*求出左孩子 */
}
else j=m+1 /*根不小于它的任一孩子时, 强迫退出 while
循环 */
}
r[i]:=x; /*将存放在 x
中的根结点放到 r[i]中 */
}
返回本章首页
下一页
上一页
快速排序
快速排序 (Quick Sort)称划分交换排序。其基本思
想是：在当前无序区 R[1]到 R[h]到中任取一个
记录作为比较的“基准”（不妨记为 temp），
用此基准将当前无序区划分为左右两个较小的
无序子区,R[1]到 R[i-1]和 R[i+1]到 R[h]，且左
边的无序子区中记录的关键字均小于或等于基
准 temp的关键字，右边的无序子区中记录的关
键字均大于或等于基准 temp的关键字，而基准
temp则位于最终排序的位置上
返回本章首页
下一页
上一页
R[1]到 R[i-1]中关键字 ≤temp.key=R[i+1]到 R[h]的关键字 （ 1≤i≤h）
当 R[1]到 R[I-1]和 R[I+1]到 R[h]均非空时, 分别对它们进行上述的划
分过程, 直至所有无序子区中记录均已排好序为止 。
要完成对当前无序区 R[1]到 R[h]的划分，具体做法是：设置两个指针
i和 j，它们的初值分别为 i=1和 j=h。不妨取基准为无序区的第 1个
记录 R[i]（即 R[1]），并将它保存在变量 temp中。令 j自 h起向左扫
描，直到找到第 1个关键字小于 temp.key的记录 R[j]，将 R[j]移至 i
所指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）的位置，
使关键字小于基准关键字的记录移到了基准的左边）；然后，令 i
自 i+1起向右扫描，直至找到第 1个关键字大于 temp.key的记录 R[i]，
将 R[i]移至 j指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）
的位置，使关键字大于基准关键字的记录移到了基准的右边）；
接着，令 j自 j+1起向右扫描，如此交替改变扫描方向，从两端各
自往中间靠拢，直至 i=j时,i便是基准 x的最终位置，将 x放在此位
置 上就完成了一次划分。
返回本章首页
下一页
上一页
综合上面的叙述, 下面分别给出一次划分及其排序的算法 。
int partition(r,1,h) /*返回划分后被定们的基准记录的位置 */
rectype R[ ]; /*对无序区 R[1]到 R[h]做划分 */
int 1,h;
{int i,j;
rectype temp;
i=1;j=h temp=R[i]; /*初始化, temp为基准 */
Do{
While((R[j].key>=temp.key) && (i<j))
j--; /*从右向左扫描, 查找第 1个关键字小于 temp.key的记录 */
if(i<j) R[i++]=R[j]; /*交换 R[i]和 R[j]*/
while((R[i].key<=temp.key) && (i<j))
i++; /*从左向左扫描, 查找第 1个关键字大于
temp.key的记录 */
if(i<j) R[j--]=R[i]; /*交换 R[i]和 R[j]*/
}
quicksort(R,s1,t1) /*对 R[s1]到 R[t1]*/
rectype R[ ];
int s1,t1;
{int i;
if (s1<t1) /* 只有一个记录或无记录须排序 */
{i= partition (R,s1,t1); /*对 R[s1]到 R[t1]做划分 */
quicksort (R,s1,i-1); /*递归处理左区间 */
quicksort (R,i+1,t1); /*递归处理右区间 */
}
}
返回本章首页
下一页
上一页
图 9-7展示了一次划分的过程及整个快速排序的过程 。 图中方括号表示无序区, 方框表示基准 temp的关键字, 它未
参加真正的交换, 只是在划分完成时才将它放入正确的位置上 。
初始关键字 [[49 ] 38 65 97 76 13 27 49`]
i j
j向左扫描 [[49] 38 65 97 76 13 27 49 `]
i j
第一次交换后 [27 38 65 97 76 13 [ ] 49`]
i j
i向右扫描 [27 38 65 97 76 13 [ ] 49 `]
i j
第二次交换后 [27 38 [ ] 97 76 13 65 49 `]
i j
j向左扫描, 位置不变
第三次交换后 [27 38 13 97 76 [ ] 65 49]`]
i向左扫描, 位置不变, i j
第四次交换后 [27 38 13 [ ] 76 97 65 49 `]
i j
j向左扫描 [27 38 13 [49] 76 97 65 49 `]
i j
返回本章首页
下一页
上一页
初始关键字,[49 38 65 97 76 13 27 49`]
一趟排序之后,[27 38 13] 49 [76 97 65 49`]
二趟排序之后,[13] 27 [38] 49 [49` 65] 76 [97]
三趟排序之后,13 27 38 49 49` [65] 76 97
最后的排序结果,13 27 38 79 79` 65 76 97
(b) 各趟排序之后的状态
返回本章首页
下一页
上一页
最坏情况是第次划分选取的基准都是当前无序区中关键字最小 （ 或
最大 ） 的记录, 划分的基准左边的无序子区为空 （ 或右边的无序
子区为空 ）, 而划分所得的另一个非空的无序子区中记录数目,
仅仅比划分前的无序区中记录个数减少一个 。 因此, 快速排序必
须做 n-1趟, 每一趟中需进行 n-i次比较, 故总手工艺比数次数达到
最大值：
Cmax=∑ (n-i)=n(n-1)/2=O(n2)
显然, 如果按上面给出的划分算法, 每次取当前无序区的第 1个记录
为基准, 那么当文件的记录已按递增序 （ 或递减序 ） 排列时, 每
次划分所取的基准就是当前无序区中关键字最小 （ 或最大 ） 的记
录, 则快速排序所需的比较次数反而最多 。
在最好情况下, 每次划分所取的基准都是当前无序区的, 中值, 记
录, 划分的结果是基准的左, 右两个无序子区的长度大致相等地 。
设 C（ n） 表示对长度为 n的文件进行快速排序所需的比较次数,
显然, 它应该等于对长度为 n的无序区进行划分所需的比较次数 n-
1。 加上递归地对划分所得的左, 右两个无序子区 （ 长度 ≤n/2） 进
行快速排序所需的比较总人
数。
返回本章首页
下一页
上一页
假设文件长度 n=2k,那么总的比较次数为：
C(n) ≤n+2C(n/2)
≤n+2[n/2+2C(n/22)]=2n+4C(n/22)
≤2n+4[n/4+2C(n/23)]=3n+8C(n/23)
≤……
≤kn+2kC(n/2k)=nlog2n+nC(1)
=O(nlog2n)
注意：式中 C（ 1）为一常数,k=log2n。,
返回本章首页
下一页
上一页
因为快速排序的记录移动次数不大于比较的次数, 所以,
快速排序的最坏时间复杂度应为 O（ n2）, 最好时间复
杂雅兴 O(log2n)。 为了改善最坏情况下的时间性能, 可
采用三者取中的规则, 即在每一趟划分开始前, 首先
比较 R[1].key,R[h].key和 R[[(1+h)/2]].key,令三者中取
中值的记录和 R[1]交换之 。
可以证明：快速排序的平均时间复杂度也是 O(nlog2n)，
它是目前基于比较的内部排序方法 中速度最快的, 快
速排序亦因此而得名 。
快速排序需要一个栈空间来实现递归 。 若每次划分均能
将文件均 匀分割 为两 部分, 则栈的 最大深 度为
[log2n]+1,所需栈空间为 O（ log2n） 。 最坏情况下, 递
归深度为 n,所需栈空间为 O（ n)。
快速排序是不稳定的，请读者自行检验。
返回本章首页
下一页
上一页
归并排序
归并排序 (Merge Sort)是利用“归并”技术来进行排序，
所谓归并是指将若干个已排序的子文件合并成一个有
序的文件。简单的归并是将两个有序的子文件合并成
一个有序的文件。假设 R(low)到 R[m]和 R[m+1]到
R[high]是存储在同一个数组中且相邻的两个有序的子
文件，要将它们合并为一个有序文件 R1[low]到 R1[high]，
只要设置三个指示器 i,j和 k，其初值分别是这三个记
录区的起始位置。合并时依次比较 R[i]和 R[j]的关键字，
取关键字较小的记录复制到 R1[k]中，然后，将指向被
复制记录的指示器加 1和指向复制位置的指示器 K加 1，
重复这一过程，直至全部记录被复制到 R1[low]到
R1[high]中为止。
返回本章首页
下一页
上一页
基数排序
前介绍的排序方法都是根据关键字值的大小来进行排序的 。 本节介绍的方法是按组成
关键字的各个位的值来实现的排序的, 这种方法称为基数排序 （ radix sort） 。 采
用基数排序法需要使用一批桶 （ 或箱子 ）, 故这种方法又称为桶排序列 。 下面以
十进制数为例来说明基数排充的过程 。
假定待排序文件中所有记录的关键字为不超过 d位的非负整数, 从最高位到最低位
（ 个位 ） 的编号依次为 1,2,…, d。 设置 10个队列 （ 即上面所说的桶 ）, 它们的
编号分别为 0,1,2,…, 9。 当第一遍扫描文字时, 将记录按关键字的个位 （ 即
第 d位）数分别放到相应的队列中：个位数为 0的关键字，其记录依次放入 0号队列中 i
个位数为 1的关键字，其记录放入 1号队列中 … ；个位数为 9的关键字，其记录放入
9号队列中。这一过程叫做按个位数分配。现在把这 10个队列中的记录，按 0号,1
号,9号队列的顺序收集和排列起来，同一队列中的记录按先进先出的次序排列。
这是第 1遍。第 2遍排序使用同样的办法，将第 1遍排序后的记录按其关键字的十位
数（第 d— 1位）分配到相应的队列中，再把队列中的记录收集和排列起来。继续
进行下去。第 d遍排序时，按第 d— 1遍排序后记录的关键字的最高位（第 1位）进
行分配，再收集和排列各队列中的记录，医得到了原文件的有序文件，这就是以
10为基的关键字的基数排序法。
返回本章首页
下一页
上一页
关键字
1 02
2 77
3 70
4 54
5 64
6 21
7 55
8 11
9 38
1 0 21
初始状态
70
21,1 1,2 1
02
5 4,6 4
55
77
38
70
21
11
21
02
54
64
55
77
38
02
11
2 1,2 1
38
54,55
64
7 0,7 7
02
11
21
21
38
54
55
64
70
77
10 个队列 关键字
第一遍，按个
位数分配
收集后 收集后
第二遍，按十
位数分配
返回本章首页
下一页
上一页
例如, 给出关键字序列 （ 02,77,70,54,64,21,55,11,38,21）, 其
中关键字 02用 1个 0在 2的前面补足到 2位, 余关键字均为 2位的正整数 。 进
行基数排序的过程如图 9-9所示 。
在这个例子中, 文件和所有的队列都表示成向量 （ 一维数组 ） 。 显然, 关键
字的某一位有可能均为同一个数字 （ 例如, 个数都为 0）, 这时所有的记
录都同时装入同一个队列中 （ 例如, 同时装入 0号队列中 ） 。 因此, 如果
每个队列的大小和文件大小相同, 则需要一个 10倍于文件大小的附加空
间 。 此外, 排序时需要进行反复的分配和收集记录 。 所以, 采用顺序表
示是不方便的 。
基数排序所需的计算时间不仅与文件的大小 n有关，而且还与关键字的位数、
关键字的基有关。设关键字的基为 r（十进制数的基为 10，二进制数的基
为 2），为建立 r个空队列所需的时间为 O（ r）。把 n个记录分放到各个队
列中并重新收集起来所需的时间为 O（ n），因此一遍排序所需的时间为
O（ n+r）。若每个关键字有 d位，则总共要进行 d遍排，所以基数排序的
时间复杂度为 O（ d（ n+r））。由于关键字的位数 d直接与基数 r以及最大
关键字的值有关，因此不同的 r和关键字将需要不同的时间。
返回本章首页
下一页
上一页
在已介绍的上述各种内部排序方法中，就所需要
的计算时间来看，快速排序、归并排序、堆排
序是很好的方法。但是，归并排序需要大小为
n的辅助空间，快速排序需要一个栈空。除了
快速排序、堆排序、选择排序不稳定外，基它
排序方法都是稳定的。评价一个排序算法性能
好坏的主要标准是它所需的计算时间和存储空
间。影响计算时间的两个景要因素是比较关键
字的次数和记录的移动次数。在实际应用中，
究竟应该选用何种排序方法，取决于具体的应
用和机器条件。
返回本章首页
下一页
上一页
外部排序
外部排序基本上由两个相对独立的阶段组成 。 首先, 按可用内存大
小, 将外存上含 n个记录的文件分成若干长度为 l的子文件或段
（ segment）, 依次读入内存并利用有效的内部排序方法对它们进
行排序, 并将排序后得到的有序子文件重新写入外存, 通常称这
些有序子文件为归并段或顺串 （ run） ；然后, 对这些归并段进行
逐趟归并, 使归并段 （ 有序的子文件 ） 逐渐由小至大, 直至得到
整个有序文件为止 。 显然, 第一阶段的工作是上一章已经讨论过
的内容 。 本章主要讨论第二阶段即归并的过程 。 先从一个具体例
子来看外排中的归并是如何进行的？
假设有一个含 10000个记录的文件，首先通过 10次内部排序得到 10个
初始归并段 R1~R10，其中每一段都含 1000个记录。然后对它们作
如下图所示的两两归并，直至得到一个有序文件为止。
返回本章首页
下一页
上一页
将两个有序段归并成一个有序段的过程, 若在内存进行, 则很简单,
上一章中的 merge过程便可实现此归并 。 但是, 在外部排序中实现
两两归并时, 不仅要调用 merge过程, 而且要进行外存的读 /写,
这是由于我们不可能将两个有序段及归并结果段同时存放在内存
中的缘故 。 在 11.1节中已经提到, 对外存上信息的读 /写是以, 物
理块, 为单位的 。 假设在上例中每个物理块可以容纳 200个记录,
则每一趟归并需进行 50次, 读, 和 50次, 写,, 四趟归并加上内
部排序时所需进行的读 /写使得在外排中总共需进行 500次的读 /写 。
一般情况下, 外部排序所需总的时间 =
内部排序 （ 产生初始归并段 ） 所需的时间 m*tIS
+外部信息读写的时间 d*tIO （ 11-1）
+内部归并所需的时间 s*utmg
其中,tIS是为得到一个初始归并段进行内部排序所需时间的均值；
tIO是进行一次外存读 /写时间的均值； utmg是对 u个记录进行内部
归并所需时间； m为经过内部排序之后得到的初始归并段的个数；
s为归并的趟数； d为总的读 /写次数。
返回本章首页
下一页
上一页
其中 tIO取决于所用的外部设备, 显然, tIO较 tmg要大得多 。 因此, 提高外
排的效率应主要着眼于减少外存信息读写的次数 d。
下面来分析 d和, 归并过程, 的关系 。 若对上例中所得的 10个初始归并段进
行 5-路平衡归并 （ 即每一趟将 5个或 5个以下的有序子文件归并成一个有
序子文件 ）, 则从下图可见, 仅需进行二趟归并, 外排时总的读 /写次数
便减至 2*100+100=300,比 2-路归并减少了 200次的读 /写 。
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
└──┴──┼──┴───┘ └──┴──┼──┴───┘
R1ˊ R2ˊ
└───────┬──────┘
有序文件
可见, 对同一文件而言, 进行外排时所需读 /写外存的次数和归并的趟数 s成
正比 。 而在一般情况下, 对 m个初始归并段进行 k-路平衡归并时, 归并的
趟数
s = [ logkm ]
可见，若增加 k或减少 m便能减少 s。
返回本章首页
下一页
上一页
各种排序方法的比较
迄今为止, 已有的排序方法远远不止本章讨论的这些方法, 人们之所以热衷于研究多种排序方法, 不仅是由于排序在计算机中所处的重
要地位, 而且还因为不同的方法各有其优缺点, 可适用于不同的场合 。 选取排序方法时需要考虑的因素有：
待排序的记录数目 n；记录本身信息量的大小；关键字的结构及分布情况；对排序稳定性的要求；语言工具的条件, 辅助空间的大小等 。
依据这些因素, 可得出如下几点结论：
（ 1） 若 n较小 （ 譬如 n50),可采用直接插入排序或直接选 。 由于直接插入排序所需记录移动操作较直接选择排序多, 因此若记录本身信
息量较大时, 则选用直接选择排序为宜 。
（ 2） 若文件的初始状态已是按关键字基本有序, 则选用直接插入排序泡排序为宜 。
（ 3） 若 N较大, 则应采用时间复杂度为的排序方法：快速排序 \堆排序或归并排序, 快速排序是目前基于内部排序的中被认为是最好的方
法, 档待排序的关键字是随机人布时, 快速排序的平均时间最少, 但堆排序所需的辅助窨少于快速排序, 并且不会出现序可能出现
的最坏情况, 这两种排序方法都是不稳定的, 若要求排序稳定则可选用归并排序 。 但本文章结合介绍的单个记录起进行两两归并排
算法并不值得提倡, 通常可以将它和直接排序结合在一起用 。 先利用直接插入排序求得的子文件, 然后, 再两 两 归并之 。 因为直
接插入排序是稳定的, 所以, 改进后的归并排序是稳定的 。
（ 4） 在基于比较的排序方法中, 每次比较两个关键字的大小之后, 仅仅出现两种可能的转移, 因此, 可以利用一棵二叉树来描述比较判
定过程, 由此可以证明 ;当文件的 N个关键字分布时, 任何借助于比较的排序算法, 至少要的时间, 由于箱排序和基数排序只需一步
就会引起 M种可能的转移, 即把一个记录半装入 M个箱子之一, 因此, 在一般情况下, 箱乔序和排序可能在时间内完成对 N个记录
的 。 但踞的是, 箱排序和排序只适用于象字符串和整数这类有明显的结构特征的关键字, 当关键字的取值范围属于某个无穷集合时,
无法使用箱排序和排序, 这时只有借助于比较方法来排序 。 由此可知, 若 N较大, 记录的关键字倍数较少时且可以分解时采用排序
较好 。
（ 5） 前面讨论的排序算法, 除排序外, 都是在一维数组上实现的, 当记录本身信息量较大时, 为了避免浪费大量时间移动记录, 可以用
链表作为存储结构, 如插入排序和归并排序都易于在链表上实现, 并分别称之为表和归并表, 但有的方法, 如快速排序和堆排序,
在链表上难于实现, 在这种情况下, 可以提取关键字建立索引表, 然后, 对索引表进行排序 。 然而更为简单的方法是 ;引入一个整
形向量作为辅助表, 排序前, 若排序算法中要求交换, 则只需交换 R[I]和 R[j]即可, 排序结束后, 向量就指示了记录之间的顺序关
系：
无论是用链表还是用辅助窨来实现排序, 都有可能要求最终结果是,
若上述要求，则可以在排序结束后，再按链表或辅助窨表所规定的次序重排各记录，完成这种 重排时间是 o(n)。
下一页
上一页
第九章查找与排序
顺序查找是一种最基本和最简单的查找方法。它
的思路是，从表中的第一个元素开始，将给定
的值与表中逐个元素的关键字进行比较，直到
两者相符，查到所要找的元素为止。否则就是
表中没有要找的元素，查找不成功。对于表中
记录的关键字是无序的表，只能采用这种方法。
描述顺序查找的算法见框图 8-1。其中 n是表 r的
长度,k是要查的元素的关键字,i查到的元素
的序号。
上一章
下一章
返回目录
返回本章首页
下一页
上一页
折半查找又称二分查找, 是针对有序表进行查找的简单,
有效而又较常用的方法 。 所谓 有序表, 即要求表中的
各元素按关键字的值有序 （ 升序或降序 ） 存放 。
折半查找不像顺序查找那样, 从第一个记录开始逐个顺
序搜索, 其基本思想是：首先选取表中间位置的记录,
将其关键字与给定关键字 k进行比较, 若相等, 则查找
成功；否则, 若 k值比该关键字值大, 则要找的元素一
定在表的后半部分 （ 或称右子表 ）, 则继续对右子表
进行折半查找；若 k值比该关键字值小, 则要找的元素
一定在表的前半部分 （ 左子表 ）, 同样应继续对左子
表进行折半查找 。 每进行一次比较, 要么找到要查找
的元素, 要么将查找的范围缩小一半 。 如此递推, 直
到查找成功或把要查找的范围缩小为空 （ 查找失败 ） 。
设表的长度为 n，表的被查找部分的头为 low，尾为 high，
初始时,low=1,high=n,k为关键字的值。
返回本章首页
下一页
上一页
（ 2） 若 k=r[mid].key,成功, 否则：
若 k<r[mid].key,则 high=mid― 1,重复 （ 1） ；
若 k>r[mid].key,则 low=mid+1,重复 （ 1） ；
直到成功或不成功 （ 此时 low>high） 。
具体算法如下：
Void binsrch(struct node r[ ],int n,int k)
{ int mid,low,high,find;
low=1; high=n;find=0; /*置区间初值 */
while ((low<=high) && (!find))
{ mid=(low+high)/2; /*求中点 */
if (k= = r[mid].key)
find=1; /*已查到 */
else if(k>r[mid].key )
low=mid+1; /*在后半区间查找 */
else high=mid-1; /*在前半区间查找 */
}
if (find)
return (mid); /*查找成功, 返回找到元素的位置 */
else return (0); /*查找不成功, 返回 0标记 */
}
返回本章首页
下一页
上一页
采用折半查找, 当查找成功时, 最少比较次数为
一次, 如在上例中查找关键字值为 18的结点,
只需一次比较 。 最多经过 log2n次比较之后, 待
查找子表要么为空, 要么只剩下一个结点, 所
以要确定查找失败需要 log2n次或 log2n+1次比
较 。 可以证明, 折半查找的平均查找长度是：
从折半查找的平均查找长度 ASL来看，当表的长
度 n很大时，该方法尤其能显示出其时间效率。
但由于折半查找的表仍是线性表，若经常要进
行插入、删除操作，则元素排列费时太多，因
此折半查找比较适合于一经建立就很少改动而
又需要经常查找的线性表，较少查找而又经常
需要改动的线性表可以采用链接存储，使用顺
序查找。
返回本章首页
下一页
上一页
分块查找
在处理线性表时, 如果既希望能够快速查找, 又要经常
动态变化, 则可以采用分块查找方法 。 分块查找又称
索引顺序查找, 要求将待查的元素均匀的分成块, 块
间按大小排序, 块内不排序 。 因此需要建立一个块的
最大 （ 或最小 ） 关键字表, 称之为, 索引表, 。
具体而言，假设我们按结点元素关键字升序方式组织表
中各块，则要求第一块中任一结点的关键字值都小于
第二块中所有结点的关键字值；第二块中任一结点的
关键字值都小于第三块中所有结点的关键字值；如此
类推。然后选择每块中的最大（或最小）关键字值组
成索引表。换言之，索引表中的结点个数等于线性表
被分割的块数。
返回本章首页
下一页
上一页
例如要找关键字为 k的元素, 则先用折半查找法由索引表查出 k所在的块, 再
用顺序查找法在对应的块中找出 k。 在图 8-2中若要找关键字值为 41的元
素, 则先由索引表查出 41在第二块中 （ 29<41<64）, 再在第二块中找到
41。
由此我们可以总结：分块查找分两步进行, 第一步确定要查找结点在表中的
哪一块, 第二步在确定的块中找到该结点 。
分块查找的平均查找长度为：
ASL=ASLb+ASLe
其中 ASLb是折半查找的平均查找长度, ASLe是用顺序查找法查块内元素的
平均查找长度 。 设每块中有 s个元素, 可以近似的得到：
可以看出分块查找的平均查找长度位于顺序查找和折半查找之间 。
下面我们简单的对以上几种查找方法做出比较：
（ 1） 平均查找长度：折半查找最小, 分块查找次之, 顺序查找最大；
（ 2） 表的结构：顺序查找对有序表, 无序表均适用；折半查找仅适用于有
序表；分块查找要求表中元素是逐段有序的, 就是块与块之间的记录按
关键字有序；
（ 3）存储结构：顺序查找和分块查找对向量和线性链表结构均适用；折半
查找只适用于向量存储结构的表，因而要求表中元素基本不变，而在需
要插入或删除运算时，要移动元素，才能保持表的有序性，所以影响了
查找效率。
返回本章首页
下一页
上一页
哈希法
哈希法又名散列法,因其英文单词 Hash而得名,是一种完全不同的查找方法 。
前面我们所介绍的三种查找方法的共同特点在于：通过对关键字的一系
列比较, 逐步缩小查找范围, 直到确定结点的存储位置或确定查找失败 。
而哈希法则希望不经过任何比较, 一次存取就能得到所查元素, 因此必
须在记录的存储位置和它的关键字之间建立一个确定的对应关系, 使得
每个关键字和结构中一个唯一的存储位置相对应, 这样查找时只需对结
点的关键字进行某种运算就能确定结点在表中的位置 。 因此哈希法的平
均比较次数和表中所含结点的个数无关 。
打个比方让我们更清楚的认识哈希法的不同。假定某教室有 35个座位，如果
不加限定让学生任意就座，则要找某个学生时就要将待找学生与当前座
位上的学生一一做比较，这就是我们前面所介绍的查找方法的大致思路。
而哈希法则要限定学生所坐的位置，比如可规定学生座位的编号应与其
学号的末两位相同，则学号为 993605的学生应坐编号为 5的座位。这样我
们要找某个学生时只需根据其学号的末两位到相应座位上去找即可，不
必一一比较了。在这个例子里，学生好比记录，学号则为关键字，对关
键字进行的操作则是取其末两位，用以确定记录的位置。
返回本章首页
下一页
上一页
哈希函数的构造方法
一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内, 以尽可能减
少冲突 。 但鉴于实际问题中关键字的不同, 没法构造出统一的哈希函数 。 从而构
造哈希函数的方法多种多样, 这里只介绍一些比较常用的, 计算较为简便的方法 。
1,自身函数
关键字自身作为哈希函数, 即 H（ k） =k,也可自身加上一个常数作为哈希函数, 即
H(k)=k+c。 例如上例中建立的哈希函数 H(学号 )=学号 -9900采用的就是这样的方法 。
但这种函数只适用于给定的一组关键字为关键字集合中的全体元素的情况, 故不
常用 。
2,除余法
选择一个适当的正整数 m,用 m去除关键字, 取其余数作为散列地址, 即 H（ key）
=key%m。 上例中后来所设定的函数 H(学号 )=学号 %10采用的就是除余法 。
但是在这种方法中, m的选择是值得研究的 。 如果选择关键字内部代码基数的幂次来
除关键字, 其结果必定是关键字的低位数字均匀性较差 。 若取 m为任意偶数, 则
当关键字内部代码为偶数时, 得到的哈希函数值为偶数；若关键字内部代码为奇
数, 则哈希函数值为奇数 。 因此, m为偶数也是不好的 。 理论分析和试验结果均
证明 m应取小于存储区容量的素数 。
返回本章首页
下一页
上一页
查找,根据给定的某个值, 在表中确定一个关键字等于给定值的记录或数据
元素 。
关键字 (Keyword)：一个或一组能唯一标识该记录的数据项称为该记录的关
键字 。
平均查找长度 （ Average Search Length）,为确定记录在表中的位置所进行
的和关键字的比较的次数的期望值称之为查找算法的平均查找长度, 简
称 ASL。
有序表,表中的各元素按关键字的值有序 （ 升序或降序 ） 存放 。
哈希表,将结点的关键字 key作为自变量, 通过一个确定的函数关系 H,计算
出相应的函数值 H(key),然后以 H(key)作为该结点的存储单元地址 。 用这
种方式建立起来的线性表称为哈希表或叫散列表
哈希函数,把结点关键字转换为该结点存储单元地址的函数 H称为哈希函数
或叫散列函数 。
在学习这些概念的基础上，我们先后学习了三种基于将待查元素的关键字和
表中元素的关键字进行比较的查找算法，即顺序查找、折半查找和分块
查找，并对它们做出比较。我们也学习了一种不同的查找算法，即哈希
法，它的基本思路是：在记录的存储位置和它的关键字之间建立一个确
定的对应关系，使得每个关键字和结构中一个唯一的存储位置相对应，
这样查找时只需对结点的关键字进行某种运算就能确定结点在表中的位
置，其间我们知道了如何构造哈希函数和如何解决冲突问题。读者应熟
悉各种查找算法的思路、算法及性能分析，以灵活应用于各种实际问题
中。
返回本章首页
下一页
上一页
排序
排序 （ sorting） 是计算机程序设计中的一种重要操作, 它
的功能是将一个数据元素 （ 或记录 ） 的任意序列, 重
新排列成一个按关键字有序的序列 。
由于待排序的记录数量不同，使得排序过程中涉及的存
储器不同，可将排序方法分为两大类：一类是内部排
序，指的是待排序记录存放在计算机存储器中进行的
排序过程；另一类是外部排序，指的是待排序记录的
数量很大，以致内存一次不能容纳全部记录，在排序
过程中对外存进行访问的排序过程。
返回本章首页
下一页
上一页
插入排序
线性插入排序的基本思想是：第 1遍，将初始文
件中的记录 R1看作有序子文件，将 R2插入这个
子文件中。若 R2的关键字小于 R1的关键字，则
R2插在 R1的前面，否则 R2插在 R1的后面。第 2
遍，将 R3插入前面的两个记录的有序子文件中，
得到 3个记录的有序子文件。依此类推，继续
进行下去，直到将 Rn插入到前面的 n-1个记录的
有序子文件中，最后得到 n个记录的有序文件。
返回本章首页
下一页
上一页
线性插入排序的基本思想是：第 1遍, 将
初始文件中的记录 R1看作有序子文件,
将 R2插入这个子文件中 。 若 R2的关键
字小于 R1的关键字, 则 R2插在 R1的前
面, 否则 R2插在 R1的后面 。 第 2遍,
将 R3插入前面的两个记录的有序子文
件中, 得到 3个记录的有序子文件 。
依此类推, 继续进行下去, 直到将 Rn
插入到前面的 n-1个记录的有序子文
件中, 最后得到 n个记录的有序文件 。
图 9-1所示为线性插入排序的例子 。
为了避免检测是否应插在 R1的前面，在
R1的前面设立记录 R0，它既是中间变
量，又是监视哨。设（ R1,R2,…,
Ri-1）是已排序的有序子文件，则插
入 Ri的步骤是：首先将 Ri存放到 Ro中，
然后将 Ko（即原 Ri的关键字 Ki）依
次与 Ki-1,Ki-2,… 比较，若 Ko<Kj
（ j=i-1,i-2,…, 1），则 Rj后移一
个位置，否则停止比较和移动；最后，
将 Ro（即原来待插入的记录 Ri）移到
j+1的位置上。由于 Ri的前面有监视
哨 Ro，因此不必每次判断下标 j是否
出界。算法描述如下：
返回本章首页
下一页
上一页
void insertsort(struct node r[ n+1],int n)
/* r[n+1]为一维数组, 其中 r[0]为监视哨, r[1]到 r[n]为待
排序的 n个记录, 排序好的记录仍放在 r中 */
{ for(i=2;i<=n;i++) /*共进行 n-1趟 */
{ r[0]=r[i]; /*r[0]为监视哨, 也可
做下边循环结束标志 */
j=i-1;
while(r[j].key>r[0].key)
{ r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
}
返回本章首页
下一页
上一页
折半插入排序
在线性插入排序中, 我们采用顺序查找法来确定记录的插入位置 。 由于 （ R1,R2,…, Ri-1） 是有
序子文件, 我们可以采用折半查找法来确定 R1的插入位置, 这种排序称为折半插入排序 。 其
算法可写出如下：
void binarysort(struct node r[ n+1],int n)
/*按关键字递增的次序对记录 r[1],r[2],……,r[n]进行折半插入排序 */
{ for(i=2;i<=n;i++)
{ r[0]=r[i];
l=1;
h=i-1;
while(l<=h)
{ mid=(l+h)/2;
if(r[0].key<r[mid].key)
h=mid-1;
else l=mid+1;
}
for(j=i-1;j>=l;j--)
r[j+1]=r[j];
r[l]=r[0];
}
}
在上面的算法中，每插入一个 R1，平均比较次数为 log2i。
返回本章首页
下一页
上一页
希尔排序
希尔排序 （ Shell’s Method） 又称, 缩小增量排序, （ Diminishing Increment Sort）,
是由 D.L.Shell在 1959年提出来的 。 它的作法是：先取定一个小于 n的整数 d1作为第
一个增量, 把文件的全部记录分成 d1个组, 所有距离为 d1的倍数的记录放在同一
个组中, 在各组内进行直接插入排序；然后, 到第二个增量 d2<d1重复上述分组和
排序, 直至所取的增量 dt=1（ dt<dt-1<… <d2<d1）, 即所有记录放在同一组中进行
直接插入排序为止 。
先从一个具体的例子来看希尔排序 。 假设待排序文件有 10个记录, 其关键字分别是：
49,38,65,97,76,13,27,49/,55,04。 增量序列取值依次为,5,3,1。
第一趟排序时, d1=5,整个文件被分成 5组,（ R1,R6）, （ R2,R7）, …, （ R5，
R10） 各组中的第 1个记录都自成一个有序区, 我们依次将各组的第 2个记录 R6，
R7,… R10分别插入到各组的有序区中, 使文件的各组均是有序的, 其结果见图 9-
2的第七行 。
第二趟排序时, d2=3,整个文件分成三组,（ R1,R4,R7,R10）, （ R2,R5,R8）,
（ R3,R6,R9）, 各组的第 1个记录仍自成一个有序区, 然后依次将各组的第 2个
记录 R4,R5,R6分别插入到该组的当前有序区中, 使得 （ R1,R4）, （ R2,R5）,
（ R3,R6） 均变为新的有序区, 接着依次将各组的第 3个记录 R7,R8,R9分别插
入到该组当前的有序区中, 又使得 （ R1,R4,R7）, （ R2,R5,R8）, （ R3,R6，
R9） 均变为新的有序区, 最后将 R10插入到有序区 （ R1,R4,R7） 中就得到第二
趟排序结果 。
最后一趟排序时,d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。
返回本章首页
下一页
上一页
若不设置监视哨，根据上例的分析不难写出希尔排序算
法，请读者自行完成之。下面我们先分析如何设置监
视哨，然后给出具体算法。设某一趟希尔排序的增量
为 h，则整个文件被分成 h组：（ R1,Rh+1,R2h+1,… ），
（ R2,Rh+2,R2h+2,… ）,… （ Rh,R2h,R3h,… ），
因为各组中记录之间的距离均为是 h，故第 1组至第 h组
的哨兵位置依次为 1-h,2-h,…, 0。如果象直接插入
排序算法那样，将待插入记录 Ri（ h+1≤i≤N） 在查找插
入位置之前保存到监视哨中，那么必须先计 Ri属于哪
一组，才能决定使用哪个监视哨来保存 Ri。为了避免
这种计算，我们可以将 Ri保存到另一个辅肋记录 X中，
而将所有监视哨 R1-h,R2-h,…, R0的关键字，设置为
小于文件中的任何关键字即可。因为增量是变化的，
所以，各趟排序中所需的监视哨数目也不相同，但是
我们可以按最大增量 d1来设置监视哨。
返回本章首页
下一页
上一页
rectype R[n+d1]； /* R[d1-1]为 d1个监视哨 */
int d[t]； /* d[0]到 d[t-1]为增量序列 */
SHELLSORT(R,d)
Rectype R[ ]；
int d[ ]；
{int i,j,k,h；
rectype temp;
int maxint=32767； /*机器中最大整数 */
for (i=0； i<d[0]； i++)
R[i].key=-maxint； /*设置哨兵 */
K=0；
Do{
H=d[k]； /*取本趟增量 */
For(i=h+di； i<n+d1； i++) /*R[h+d1]到 R[n+d1-1]插入当前有序区 */
{temp=R[i]}； /*保存待插入记录 R[i]*/
j=i-h；
while(temp.key<R[j].key) /*查找正确的插入位置 */
{R[j+h]=R[j]}； /*后移记录 */
j=j-h； /*得到前一记录位置 */
}
R[j+h]=temp； /*插入 R[i]*/
} /*本趟排序完成 */
k++；
} while (h！ =1)； /*增量为 1排序后终止算法 */
} /*SHELLSORT*/
返回本章首页
下一页
上一页
读者可能看出, 当增量 h=1时, SHELLSORT算法与 INSERTSORT基
本一致 。
对希尔排序的分析提出了许多困难的数学问题, 特别是如何选择增
量序列才能产生最好的排序效果, 至今没有得到解决 。 希尔本为
最初提出取 d1=┗ n/2┛, di+1=┗ di/2┛, dt=1,t=┗ log2n┛ 。 后来又
有人提出其它选择增量序列的方法, 如 di+1=┗ (di-1)/3┛, dt=1，
t=┗ log3n-1┛ ；以及 di+1=┗ (di-1)/2┛, dt=1,t=┗ log2n-1┛ 。
为什么希尔排序的时间性能优于直接插入排序呢？ 我们知道直接插
入排序在文件初态为正序时所需要时间最少, 实际上, 当文件初
基本有序时直接插入排序所需的比较和移动次数均较少 。 另一面,
当 n值较小时, n和 n2的差别也较小, 即直接插入排序的最好时间
复杂度 O(n)和最坏时间复杂度 O(n2)差别不大 。 在希尔排序时增量
较大, 分组较多, 每组的记录数目少, 故各组内直接插入较快,
后来增量 di逐渐缩小, 分组数逐渐减少, 而各组的记录数目逐渐
增多, 但由于已经按 di-1作为距离排过序, 使文件较近于有序状态,
所以新的国趟排序过程也较快 。 因此, 希尔排序在较率上较直接
接入排序有较大的改进 。
希尔排序是不稳定的。参见图 9-2的例子，该例中两个相同关键字 49
在排序前后的相对次序发生了变化。
返回本章首页
下一页
上一页
选择排序
选择排序 （ selection sort） 也是一种简单排序法 。 一个记录最多只需进行一
次交换就可以直接到达它的排序位置 。
设待排序的文件为 （ R1,R2,…, Rn）, 进行选择排序的基本步骤如下：
（ 1） 置 i 为 1；
（ 2） 当 i<n时, 重复下列步骤；
1） 当 (Ri,…, Rn)中选出一个关键字最小的记录 Rmin,若 Rmin不是 Ri,即
Rmin≠i则交换 Ri和 Rmin的位置；否则, 不进行交换 。
2） i的值加 1。
第 1遍扫描时, 在 n个记录中为了选出最小关键字的记录, 需要进行 n-1次比
较, 第 2扫描时, 在余下的 n-1记录中, 再选出具有最小关键字的记录需
要比较 n-2次, …… 第 n-1扫描时, 在最后的 2个记录中, 比较 1次选出最小
关键字的记录 。
返回本章首页
下一页
上一页
堆排序
堆排序 (heap sort)是在选择排序的基础上发展起来的 。 它
比选择排序的效率要高 。 在堆排序中, 把待排序的文
件逻辑上看作是一棵顺序二叉树, 并用到堆的概念 。
在介绍堆排序之前, 先引入堆的概念 。
我们回忆一下，一棵有 n个结点的顺序二叉树可以用一个
长度为 n的向量 (一维数组 )来表示；反过来，一个有 n个
记录的顺序表示的文件，在概念上可以看作是一棵有 n
个结点 (即记录 )的顺序二叉树。例如，一个顺序表示的
文件 (R1,R2,……, R9)，可以看作为图 9-4所示的顺
序二叉树。
返回本章首页
下一页
上一页
当我们把顺序表示的文件 (R1,R2,…, Rn)看作为顺序二叉树时, 由顺序二叉树的性质可知：记
录 Ri(1<i≤n)的双亲是记录 R[i 2]； R1的左孩子是记录 R2i(2i≤n),但若 2i>n,则 Ri的左孩子不存在；
Ri的右孩子是记录 R2i+1(2i+1≤n),但若 2i+1>n,则 Ri的右孩子不存在 。
什么是堆呢?堆是一个具有这样性质的顺序二叉树, 每个非终端结点 (记录 )的关键字大于等于它的
孩子结点的关键字 。 例如, 图 9-5所示的顺序二叉树就是一个堆 。
显然, 在一个堆中, 根结点具有最大值 (指关键字, 下同 ),而且堆中任何一个结点的非空左, 右子
树都是一个堆, 它的根结点到任一叶子的每条路径上的结点都是递减有序的 。
堆排序的基本思想是：首先把待排序的顺序表示 (一维数组 )的文件 (R1,R2,…, Rn)在概念上看作
一棵顺序二叉树, 并将它转换成一个堆 。 这时, 根结点具有最大值, 删去根结点, 然后将剩
下的结点重新调整为一个堆 。 反复进行下去, 直到只剩下一个结点为止 。
堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆 。 初始状态时, 结点是随机排列的, 需
要经过多次调整才能把它转换成一个堆, 这个堆叫做初始堆 。 建成堆之后, 交换根结点和堆
的最后一个结点的位置, 相当于删去了根结点 。 同时, 剩下的结点 (除原堆中的根结点 )又构成
一棵顺序二叉树 。 这时, 根结点的左, 右子树显然仍都是一个堆, 它们的根结点具有最大值
(除上面删去的原堆中的根结点 )。 把这样一棵左, 右子树均是堆的顺序二叉树调整为新堆, 是
很容易实现的 。
例如, 对于图 7-7所示的堆, 交换根结点 63和最后的结点 30之后, 便得到图 9-6(a)所示的顺序二叉
树 (除 63之外 )。 现在, 新的根结点是 30,其左, 右子树仍然都是堆 。 下面讨论如何把这棵二叉
树调整为一个新堆 。
由于堆的根结点应该是具有最大值的结点, 且已知左, 右子树是堆, 因此, 新堆的根结点应该是
这棵二叉树的根结点, 根结点的左孩子, 根结点的右孩子 (若存在的话 )中最大的那个结点 。 于
是, 先找出根结点的左, 右孩子, 比较它们的大小 。 将其中较大的孩子再与根结点比较大小 。
如果这个孩子大于根结点, 则将这个孩子上移到根结点的位置, 而根结点下沉到这个孩子的
位置, 即交换它们的位置 。 在图 9-6(a)中, 根结点 30的左, 右孩子分别是 60,59,由于 60>59，
并且 60>30,于是应交换根结点 30和左孩子 60的位置 。
这时，新的根结点 60的右子树没有改变，仍然是一个堆。但是，由于结点 30下沉到左子树的根上，
使得左子树有可能不再是堆了。按照上面所用的办法，把这棵子树调整为一个堆，显然，结
点 30的左、右子树原来都是堆,30的左、右子树分别是 40,45。由于 40<45，并且 45>30，于
是应交换结点 30和右孩子 45的位置。
返回本章首页
下一页
上一页
void adjust(struct node r[m+1],int m)
/* 将文件 (r[1],r[2],…,r[m])解释为一棵顺序二叉树,将其中以 r[i]为根结点的二叉树调
整
为一个堆,设以 r[i]为根的二叉树的左,右子树已是堆,1≤i≤1[m/2] */
{ x=r[i];j=2*i;
/*求出 r[i]的左孩子 r[2*i],即 r[j] */
while (j<=m) /*有左孩子 */
{ if ((j<m) &&(r[j].key<r[j+1].key)) /*比较左, 右孩子 */
j=j+1; /*左孩子 <右孩子 */
if (x.key<r[j].key) /*比较根结点和它的大孩子 */
{ r[i]=r[j]; /*大孩子上移到它的双亲位置 */
i=j; /*今 r[j]为根结点 */
j=2*i; /*求出左孩子 */
}
else j=m+1 /*根不小于它的任一孩子时, 强迫退出 while
循环 */
}
r[i]:=x; /*将存放在 x
中的根结点放到 r[i]中 */
}
返回本章首页
下一页
上一页
快速排序
快速排序 (Quick Sort)称划分交换排序。其基本思
想是：在当前无序区 R[1]到 R[h]到中任取一个
记录作为比较的“基准”（不妨记为 temp），
用此基准将当前无序区划分为左右两个较小的
无序子区,R[1]到 R[i-1]和 R[i+1]到 R[h]，且左
边的无序子区中记录的关键字均小于或等于基
准 temp的关键字，右边的无序子区中记录的关
键字均大于或等于基准 temp的关键字，而基准
temp则位于最终排序的位置上
返回本章首页
下一页
上一页
R[1]到 R[i-1]中关键字 ≤temp.key=R[i+1]到 R[h]的关键字 （ 1≤i≤h）
当 R[1]到 R[I-1]和 R[I+1]到 R[h]均非空时, 分别对它们进行上述的划
分过程, 直至所有无序子区中记录均已排好序为止 。
要完成对当前无序区 R[1]到 R[h]的划分，具体做法是：设置两个指针
i和 j，它们的初值分别为 i=1和 j=h。不妨取基准为无序区的第 1个
记录 R[i]（即 R[1]），并将它保存在变量 temp中。令 j自 h起向左扫
描，直到找到第 1个关键字小于 temp.key的记录 R[j]，将 R[j]移至 i
所指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）的位置，
使关键字小于基准关键字的记录移到了基准的左边）；然后，令 i
自 i+1起向右扫描，直至找到第 1个关键字大于 temp.key的记录 R[i]，
将 R[i]移至 j指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）
的位置，使关键字大于基准关键字的记录移到了基准的右边）；
接着，令 j自 j+1起向右扫描，如此交替改变扫描方向，从两端各
自往中间靠拢，直至 i=j时,i便是基准 x的最终位置，将 x放在此位
置 上就完成了一次划分。
返回本章首页
下一页
上一页
综合上面的叙述, 下面分别给出一次划分及其排序的算法 。
int partition(r,1,h) /*返回划分后被定们的基准记录的位置 */
rectype R[ ]; /*对无序区 R[1]到 R[h]做划分 */
int 1,h;
{int i,j;
rectype temp;
i=1;j=h temp=R[i]; /*初始化, temp为基准 */
Do{
While((R[j].key>=temp.key) && (i<j))
j--; /*从右向左扫描, 查找第 1个关键字小于 temp.key的记录 */
if(i<j) R[i++]=R[j]; /*交换 R[i]和 R[j]*/
while((R[i].key<=temp.key) && (i<j))
i++; /*从左向左扫描, 查找第 1个关键字大于
temp.key的记录 */
if(i<j) R[j--]=R[i]; /*交换 R[i]和 R[j]*/
}
quicksort(R,s1,t1) /*对 R[s1]到 R[t1]*/
rectype R[ ];
int s1,t1;
{int i;
if (s1<t1) /* 只有一个记录或无记录须排序 */
{i= partition (R,s1,t1); /*对 R[s1]到 R[t1]做划分 */
quicksort (R,s1,i-1); /*递归处理左区间 */
quicksort (R,i+1,t1); /*递归处理右区间 */
}
}
返回本章首页
下一页
上一页
图 9-7展示了一次划分的过程及整个快速排序的过程 。 图中方括号表示无序区, 方框表示基准 temp的关键字, 它未
参加真正的交换, 只是在划分完成时才将它放入正确的位置上 。
初始关键字 [[49 ] 38 65 97 76 13 27 49`]
i j
j向左扫描 [[49] 38 65 97 76 13 27 49 `]
i j
第一次交换后 [27 38 65 97 76 13 [ ] 49`]
i j
i向右扫描 [27 38 65 97 76 13 [ ] 49 `]
i j
第二次交换后 [27 38 [ ] 97 76 13 65 49 `]
i j
j向左扫描, 位置不变
第三次交换后 [27 38 13 97 76 [ ] 65 49]`]
i向左扫描, 位置不变, i j
第四次交换后 [27 38 13 [ ] 76 97 65 49 `]
i j
j向左扫描 [27 38 13 [49] 76 97 65 49 `]
i j
返回本章首页
下一页
上一页
初始关键字,[49 38 65 97 76 13 27 49`]
一趟排序之后,[27 38 13] 49 [76 97 65 49`]
二趟排序之后,[13] 27 [38] 49 [49` 65] 76 [97]
三趟排序之后,13 27 38 49 49` [65] 76 97
最后的排序结果,13 27 38 79 79` 65 76 97
(b) 各趟排序之后的状态
返回本章首页
下一页
上一页
最坏情况是第次划分选取的基准都是当前无序区中关键字最小 （ 或
最大 ） 的记录, 划分的基准左边的无序子区为空 （ 或右边的无序
子区为空 ）, 而划分所得的另一个非空的无序子区中记录数目,
仅仅比划分前的无序区中记录个数减少一个 。 因此, 快速排序必
须做 n-1趟, 每一趟中需进行 n-i次比较, 故总手工艺比数次数达到
最大值：
Cmax=∑ (n-i)=n(n-1)/2=O(n2)
显然, 如果按上面给出的划分算法, 每次取当前无序区的第 1个记录
为基准, 那么当文件的记录已按递增序 （ 或递减序 ） 排列时, 每
次划分所取的基准就是当前无序区中关键字最小 （ 或最大 ） 的记
录, 则快速排序所需的比较次数反而最多 。
在最好情况下, 每次划分所取的基准都是当前无序区的, 中值, 记
录, 划分的结果是基准的左, 右两个无序子区的长度大致相等地 。
设 C（ n） 表示对长度为 n的文件进行快速排序所需的比较次数,
显然, 它应该等于对长度为 n的无序区进行划分所需的比较次数 n-
1。 加上递归地对划分所得的左, 右两个无序子区 （ 长度 ≤n/2） 进
行快速排序所需的比较总人
数。
返回本章首页
下一页
上一页
假设文件长度 n=2k,那么总的比较次数为：
C(n) ≤n+2C(n/2)
≤n+2[n/2+2C(n/22)]=2n+4C(n/22)
≤2n+4[n/4+2C(n/23)]=3n+8C(n/23)
≤……
≤kn+2kC(n/2k)=nlog2n+nC(1)
=O(nlog2n)
注意：式中 C（ 1）为一常数,k=log2n。,
返回本章首页
下一页
上一页
因为快速排序的记录移动次数不大于比较的次数, 所以,
快速排序的最坏时间复杂度应为 O（ n2）, 最好时间复
杂雅兴 O(log2n)。 为了改善最坏情况下的时间性能, 可
采用三者取中的规则, 即在每一趟划分开始前, 首先
比较 R[1].key,R[h].key和 R[[(1+h)/2]].key,令三者中取
中值的记录和 R[1]交换之 。
可以证明：快速排序的平均时间复杂度也是 O(nlog2n)，
它是目前基于比较的内部排序方法 中速度最快的, 快
速排序亦因此而得名 。
快速排序需要一个栈空间来实现递归 。 若每次划分均能
将文件均 匀分割 为两 部分, 则栈的 最大深 度为
[log2n]+1,所需栈空间为 O（ log2n） 。 最坏情况下, 递
归深度为 n,所需栈空间为 O（ n)。
快速排序是不稳定的，请读者自行检验。
返回本章首页
下一页
上一页
归并排序
归并排序 (Merge Sort)是利用“归并”技术来进行排序，
所谓归并是指将若干个已排序的子文件合并成一个有
序的文件。简单的归并是将两个有序的子文件合并成
一个有序的文件。假设 R(low)到 R[m]和 R[m+1]到
R[high]是存储在同一个数组中且相邻的两个有序的子
文件，要将它们合并为一个有序文件 R1[low]到 R1[high]，
只要设置三个指示器 i,j和 k，其初值分别是这三个记
录区的起始位置。合并时依次比较 R[i]和 R[j]的关键字，
取关键字较小的记录复制到 R1[k]中，然后，将指向被
复制记录的指示器加 1和指向复制位置的指示器 K加 1，
重复这一过程，直至全部记录被复制到 R1[low]到
R1[high]中为止。
返回本章首页
下一页
上一页
基数排序
前介绍的排序方法都是根据关键字值的大小来进行排序的 。 本节介绍的方法是按组成
关键字的各个位的值来实现的排序的, 这种方法称为基数排序 （ radix sort） 。 采
用基数排序法需要使用一批桶 （ 或箱子 ）, 故这种方法又称为桶排序列 。 下面以
十进制数为例来说明基数排充的过程 。
假定待排序文件中所有记录的关键字为不超过 d位的非负整数, 从最高位到最低位
（ 个位 ） 的编号依次为 1,2,…, d。 设置 10个队列 （ 即上面所说的桶 ）, 它们的
编号分别为 0,1,2,…, 9。 当第一遍扫描文字时, 将记录按关键字的个位 （ 即
第 d位）数分别放到相应的队列中：个位数为 0的关键字，其记录依次放入 0号队列中 i
个位数为 1的关键字，其记录放入 1号队列中 … ；个位数为 9的关键字，其记录放入
9号队列中。这一过程叫做按个位数分配。现在把这 10个队列中的记录，按 0号,1
号,9号队列的顺序收集和排列起来，同一队列中的记录按先进先出的次序排列。
这是第 1遍。第 2遍排序使用同样的办法，将第 1遍排序后的记录按其关键字的十位
数（第 d— 1位）分配到相应的队列中，再把队列中的记录收集和排列起来。继续
进行下去。第 d遍排序时，按第 d— 1遍排序后记录的关键字的最高位（第 1位）进
行分配，再收集和排列各队列中的记录，医得到了原文件的有序文件，这就是以
10为基的关键字的基数排序法。
返回本章首页
下一页
上一页
关键字
1 02
2 77
3 70
4 54
5 64
6 21
7 55
8 11
9 38
1 0 21
初始状态
70
21,1 1,2 1
02
5 4,6 4
55
77
38
70
21
11
21
02
54
64
55
77
38
02
11
2 1,2 1
38
54,55
64
7 0,7 7
02
11
21
21
38
54
55
64
70
77
10 个队列 关键字
第一遍，按个
位数分配
收集后 收集后
第二遍，按十
位数分配
返回本章首页
下一页
上一页
例如, 给出关键字序列 （ 02,77,70,54,64,21,55,11,38,21）, 其
中关键字 02用 1个 0在 2的前面补足到 2位, 余关键字均为 2位的正整数 。 进
行基数排序的过程如图 9-9所示 。
在这个例子中, 文件和所有的队列都表示成向量 （ 一维数组 ） 。 显然, 关键
字的某一位有可能均为同一个数字 （ 例如, 个数都为 0）, 这时所有的记
录都同时装入同一个队列中 （ 例如, 同时装入 0号队列中 ） 。 因此, 如果
每个队列的大小和文件大小相同, 则需要一个 10倍于文件大小的附加空
间 。 此外, 排序时需要进行反复的分配和收集记录 。 所以, 采用顺序表
示是不方便的 。
基数排序所需的计算时间不仅与文件的大小 n有关，而且还与关键字的位数、
关键字的基有关。设关键字的基为 r（十进制数的基为 10，二进制数的基
为 2），为建立 r个空队列所需的时间为 O（ r）。把 n个记录分放到各个队
列中并重新收集起来所需的时间为 O（ n），因此一遍排序所需的时间为
O（ n+r）。若每个关键字有 d位，则总共要进行 d遍排，所以基数排序的
时间复杂度为 O（ d（ n+r））。由于关键字的位数 d直接与基数 r以及最大
关键字的值有关，因此不同的 r和关键字将需要不同的时间。
返回本章首页
下一页
上一页
在已介绍的上述各种内部排序方法中，就所需要
的计算时间来看，快速排序、归并排序、堆排
序是很好的方法。但是，归并排序需要大小为
n的辅助空间，快速排序需要一个栈空。除了
快速排序、堆排序、选择排序不稳定外，基它
排序方法都是稳定的。评价一个排序算法性能
好坏的主要标准是它所需的计算时间和存储空
间。影响计算时间的两个景要因素是比较关键
字的次数和记录的移动次数。在实际应用中，
究竟应该选用何种排序方法，取决于具体的应
用和机器条件。
返回本章首页
下一页
上一页
外部排序
外部排序基本上由两个相对独立的阶段组成 。 首先, 按可用内存大
小, 将外存上含 n个记录的文件分成若干长度为 l的子文件或段
（ segment）, 依次读入内存并利用有效的内部排序方法对它们进
行排序, 并将排序后得到的有序子文件重新写入外存, 通常称这
些有序子文件为归并段或顺串 （ run） ；然后, 对这些归并段进行
逐趟归并, 使归并段 （ 有序的子文件 ） 逐渐由小至大, 直至得到
整个有序文件为止 。 显然, 第一阶段的工作是上一章已经讨论过
的内容 。 本章主要讨论第二阶段即归并的过程 。 先从一个具体例
子来看外排中的归并是如何进行的？
假设有一个含 10000个记录的文件，首先通过 10次内部排序得到 10个
初始归并段 R1~R10，其中每一段都含 1000个记录。然后对它们作
如下图所示的两两归并，直至得到一个有序文件为止。
返回本章首页
下一页
上一页
将两个有序段归并成一个有序段的过程, 若在内存进行, 则很简单,
上一章中的 merge过程便可实现此归并 。 但是, 在外部排序中实现
两两归并时, 不仅要调用 merge过程, 而且要进行外存的读 /写,
这是由于我们不可能将两个有序段及归并结果段同时存放在内存
中的缘故 。 在 11.1节中已经提到, 对外存上信息的读 /写是以, 物
理块, 为单位的 。 假设在上例中每个物理块可以容纳 200个记录,
则每一趟归并需进行 50次, 读, 和 50次, 写,, 四趟归并加上内
部排序时所需进行的读 /写使得在外排中总共需进行 500次的读 /写 。
一般情况下, 外部排序所需总的时间 =
内部排序 （ 产生初始归并段 ） 所需的时间 m*tIS
+外部信息读写的时间 d*tIO （ 11-1）
+内部归并所需的时间 s*utmg
其中,tIS是为得到一个初始归并段进行内部排序所需时间的均值；
tIO是进行一次外存读 /写时间的均值； utmg是对 u个记录进行内部
归并所需时间； m为经过内部排序之后得到的初始归并段的个数；
s为归并的趟数； d为总的读 /写次数。
返回本章首页
下一页
上一页
其中 tIO取决于所用的外部设备, 显然, tIO较 tmg要大得多 。 因此, 提高外
排的效率应主要着眼于减少外存信息读写的次数 d。
下面来分析 d和, 归并过程, 的关系 。 若对上例中所得的 10个初始归并段进
行 5-路平衡归并 （ 即每一趟将 5个或 5个以下的有序子文件归并成一个有
序子文件 ）, 则从下图可见, 仅需进行二趟归并, 外排时总的读 /写次数
便减至 2*100+100=300,比 2-路归并减少了 200次的读 /写 。
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
└──┴──┼──┴───┘ └──┴──┼──┴───┘
R1ˊ R2ˊ
└───────┬──────┘
有序文件
可见, 对同一文件而言, 进行外排时所需读 /写外存的次数和归并的趟数 s成
正比 。 而在一般情况下, 对 m个初始归并段进行 k-路平衡归并时, 归并的
趟数
s = [ logkm ]
可见，若增加 k或减少 m便能减少 s。
返回本章首页
下一页
上一页
各种排序方法的比较
迄今为止, 已有的排序方法远远不止本章讨论的这些方法, 人们之所以热衷于研究多种排序方法, 不仅是由于排序在计算机中所处的重
要地位, 而且还因为不同的方法各有其优缺点, 可适用于不同的场合 。 选取排序方法时需要考虑的因素有：
待排序的记录数目 n；记录本身信息量的大小；关键字的结构及分布情况；对排序稳定性的要求；语言工具的条件, 辅助空间的大小等 。
依据这些因素, 可得出如下几点结论：
（ 1） 若 n较小 （ 譬如 n50),可采用直接插入排序或直接选 。 由于直接插入排序所需记录移动操作较直接选择排序多, 因此若记录本身信
息量较大时, 则选用直接选择排序为宜 。
（ 2） 若文件的初始状态已是按关键字基本有序, 则选用直接插入排序泡排序为宜 。
（ 3） 若 N较大, 则应采用时间复杂度为的排序方法：快速排序 \堆排序或归并排序, 快速排序是目前基于内部排序的中被认为是最好的方
法, 档待排序的关键字是随机人布时, 快速排序的平均时间最少, 但堆排序所需的辅助窨少于快速排序, 并且不会出现序可能出现
的最坏情况, 这两种排序方法都是不稳定的, 若要求排序稳定则可选用归并排序 。 但本文章结合介绍的单个记录起进行两两归并排
算法并不值得提倡, 通常可以将它和直接排序结合在一起用 。 先利用直接插入排序求得的子文件, 然后, 再两 两 归并之 。 因为直
接插入排序是稳定的, 所以, 改进后的归并排序是稳定的 。
（ 4） 在基于比较的排序方法中, 每次比较两个关键字的大小之后, 仅仅出现两种可能的转移, 因此, 可以利用一棵二叉树来描述比较判
定过程, 由此可以证明 ;当文件的 N个关键字分布时, 任何借助于比较的排序算法, 至少要的时间, 由于箱排序和基数排序只需一步
就会引起 M种可能的转移, 即把一个记录半装入 M个箱子之一, 因此, 在一般情况下, 箱乔序和排序可能在时间内完成对 N个记录
的 。 但踞的是, 箱排序和排序只适用于象字符串和整数这类有明显的结构特征的关键字, 当关键字的取值范围属于某个无穷集合时,
无法使用箱排序和排序, 这时只有借助于比较方法来排序 。 由此可知, 若 N较大, 记录的关键字倍数较少时且可以分解时采用排序
较好 。
（ 5） 前面讨论的排序算法, 除排序外, 都是在一维数组上实现的, 当记录本身信息量较大时, 为了避免浪费大量时间移动记录, 可以用
链表作为存储结构, 如插入排序和归并排序都易于在链表上实现, 并分别称之为表和归并表, 但有的方法, 如快速排序和堆排序,
在链表上难于实现, 在这种情况下, 可以提取关键字建立索引表, 然后, 对索引表进行排序 。 然而更为简单的方法是 ;引入一个整
形向量作为辅助表, 排序前, 若排序算法中要求交换, 则只需交换 R[I]和 R[j]即可, 排序结束后, 向量就指示了记录之间的顺序关
系：
无论是用链表还是用辅助窨来实现排序, 都有可能要求最终结果是,
若上述要求，则可以在排序结束后，再按链表或辅助窨表所规定的次序重排各记录，完成这种 重排时间是 o(n)。
