数据结构教学-第9章 排序ppt课件

1、第第9 9章章 排序排序 9.1 排序根本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序总结 9.8 有关排序算法的C言语源程序 9.9 多路归并用于外排序的简介第第9章章 排序排序前往主目录前往主目录第第9 9章章 排序排序第第9章章排序排序9.1 排序根本概念排序根本概念 排序排序sorting又称分类又称分类, 意指把一意指把一批杂乱无章的数据序列重新陈列成有序序批杂乱无章的数据序列重新陈列成有序序列。按待排序的记录的数量多少列。按待排序的记录的数量多少, 排序过排序过程中涉及的存储介质不同程中涉及的存储介质不同, 排序方

2、法分为排序方法分为两大类两大类: 内部排序和外部排序。内部排序内部排序和外部排序。内部排序是指待排序的记录存放在计算机内存之中是指待排序的记录存放在计算机内存之中; 外部排序是指待排序的记录数量很大外部排序是指待排序的记录数量很大, 以以致于内存包容不下而存放在外存储器之中致于内存包容不下而存放在外存储器之中, 排序过程需求访问外存。排序过程需求访问外存。 排序的根据可以是记录的主关键字排序的根据可以是记录的主关键字, 也可以是次关键字也可以是次关键字, 甚至是假设干数据项甚至是假设干数据项的组合。的组合。 为了讨论方便为了讨论方便, 把排序所根据的把排序所根据的数据项统称排序关键字数据项统称

3、排序关键字, 简称关键字。简称关键字。 第第9 9章章 排序排序 假设含有n个记录的序列为R1, R2, , Rn , 其相应的关键字序列为K1, K2, , Kn , 所谓排序就是将记录按关键字非递减或非递增的顺序重新陈列起来。 在待排序的记录中假设有多个一样的关键字, 在用某种方法排序之后, 这些关键字一样的记录相对先后次序不变, 那么称这种排序方法是稳定的; 否那么是不稳定的。本章所引见的内部排序方法包括插入排序、交换排序、选择排序、归并排序和基数排序。 前四类排序是经过比较关键字的大小决议记录先后次序,也称为比较排序。 基数排序是不经关键字比较的排序方法。 为了讨论方便, 在此把排序关

4、键字假设为整型。 记录的构造定义为: 第第9 9章章 排序排序 struct node int key; /*排序关键字域*/ int oth; /*其它域, 根据需求本人设定*/ 第第9 9章章 排序排序9.2 插入排序插入排序 9.2.1 直接插入排序直接插入排序 直接插入排序直接插入排序straight insertion sort是一种最是一种最简单的排序方法。简单的排序方法。 它的根本操作是将一个记录插入它的根本操作是将一个记录插入到一个长度为到一个长度为m假设的有序表中假设的有序表中, 使之仍坚持有使之仍坚持有序序, 从而得到一个新的长度为从而得到一个新的长度为m1的有序表。的有序

5、表。 算法思绪算法思绪: 设有一组关键字设有一组关键字K1, K2, , Kn , 排序开场就以为排序开场就以为K1是一个有序序列是一个有序序列; 让让K2插入上述表插入上述表长为长为1的有序序列的有序序列, 使之成为一个表长为使之成为一个表长为2的有序序列的有序序列; 然后让然后让K3插入上述表长为插入上述表长为2的有序序列的有序序列, 使之成为一使之成为一个表长为个表长为3的有序序列的有序序列; 依次类推依次类推, 最后让最后让Kn插入上述插入上述表长为表长为n-1的有序序列的有序序列, 得一个表长为得一个表长为n的有序序列。的有序序列。 第第9 9章章 排序排序第第9 9章章 排序排序

6、例9.1 设有一组关键字序列55, 22, 44, 11, 33, 这里n=5, 即有5个记录。 如图 9.1 所示。 请将其按由小到大的顺序排序在详细实现Ki 向前边插入时, 有两种方法。 一种方法是让Ki与K1, K2, 顺序比较; 另一种方法是Ki与 Ki-1 , Ki-2 倒着比较。 这里选用后一种方法。 用一维数组r做存储构造, n表示记录个数, MAXSIZE为常量， 且MAXSIZEn。 那么算法如下: 算法 9.1void stinsort struct node rMAXSIZE, int n for i=2; i r0.key rj+1=rj; j-; rj+1=r0; /

7、*将r0即原ri记录内容, 插到rj后一位置*/ /*stinsort*/ 此算法外循环n-1次, 在普通情况下内循环平均比较次数的数量级为n, 所以算法总时间复杂度为n2。 由于比较过程中, 当Kj 与K0相等时并不挪动记录, 因此直接插入排序方法是稳定的。 直接插入排序也可用单链表做存储构造。第第9 9章章 排序排序 当某结点i的关键字Kj与前边有序表比较时,显然先与K1 比较, 再与K2比较, , 即从链表表头结点开场向后逐一比较更适宜。另外, 直接插入排序在原关键字序列根本有序或n值较小时, 它是一种最常用的排序方法, 它的时间复杂度接近于On。 但是, 当n值又较大时, 此方法就不再

8、适用。 第第9 9章章 排序排序 9.2.2 折半插入排序 当直接插入排序进展到某一趟时, 对于ri.key来讲, 前面i-1个记录曾经按关键字有序。 此时不用直接插入排序的方法, 而改为折半查找, 找出ri.key应插的位置, 然后插入。 这种方法就是折半插入排序binary insertion sort。算法如下: 算法 9.2 void binasortstruct node rMAXSIZE, int n for i=2; i=n; i+ ZKr0=ri; l=1; h=i-1; 第第9 9章章 排序排序while l=h mid= l+h/2; ifr0.key=l; j- rj+1

9、=rj; rl=r0; /*binasort*/第第9 9章章 排序排序 9.2.3 希尔排序 希尔排序shell sort是D希尔D.L.Shell提出的“减少增量的排序方法。它的作法不是每次一个元素挨一个元素的比较, 而是初期选用大跨步增量较大间隔比较,使记录腾跃式接近它的排序位置; 然后增量减少; 最后增量为 1, 这样记录挪动次数大大减少, 提高了排序效率。希尔排序对增量序列的选择没有严厉规定。 算法思绪: 先取一个正整数d1d1 n, 把全部记录分成d1 个组, 一切间隔 为d1的倍数的记录看成一组, 然后在各组内进展插入排序; 然后取d2 d2 =1, 即一切记录成为一个组为止。普

10、通选d1约为n/2, d1为 d1 /2, d3为d1 /2, , d1 =1。 第第9 9章章 排序排序 例92 有一组关键字76, 81, 60, 22, 98, 33, 12, 79, 将其按由小到大的顺序排序。 这里n=8, 取d1 =4, d2=2, d3 =1, 其排序过程如图9.2所示。 算法实现见算法9.3。 算法 9.3 void shellsortstruct node rMAXSIZE, int n k=n/2; /*k值代表前文中的d值*/ whilek=1 fori=k+1; ir0.key& j=0 rj+k=rj; j=j-k; rj+k=r0; ZK k

11、=k/2; ZK /*shellsort*/第第9 9章章 排序排序第第9 9章章 排序排序 此算法外层循环是增量由n/2逐渐减少到的循环。 for所构成的循环是针对某一特定的增量k, 进展大跨步腾跃式的插入排序。 例如k=2时, 关键字分成二组, 见图9.2的第2行, 其中第1组是76,12,98,60, 排序后的结果为12,60,76,98,插入操作如下: i=3 K1=76有序, K3 =12向前插; i=5 12,76有序, K5 =98不挪动; i=7 12,76,98有序, K7 =60向前插; 第第9 9章章 排序排序 第2组是33,22,81,79, 排序后的结果为22,33,

12、79,81, 插入操作如下: HT5SS i=4 K2=33 有序, K2 =22向前插; i=6 22,33 有序, K6=81不挪动; i=8 22,33,81有序, K8 =79向前插; 对 整 个 文 件 来 说 , 排 序 结 果 实 践 上 为 : 12,22,60,33,76,79,98,81。 当K=1时, 此算法就等同于直接插入排序方法。 由于前边大增量的处置, 使关键字大致有序, 因此最后一趟排序挪动的记录少, 处置速度快。 第第9 9章章 排序排序 希尔排序的分析是一个复杂的问题, 由于它的时间是所选定的“增量序列的函数, 这涉及到数学上一些尚未处置的难题。 到目前为止,

13、 没有人找到一种最好的增量序列。有人在大量实验根底上推导出, 希尔排序的时间复杂度为On1.3。假设对关键字序列6,7,51,2,52,8进展希尔排序, 可以看出希尔排序是不稳定的。 第第9 9章章 排序排序9.3 交换排序交换排序 9.3.1 冒泡排序 冒泡排序bubble sort是一种人们熟知的、 最简单的交换排序方法。 在排序过程中, 关键字较小的记录经过与其它记录的对比交换, 像水中的气泡向上冒出一样, 移到序列的首部, 故称此方法为冒泡排序法。 排序的算法思绪是: 1 让j取n至2, 将rj.key与rj-1.key比较, 假设rj.keyi;j-if rj.keyrj-1.key

14、第第9 9章章 排序排序第第9 9章章 排序排序 x=rj;rj=ri; ri=x;tag=1;ZK i+; while tag=1 & in; /*bubblesort*/ 算法中tag为标志变量, 当某一趟处置过程中未进展过记录交换时, tag值应为0； 假设发生过交换, 那么tag值为1。 所以外循环终了条件是: 或者tag=0,已有序; 或者i=n, 已进展了n-1趟处置。 该算法的时间复杂度为On2。但是, 当原始关键字序列已有序时, 只进展一趟比较就终了, 此时时间复杂度为On。 第第9 9章章 排序排序 9.3.2 快速排序 快速排序由霍尔Hoare提出, 它是一种对冒泡

15、排序的矫正。 由于其排序速度快, 故称快速排序quick sort。 快速排序方法的本质是将一组关键字K1,K2,Kn 进展分区交换排序。 其算法思绪是: 1以第一个关键字K1为控制字, 将 K1, K2, Kn 分成两个子区, 使左区一切关键字小于等于K1, 右区一切关键字大于等于K1, 最后控制字居两个子区中间的适当位置。 在子区内数据尚处于无序形状。 2将右区首、尾指针记录的下标号保管入栈, 对左区进展与第1步相类似的处置, 又得到它的左子区和右子区, 控制字居中。 第第9 9章章 排序排序 3反复第1、 2步, 直到左区处置终了。 然后退栈对一个个子区进展相类似的处置, 直到栈空。 由

16、以上三步可以看出: 快速排序算法总框架是进展多趟的分区处置; 而对某一特定子区, 那么应把它看成又是一个待排序的文件, 控制字总是取子区中第一个记录的关键字。如今设计一个函数hoare, 它仅对某一待排序文件进展左、右子区的划分, 使控制字居中; 再设计一个主体框架函数quicksort, 在这里屡次调用hoare函数以实现对整个文件的排序。 例9.4 HT设有一组关键字46,56,14,43,95,19,18,72, 这里n=8。 试用快速排序方法由小到大进展排序。 1 分区处置函数hoare第第9 9章章 排序排序 思绪: 首先用两个指针i、j分别指向首、尾两个关键字, i=1,j=8。

17、第一个关键字46作为控制字, 该关键字所属的记录另存储在一个x变量中。从文件右端元素rj.key开场与控制字x.key相比较, 当rj.key大于等于x.key时, rj不挪动, 修正j指针, j-, 直到rj.keyx.key,把记录ri移到文件右边j所指向的位置; 再到文件右边修正j指针, j-。 反复上面的步骤, 直到i=j, 此处就是控制字记录x所在的位置。 第第9 9章章 排序排序 至此将文件分成了左、 右两个子区, 其详细操作见图9.4。 算法如算法 9.5假设某区段文件, 指向第一个记录的指针为l, 指向最后一个记录的指针为h。 算法 9.5 int hoarestruct no

18、de rMAXSIZE,int l,int h i=1;j=h;x=ri; do whilei=x.key j-; if ij ri=rj;i+;第第9 9章章 排序排序第第9 9章章 排序排序 whileij &ri.key=x.key i+; if i=j rj=ri; j-; whileij; ri=x;returni; /*hoare*/ 2 快速排序主体框架算法 对一个文件, 令l=1,h=n, 调用hoare, 求出i; 然后右子区l=i+1,h=n, 入栈, 对左子区令l=1,h=i-1, 再次调用hoare, , 如此反复, 直到全部文件记录处置终了。 图9.5中第1行

19、表示对例9.4的数据进展过一次分区处置之后的结果, 在此根底上经过屡次调用hoare后, 最后得出第5行的结果。 第第9 9章章 排序排序第第9 9章章 排序排序下面给出快速排序的递归算法和非递归算法。 非递归算法: 算法 9.6void quicksort1struct node rMAXSIZE, int n /*int sn2;辅助栈s*/ l=1;h=n;tag=1;top=0; do while lh i=hoarer,l,h; top+;stop0=i+1; stop1=h;h=i-1; 第第9 9章章 排序排序else l=stop0; h=stop1;top-; while t

20、ag=1; /*quicksort1*/ 递归算法: 算法 9.7void quicksort2struct node r,int l,int h iflh i=hoarer,l,h; /*划分两个区*/第第9 9章章 排序排序quicksort2r,l,i-1; /*对左分区快速排序*/quicksort2r,i+1,h; /*对右分区快速排序*/ /*quicksort2*/ 在主程序调用非递归算法比较简单易懂。 假设要调用递归算法, 因函数的形参不同, 需做预处置。主程序的主要操作如下: 调用递归函数 调用非递归函数 creatr,n; creatr,n; l=1;h=n; quicks

21、ort1r,n; quicksort2r,l,h; 输出r; 输出r; 第第9 9章章 排序排序 3 快速排序算法空间时间及稳定性分析 快速排序的非递归算法援用了辅助栈, 它的深度为log2n。 假设每一次分区处置所得的两个子区长度相近, 那么可入栈的子区长度分别为: n/21, n/22, n/23, , n/2k, 又由于n/2k=1,所以k= log2n。分母中2的指数恰好反映出需求入栈的子区个数, 它就是log2n, 也即栈的深度。 在最坏情况下, 比如原文件关键字曾经有序, 每次分区处置仅能得到一个子区。 可入的子区个数接近n, 此时栈的最大深度为n。 快速排序主体算法时间运算量约O

22、log2n, 划分子区函数运算量约On, 所以总的时间复杂度为On log2n, 它显然优于冒泡排序On2。可是算法的优势并不是绝对的, 试分析, 当原文件关键字有序时,快速排序时间复杂度是On2,这种情况下快速排序不快。 第第9 9章章 排序排序 而这种情况的冒泡排序是On,反而很快。在原文件记录关键字无序时的多种排序方法中, 快速排序被以为是最好的一种排序方法。 例9.5 试对6, 7, 51, 2, 52, 8进展快速排序。 排序过程简述如下: 67512528初始形状 52 7 51 6 7 8 2 52 516 7 8 2 52 51 6 7 8 最后形状第第9 9章章 排序排序9.

23、4 选择排序选择排序 9.4.1 简单项选择择排序 简单项选择择排序simple selection sort也是直接选择排序。 此方法在一些高级言语课程中做过引见, 是一种较为容易了解的方法。 对于一组关键字K1, K2, Kn, 将其由小到大进展简单排序的详细思绪是: 首先从K1, K2, Kn中选择最小值, 假设它是Kz, 那么将Kz与K1对换; 然后从K2, K3, , Kn中选择最小值Kz, 再将Kz与Kz对换; 如此进展选择和互换n-2趟。 第n-1趟, 从Kn-1、 Kn中选择最小值Kz, 将Kz与Kn-1对换, 最后剩下的就是该序列中的最大值, 一个由小到大的有序序列就这样构成

24、的。该算法的时间复杂度为On2。 第第9 9章章 排序排序 由此可见, 对于n个记录的关键字, 需求处置n-1趟; 而在每趟之中, 又有一个内循环。 图9.6是一个有5个关键字3,4,1,5,2的简单项选择择排序过程的表示图。 假设用变量z记下较小值的下标, 那么算法如算法 9.8。 算法 9.8 void sisortstruct node rMAXSIZE,int n for i=1;in;i+ z=i; for j=i+1;j=n;j+ 第第9 9章章 排序排序第第9 9章章 排序排序 if rj.keyrz.key z=j; x=ri;ri=rz; rz=x; /*sisort*/第第

25、9 9章章 排序排序 9.4.2 堆排序 除了简单项选择择排序之外, 还有树形选择排序锦标赛排序。 1964年威洛姆斯J.Willioms提出了进一步矫正的排序方法, 即堆排序heap sort。 堆是n个元素的有限序列k1, k2, , kn, 它当且仅当满足如下关系: ki=k2i ki= k2i+1 i=1,2, 这是一个上小、 底大的堆。 假设是一个上大、 底小的堆, 只需把“=即可。 堆是一种数据元素之间的逻辑关系, 常用向量做存储构造。 对于第 6 章中引见的满二叉树, 当对它的结点由上而下, 第第9 9章章 排序排序 自左至右编号之后, 编号为i的结点是编号为2i和2i+1结点的

26、双亲。反过来讲, 结点2i是结点i的左孩子, 结点2i+1是结点i的右孩子。图9.7表示完全二叉树和它在向量中的存储形状。 结点编号对应向量中的下标号。 用堆的概念分析向量中的数据, 它显然满足上小、 底大堆的关系。 不难看出, 满足堆的逻辑关系的一组数据, 可画成二叉树的外形, 并且它是一棵完全二叉树树形。因此, 也可借助完全二叉树来描画堆的概念。假设完全二叉树中任一非叶子结点的值小于等于或大于等于其左、 右孩子结点的值, 那么从根结点开场按结点编号陈列所得的结点序列就是一个堆。在图9.8中a、 c是堆, b、 d不是堆。 第第9 9章章 排序排序第第9 9章章 排序排序第第9 9章章 排序

27、排序 堆排序的思绪是: 把n个记录存于向量r之中, 把它看成完全二叉树, 此时关键字序列不一定满足堆的关系。堆排序大致分两步处置。 1 初建堆。从堆的定义动身, 当i=1,2, ,n/2时应满足ki=k2i和ki=k2i+1。所以先取i=n/2 它一定是第n个结点双亲的编号, 将以i结点为根的子树调整为堆; 然后令i=i-1, 将以i结点为根的子树调整为堆。此时能够会反复调整某些结点, 直到i=1为止, 堆初步建成。 2 堆排序。 首先输出堆顶元素普通是最小值, 让堆中最后一个元素上移到原堆顶位置, 然后恢复堆。由于经过第一步输出堆顶元素的操作后, 往往破坏了堆关系, 所以要恢复堆; 反复执行

28、输出堆顶元素、堆尾元素上移和恢复堆的步骤, 直到全部元素输出完为止。 第第9 9章章 排序排序 例 9 . 6 设 有 n 个 记 录 n = 8 的 关 键 字 是46,55,13,42,94,17,5,80, 试对它们进展堆排序。 第一步: 初建堆。由于n=8, 所以从i=4开场, 见图9.9。 调整成为堆是一个较复杂的过程, 当i值确定之后用kz记下ki的值, 用kz分别与k2i和k2i+1比较, 可了解为kz值与结点i的左、 右孩子的关键字比较。 假设一开场kz比k2和k2+1均小, 那么不进展任何调整。例如i=4时, k4k8 4280, 就不用调整, 见图9.9a。假设结点i的某一

29、个孩子的关键字小于kz, 那么把这个孩子结点移上来。假设结点i的两个孩子的关键字都小于kz, 那么将两个孩子中较小的一个调整上来。 第第9 9章章 排序排序第第9 9章章 排序排序 假设结点i的两个孩子的关键字都小于kz, 那么将两个孩子中较小的一个调整上来。 在图9.9c中, i=1时, k2、 k3都小于kz42,546, 那么让k3即5移上去。 此时需求让kz与更下一层的左、 右孩子的关键字进展比较, 直到某一层的左、右孩子的关键字不小于kz, 或左、 右孩子不存在为止。 此时将kz填入适当位置, 使之成为堆。在图9.9c中, 先把5调整上来, 然后把13移到5原来的位置上, 最后将kz

30、即46填到13原来的位置上。 第二步: 堆排序。 这是一个反复输出堆顶元素, 将堆尾元素移至堆顶, 再调整恢复堆的过程。恢复堆的过程与初建堆中i=1时所进展的操作完全一样。请留意: 每输出一次堆顶元素，堆尾的逻辑位置退1，直到堆中剩下一个元素为止。排序过程如图 9.10所示。 第第9 9章章 排序排序 堆排序算法实现: 由上述可知, 有一种操作过程即调整恢复堆要被屡次反复调用, 那就是当i值确定之后, 以ki为比较参照值, 与它的左、 右孩子的关键字比较和调整, 使得以结点i为根的子树成为堆, 因此把这个过程设计成一个函数heap。另外, 当然还需再设计一个主体算法, 使在初建堆阶段, 让i从

31、n/2变化到1, 循环调用函数heap。而在堆排序阶段, 每输出一次堆顶元素同时将堆尾元素移至堆顶之后, 就调用一次heap函数来恢复堆。主体算法由函数heapsort实现。 以编号为i的结点为根, 调整为堆的算法为: 算法 9.9第第9 9章章 排序排序第第9 9章章 排序排序void heapstruct node rMAXSIZE,int i, int m/*i是根结点编号, m是以i结点为根的子树的最后一个结点编号*/ x=ri;j=2*i; /*x保管根记录内容, j为左孩子编号*/ while j=m if jrj+1.key j+; /*当结点i有左、 右两个孩子时, j取关键字

32、较小的孩子结点编号*/ if rj.keym, 以便终了循环*/ 第第9 9章章 排序排序ri=x; /* heap*/堆排序主体算法: 算法 9.10HT void heapsortstruct node rMAXSIZE,int n /*n为文件的实践记录数,r0没有运用*/for i=n/2;i=1;i- heapr,i,n /*初建堆*/for v=n;v=2;v- printf%5d,r1.key; /*输出堆顶元素*/x=r1; r1=rv; rv=x; /*堆顶堆尾元素交换*/heapr,1,v-1; /*本次比上次少处置一个记录*/ printf%5d,r1.key; /* h

33、eapsort*/第第9 9章章 排序排序 在堆排序图示中, 堆越画越小, 实践上在r向量中堆顶元素输出之后并未删除, 而是与堆尾元素对换。 由图9.10可知输出的是一个由小到大的升序序列, 而最后r向量中记录的关键字从r1.key到rn.key是一个由大到小的降序序列。堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的树深log2n+1 相关。 而heapsort中对heap的调用数量级为n, 所以整个堆排序的时间复杂度为Onlog2n。在内存空间占用方面, 根本没有额外的辅助空间, 仅有一个x。如今来分析堆排序的稳定性问题。设有一组关键字: 6,7,51,2,52,8,经排序后的结果

34、是: 2,52,51,6,7,8。 本来51在前面, 排序后52移到51的前面, 所以说堆排序是不稳定的。堆排序的部分处置过程如图9.11所示。 第第9 9章章 排序排序第第9 9章章 排序排序9.5 归并排序归并排序 归并排序merge sort是一类与插入排序、交换排序、选择排序不同的另一种排序方法。 归并的含义是将两个或两个以上的有序表合并成一个新的有序表。 归并排序有多路归并排序和两路归并排序； 可用于内排序, 也可以用于外排序。 这里仅对内排序的两路归并方法进展讨论。 两路归并排序算法思绪: 1把n个记录看成n个长度为l的有序子表; 2进展两两归并使记录关键字有序, 得到n/2个长度

35、为2的有序子表; 3 反复第2步， 直到一切记录归并成一个长度为n的有序表为止。 第第9 9章章 排序排序 例9.7 HT有一组关键字4,7,5,3,2,8,6,1, n=8, 将其按由小到大的顺序排序。 两路归并排序操作过程如9.12所示, 其中l为子表长度。 初始4 7 5 3 2 8 6 1 l=1第 1 趟4 7 3 2 1 l=2第 2 趟3 4 5 7 1 2 6 8 l=4第 1 趟1 2 3 4 5 6 7 8 l=n 算法实现: 此算法的实现不像图示那样简单, 现分三步来讨论。 首先从宏观上分析, 先让子表表长l=1进展处置; 不时地使l=2*L, 进展子表处置, 直到l=n

36、为止, 把这一过程写成一个主体框架函数mergesort。 第第9 9章章 排序排序第第9 9章章 排序排序 然后对于某确定的子表表长l, 将n个记录分成假设干组子表, 两两归并, 这里显然要循环假设干次, 把这一步写成一个函数mergepass, 可由mergesort调用。 最后再看每一组一对子表的归并, 其原理是一样的, 只是子表表长不同。换句话说, 是子表的首记录号与尾记录号不同, 把这个归并操作作为中心算法写成函数merge, 由mergepass来调用。 主体框架算法描画如下: 算法 9.11 void mergesortstruct node rMAXSIZE,int n /*r

37、是包含有n个记录的原文件, 归并过程中另需一个r2作为辅助存储空间*/ l=1; /*子表初始长度*/第第9 9章章 排序排序 while l=2*l /*剩下的记录数目大于两个子表时*/ h1=i; mid=h1+l-1;h2=i+2*l-1; merger,r2,h1,mid,h2;i=i+2*l; /*跳过两个子表, 指向新的一对子表的首记录*/ if n-i+1=l /*剩下的记录数目小于一个子表时*/for j=i;j=n;j+ r2j=rj;else /*剩下的记录数目大于一个, 小于两个子表时*/ h1=i;mid=h1+l-1;h2=n; merger,r2,h1,mid,h2

38、; /* mergesort*/第第9 9章章 排序排序归并排序中心算法描画如下: 算法 9.13oid mergestruct node rMAXSIZE,struct node r2MAXSIZE,int h1,int mid,int h2 /*h1为第一个子表首元素的下标, mid 为第一个子表未元素的下标, */ /* h2为第二个子表未元素的下标 */ i=h1;j=mid+1;k=h1-1; /* k是r2的初始指针*/ while i=mid & j=h2 k=k+1; if ri.key=rj.key r2k=ri;i+; else r2k=rj;j+; 第第9 9章章

39、 排序排序while i=mid k+;r2k=ri;i+;while j=h2 k+;r2=rj;j+; /* merge*/ 算法的最后两个while语句也可以改写成: if i=mid fort=i;t=mid;t+ k+;r2k=rt;else fort=j;t=h2;t+ k+;r2k=rt;第第9 9章章 排序排序 9.6 基数排序 基数排序radix sort是与前面所引见的各类排序方法完全不同的一种排序方法。 前几节所引见的排序方法主要是经过比较记录的关键字来实现的, 而基数排序法不用经过关键字的比较来实现排序, 而是根据关键字每个位上的有效数字的值, 借助于“分配和“搜集两种

40、操作来实现排序的。 本章假设记录的关键字为整型本质上关键字并不限于整型。 基数排序有两种方法: 一种方法是首先根据最高位有效数字进展排序, 然后根据次高位有效数字进展排序, 依次类推, 直到根据最低位个位有效数字进展排序, 产生一个有序序列。这种方法称最高位优先法Most Significant Digit First, 简称MSD法。 第第9 9章章 排序排序 另一方法是首先根据关键字最低位个位有效数字进展排序, 然后根据次低位十位有效数字进展排序, 依次类推, 直到根据最高位有效数字进展排序, 产生一个有序序列。 这种方法称最低位优先法Least Significant Digit Fir

41、st, 简称LSD法。 现用LSD法进展基数排序。假设有n个记录, 其关键字在0999之间, 每一位上有效数字值在09之间共10种能够性, 那么以为基数是10, 在进展“分配操作时涉及10个队列, 即队列的个数与基数一样。 此处关键字最多位数是3, 那么就需进展3趟“分配和“搜集操作。 算法思绪: 第第9 9章章 排序排序 1 第一趟“分配, 根据关键字个位有效数字, 把一切记录分配到相应的10个队列中去。 用f0, e0表示 0 号队列的头、 尾指针, f9, e9表示9号队列的头、 尾指针。 例如, 关键字为184的记录就分配到4号队列中去。 2第一趟“搜集把一切非空队列10个队列中能够有

42、空队按队列号由小到大的顺序头、尾相接, 搜集成一个新的序列。此序列假设察看其关键字的个位, 那么它是有序的; 假设察看其关键字的高位, 那么它尚处于无序形状。 3以后各趟分别根据关键字的十位、 百位有效数字反复第1、2步的“分配与“搜集操作, 最终得到一个按关键字由小到大的序列。 例9.8 有一组关键字278,109,063,930,589,184,505,269,008,083, 将它们按由小到大的顺序排序。 第第9 9章章 排序排序 图9.13a是待排序的关键字序列的初始形状。 图9.13b是按每个关键字的个位有效数字将它们分配到相应的队列中去。 例如, 关键字008、278都分配到了8号

43、队列中去, e8指向队尾, f8指向队头。 图9.13c是将6个非空队列0号, 3号, 4号, 5号, 8号, 9号头尾相接搜集在一同之后得到的一个新的序列。 图9.13d是按每个关键字十位上的有效数字重新将它们分配到相应的队列中去, 例如, 关键字589、 184、 083都分配到了8号队列中去。然后再次搜集, 构成如图9.13e所示的新的序列。 图9.13f那么是按百位上的有效数字分配之后的各队列形状。 图9.13g那么是再次搜集后的结果, 这也是基数排序所得到的最终的有序序列。 第第9 9章章 排序排序第第9 9章章 排序排序 在本章前几节的讨论中, 待排序的记录是用向量r做存储构造的。

44、 基数排序又是“分配队列, 又要“搜集起来, 故适用于链表方式存储。 本节不采用动态链表而仍用向量r存储即一维数组, 让每个存放记录的数组元素添加一个指针域。此域为整型, 用来存放该 记录的下一个相邻记录所在数组元素的下标。 这种构造称为静态链表构造。所谓队列的头、尾指针也是整型, 它们记下可做某号队列队头或队尾元素的记录在数组r中的下标值。 记录构造为: struct node int key; /*关键字域*/ int oth; /*其它信息域*/ int point; /*指针域*/ 第第9 9章章 排序排序 基数排序算法: 设n个待排序的记录存储在向量r中, 限定关键字为整型并且有效数

45、字位数d5; 基数显然是10; 10个队列的头指针、 尾指针分别用向量f和e来表示, 代表头指针的数组元素是f0, f1, , f9, 代表尾指针的数组元素分别是e0, e1, e2, , e9, 那么算法描画如下: 算法 9.14 int radixsortstruct node rMAXSIZE,int n int f10,e10; for i=1;in;i+ ri.point=i+1; rn.point=0;p=1; /*建立静态链表, p指向链表的第一个元素第第9 9章章 排序排序for i=1;i=d;i+ /*下面是分配队列*/ for j=0;j10;j+ fj=0;ej=0;w

46、hile p!KG-*2=0 k=yxrp.key,i; /*取关键字倒数第i位有效数字*if fk=0 fk=p; ek=p; *让头指针指向同一元素*else l=ek;rl.point=p; ek=p; *在k号队列尾部入队* p=rp.point; *在r向量中, p指针向后移* 第第9 9章章 排序排序*下面是搜集* j=0; while fj=0 j+; /*找第一个非空队列* p=fj; t=ej; *p记下队头做搜集后的静态链表头指针* while j10 j+; while j10 & fj=0 j+; if fj!KG-*2=0 rt.point=fj; t=ej;

47、 *将前边一个非空队列的队尾指针指向如今队头并记下如今队尾位置*第第9 9章章 排序排序rt.point=0; *这是一趟分配与搜集之后的链表最后一个元素* /* for i */ returnp; /*基数排序结果p指向静态链表的第一个元素, 即关键字最小的记录* /*radixsort*/分别关键字倒数第i位有效数字算法: 第第9 9章章 排序排序算法 9.15int yxint m,int i switch case 1:x=m%10; /*个位* case 2:x=m%100/10; *十位* case 3:x=m%1000/100; *百位* case 4:x=m%10000/100

48、0; *千位* returnx; /*yx*/第第9 9章章 排序排序 radixsort算法中基数为10, 这里用rd表示它, 最高有效数字位是4, 这里用d表示, 记录总数为n。 基数排序时间复杂度为Odn+rd, 这是由于总共循环d趟, 每趟分配运算量数量级为On, 搜集运算量数量级为Ord, 所以总时间复杂度为Odn+rd。 它的空间占用情况是, 向量r多了n个指针域, 辅助空间为2rd个队列指针。 基数排序是稳定的。 第第9 9章章 排序排序.7 内部排序总结内部排序总结 表9.1列出了8种排序方法的性能比较。 当问题的规模不大, 即待排序的记录数n不大时n=50, 可选用表中前三种

49、排序方法之一。它们的时间复杂度虽为On2, 但方法简单易掌握。 直接插入排序和冒泡排序在原文件记录按关键字“根本有序时, 排序速度比较快。其中直接插入排序更为常用。 当n值很大, 并不强求排序稳定性, 并且内存容量不宽余时, 应该选用快速排序或堆排序。普通来讲, 它们排序速度非常快。但快速排序对原序列根本有序的情况, 速度减慢接近On2,而堆排序不会呈现最坏情况。 第第9 9章章 排序排序第第9 9章章 排序排序 当n值很大, 对排序稳定性有要求, 存储容量较宽余时, 用归并排序最为适宜。 排序速度很快, 并且稳定性好。 当n值很大并且关键字位数较小时, 采用静态链表基数排序不只速度较快, 并

50、且稳定性好。 第第9 9章章 排序排序9.8 有关排序算法的有关排序算法的C言语源程序言语源程序 本章引见了多种算法, 其中直接插入排序、 折半插入排序、 冒泡排序和简单项选择择排序的程序在各种程序设计言语中都有详细的引见。 这里我们提供希尔排序、 快速排序、 堆排序、 归并排序和基数排序的程序清单均已上机经过, 供大家在消化算法和实验时参考。 struct node /*记录构造。 为简化问题, 设定记录中只含关键字* int key; r20;第第9 9章章 排序排序main oid printstruct node a20,int n; int creat ; oid shellstru

51、ct node a20,int n; int hoarestruct node a20,int l,int h; oid quick1struct node a20,int n; oid quick2struct node a20,int l,int h; oid heapstruct node a20,int i,int m; oid heapsortstruct node a20,int n; oid mergestruct node a20,struct node a220,int h1,int mid,int h2;第第9 9章章 排序排序oid mergepassstruct nod

52、e a20,struct node a220,int l,int n; oid mergesortstruct node a20,int n; int yxint m,int i; int radixsortstruct rnode a20,int n; int num,l,h,c; struct rnode s20;c=1; while c!KG-*2=0第第9 9章章 排序排序 printf 主菜单; printf1. 输入关键字, 以-9999表示终了。 n; printf2. 希尔排序n; printf3. 非递归的快速排序n; printf4. 递归的快速排序n; printf5.

53、堆排序n; printf6. 归并排序n; printf7. 基数排序n; printf输入选择 1-7,0 表示终了:;第第9 9章章 排序排序 scanf%d,&c; switchc case 1:num=creat;printr,num;break; case 2:shellr,num;printr,num;break; case 3:quick1r,num;printr,num;break; case 4:l=0;h=num-1;quick2r,l,h; printfoutput quick2sort result:n; printr,num;break; case 5:hea

54、psortr,num;break; case 6:mergesortr,num;printr,num;break; case 7:radixsorts,num;第第9 9章章 排序排序 /*main end*/ oid prin tstruct node a20,int n*打印记录* int i; for i=0;i=1;i- ai.key=ai-1.key; k=n/2; while k=1 for i=k+1;ia0.key & j=0 aj+k.key=aj.key;j=j-k; aj+k=a0; 第第9 9章章 排序排序 k=k/2; for i=0;in;i+ ai.key

55、=ai+1.key; printf输出希尔排序的结果:n; *shell end*int hoarestruct node a20,int l,int h*分区处置函数* int i,j; struct node x; i=l;j=h;x.key=ai.key; do whilei=x.key j-; ifij ai.key=aj.key;i+;第第9 9章章 排序排序 whileij & ai.key=x.key i+; if ij aj.key=ai.key;j-; while ij; ai.key=x.key;returni; *hoare end*oid quick1struc

56、t node a20,int n*非递归的快速排序主体函数* int i,l,h,tag,top; int s202; l=0;h=n-1;tag=1;top=0; do while lh第第9 9章章 排序排序 i=hoarea,l,h; top+;stop0=i+1; stop1=h;h=h-1; iftop=0 tag=0; else l=stop0; h=stop1;top-; while tag=1;第第9 9章章 排序排序printf输出非递归快速排序的结果:n; *quick1 end*oid quick2struct node a20,int l,int h*递归的快速排序主体

57、函数 int i; iflh i=hoarea,l,h; quick2a,l,i-1; quick2a,i+1,h; *quick2 end*第第9 9章章 排序排序oid heapstruct node a20,int i,int m*调整堆的函数* struct node x; int j; x.key=ai.key;j=2*i; while j=m if jaj+1.key j+; if aj.key0;i- ai.key=ai-1.key; for i=n/2;i=1;i- heapa,i,n; printf输出归并排序的结果:n; for=n;=2;- printf%5d,a1.ke

58、y; x.key=a1.key;a1.key=a.key; a.key=x.key; heapa,1,-1; 第第9 9章章 排序排序printf%5d,a1.key; for i=0;in;i+ ai.key=ai+1.key; *heapsort end*oid mergestruct node a20,struct node a220,int h1,int mid,int h2*归并排序的中心算法* int i,j,k; i=h1;j=mid+1;k=h1-1; while i=mid & j=h2 k=k+1; if ai.key=aj.key a2k.key=ai.key;i

59、+; 第第9 9章章 排序排序 else a2k.key=aj.key;j+; while i=mid k+;a2k.key=ai.key;i+; while j=2*l第第9 9章章 排序排序 h1=i;mid=h1+l-1;h2=i+2*l-1; mergea,a2,h1,mid,h2; i=i+2*l; if n-i=l for j=i;j=n;j+ a2j.key=aj.key; else h1=i;mid=h1+l-1;h2=n-1; mergea,a2,h1,mid,h2; *mergepass end*第第9 9章章 排序排序oid mergesortstruct node a2

60、0,int n*归并排序的主体函数 int l; struct node a220; l=1; while ln mergepassa,a2,l,n;l=2*l; mergepassa2,a,l,n;l=2*l; printf输出归并排序的结果:n; *mergesort end*第第9 9章章 排序排序int yxint m,int i*分别关键字倒数第i位有效数字的算法* int x; switchi case 1:x=m%10; break; case 2:x=m%100/10;break; case 3:x=m%1000/100;break; case 4:x=m%10000/1000; returnx; /*yx end*第第9 9章章 排序排序struct r