数据结构PPT教学课件-第9章 排序.ppt
106页
第9章 排序,,9.1 排序基本概念,,,,9.2 插入排序,,,9.3 交换排序,,,9.4 选择排序,,,,9.5 归并排序,,,,9.6 基数排序,,,,9.7 内部排序总结,,,,9.8 有关排序算法的C语言源程序,,,9.9 多路归并用于外排序的简介,第9章 排序,返回主目录,,第9章排序,9.1 排序基本概念,,排序（sorting）又称分类, 意指把一批杂乱无章的数据序列重新排列成有序序列按待排序的记录的数量多少, 排序过程中涉及的存储介质不同, 排序方法分为两大类: 内部排序和外部排序内部排序是指待排序的记录存放在计算机内存之中; 外部排序是指待排序的记录数量很大, 以至于内存容纳不下而存放在外存储器之中, 排序过程需要访问外存排序的依据可以是记录的主关键字, 也可以是次关键字, 甚至是若干数据项的组合 为了讨论方便, 把排序所依据的数据项统称排序关键字, 简称关键字假设含有n个记录的序列为｛R,1,, R,2,, …, R,n,｝, 其相应的关键字序列为｛K,1,, K,2,, …, K,n,｝, 所谓排序就是将记录按关键字非递减(或非递增)的顺序重新排列起来。
,,在待排序的记录中若有多个相同的关键字, 在用某种方法排序之后, 这些关键字相同的记录相对先后次序不变, 则称这种排序方法是稳定的; 否则是不稳定的本章所介绍的内部排序方法包括插入排序、交换排序、选择排序、归并排序和基数排序 前四类排序是通过比较关键字的大小决定记录先后次序,也称为比较排序 基数排序是不经关键字比较的排序方法 ,,为了讨论方便, 在此把排序关键字假设为整型 记录的结构定义为: ,struct node,,｛ int key; /*排序关键字域*/,,int oth; /*其它域, 根据需要自己设定*/,,｝,9.2 插入排序,9.2.1 直接插入排序,,直接插入排序（straight insertion sort）是一种最简单的排序方法 它的基本操作是将一个记录插入到一个长度为m（假设）的有序表中, 使之仍保持有序, 从而得到一个新的长度为m＋1的有序表 ,,算法思路: 设有一组关键字｛K,1,, K,2,, …, K,n,｝, 排序开始就认为K,1,是一个有序序列; 让K,2,插入上述表长为1的有序序列, 使之成为一个表长为2的有序序列; 然后让K,3,插入上述表长为2的有序序列, 使之成为一个表长为3的有序序列; 依次类推, 最后让K,n,插入上述表长为n-1的有序序列, 得一个表长为n的有序序列。
例9.1 设有一组关键字序列｛55, 22, 44, 11, 33｝, 这里n=5, 即有5个记录 如图 9.1 所示 请将其按由小到大的顺序排序在具体实现K,i,向前边插入时, 有两种方法 一种方法是让K,i,与K,1,, K,2,, …顺序比较; 另一种方法是K,i,与 K,i-1,, K,i-2,… 倒着比较 这里选用后一种方法 ,,用一维数组r做存储结构, n表示记录个数, MAXSIZE为常量， 且MAXSIZE>n 则算法如下:,,算法 9.1,,void stinsort (struct node r［MAXSIZE］, int n),,｛ 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］; /*将r［0］即原r［i］记录内容, 插到r［j］后一位置*/,,｝,,｝/*stinsort*/,,此算法外循环n-1次, 在一般情况下内循环平均比较次数的数量级为Ｏ(n), 所以算法总时间复杂度为Ｏ(n,2,)。
由于比较过程中, 当K,j,与K,0,相等时并不移动记录, 因此直接插入排序方法是稳定的 ,,直接插入排序也可用单链表做存储结构当某结点i的关键字K,j,与前边有序表比较时,显然先与K,1,比较, 再与K,2,比较,… …, 即从链表表头结点开始向后逐一比较更合适另外, 直接插入排序在原关键字序列基本有序或n值较小时, 它是一种最常用的排序方法, 它的时间复杂度接近于O(n) 但是, 当n值又较大时, 此方法就不再适用 ,,9.2.2 折半插入排序,,当直接插入排序进行到某一趟时, 对于r［i］.key来讲, 前面i-1个记录已经按关键字有序此时不用直接插入排序的方法, 而改为折半查找, 找出r［i］.key应插的位置, 然后插入 这种方法就是折半插入排序（binary insertion sort）算法如下: ,,算法 9.2,,void binasort(struct node r［MAXSIZE］, int n),,｛ for (i=2; i<=n; i++),,｛ 〖ZK(〗r［0］=r［i］; ,,l=1; h=i-1; ,while (l<=h),,｛ mid= (l+h)/2; ,,if(r［0］.key
它的作法不是每次一个元素挨一个元素的比较, 而是初期选用大跨步（增量较大）间隔比较,使记录跳跃式接近它的排序位置; 然后增量缩小; 最后增量为 1, 这样记录移动次数大大减少, 提高了排序效率希尔排序对增量序列的选择没有严格规定 ,,算法思路: 先取一个正整数d,1,(d,1,
for所构成的循环是针对某一特定的增量k, 进行大跨步跳跃式的插入排序 例如k=2时, 关键字分成二组, 见图9.2的第2行, 其中第1组是［76,12,98,60］, 排序后的结果为［12,60,76,98］,插入操作如下: ,,i=3 ［K1=76］有序, K,3,=12向前插;,, i=5 ［12,76］有序, K,5,=98不移动; ,,i=7 ［12,76,98］有序, K,7,=60向前插; ,第2组是［33,22,81,79］, 排序后的结果为［22,33,79,81］, 插入操作如下: ,,[HT5”SS],,i=4 ［K,2,=33］ 有序, K,2,=22向前插; ,,i=6 ［22,33］ 有序, K,6,=81不移动; ,,i=8 ［22,33,81］有序, K,8,=79向前插; ,,对整个文件来说, 排序结果实际上为: ［12,22,60,33,76,79,98,81］ ,,当K=1时, 此算法就等同于直接插入排序方法 由于前边大增量的处理, 使关键字大体有序, 因此最后一趟排序移动的记录少, 处理速度快。
,希尔排序的分析是一个复杂的问题, 因为它的时间是所选定的“增量序列”的函数, 这涉及到数学上一些尚未解决的难题 到目前为止, 没有人找到一种最好的增量序列有人在大量实验基础上推导出, 希尔排序的时间复杂度为O(n1.3）如果对关键字序列{6,7,51,2,52,8}进行希尔排序, 可以看出希尔排序是不稳定的9.3 交换排序,,9.3.1 冒泡排序,,冒泡排序(bubble sort)是一种人们熟知的、 最简单的交换排序方法 在排序过程中, 关键字较小的记录经过与其它记录的对比交换, 像水中的气泡向上冒出一样, 移到序列的首部, 故称此方法为冒泡排序法 ,,排序的算法思路是: ,,(1) 让j取n至2, 将r［j］.key与r［j-1］.key比较, 如果r［j］.key 这表明关键字已经有序, 因此不必要进行第5趟至第7趟处理 算法如算法9.4void bubblesort(struct node r［MAXSIZE］,int n) { i=1;,,do { tag=0;,,for (j=n;j>i;j--),,if (r［j］.key 其算法思路是: ,,（1）以第一个关键字K,1,为控制字, 将［ K,1,, K,2,,…, K,n,］分成两个子区, 使左区所有关键字小于等于K,1,, 右区所有关键字大于等于K,1,, 最后控制字居两个子区中间的适当位置 在子区内数据尚处于无序状态 ,,（2）将右区首、尾指针(记录的下标号)保存入栈, 对左区进行与第（1）步相类似的处理, 又得到它的左子区和右子区, 控制字居中3）重复第（1）、 （2）步, 直到左区处理完毕 然后退栈对一个个子区进行相类似的处理, 直到栈空 ,,由以上三步可以看出: 快速排序算法总框架是进行多趟的分区处理; 而对某一特定子区, 则应把它看成又是一个待排序的文件, 控制字总是取子区中第一个记录的关键字现在设计一个函数hoare, 它仅对某一待排序文件进行左、右子区的划分, 使控制字居中; 再设计一个主体框架函数quicksort, 在这里多次调用hoare函数以实现对整个文件的排序 ,,例9.4 [HT]设有一组关键字{46,56,14,43,95,19,18,72}, 这里n=8 试用快速排序方法由小到大进行排序 ,,1) 分区处理函数hoare,思路: 首先用两个指针i、j分别指向首、尾两个关键字, i=1,j=8。 第一个关键字46作为控制字, 该关键字所属的记录另存储在一个x变量中从文件右端元素r［j］.key开始与控制字x.key相比较, 当r［j］.key大于等于x.key时, r［j］不移动, 修改j指针, j--, 直到r［j］.keyx.key,把记录r［i］移到文件右边j所指向的位置; 再到文件右边修改j指针, j--重复上面的步骤, 直到i=j, 此处就是控制字记录x所在的位置至此将文件分成了左、 右两个子区, 其具体操作见图9.4 算法如算法 9.5（假设某区段文件, 指向第一个记录的指针为l, 指向最后一个记录的指针为h）,,算法 9.5,,int hoare(struct node r［MAXSIZE］,int l,int h),,{ i=1;j=h;x=r［i］;,,do ,,{ while((i=x.key)) j--;,,if (i 图9.5中第1行表示对例9.4的数据进行过一次分区处理之后的结果, 在此基础上经过多次调用hoare后, 最后得出第5行的结果 ,下面给出快速排序的递归算法和非递归算法 ,,① 非递归算法: ,,算法 9.6,,void quicksort1(struct node r［MAXSIZE］, int n) /*int s［n］［2］;辅助栈s*/,,{ l=1;h=n;tag=1;top=0;,,do { while (l 若要调用递归算法, 因函数的形参不同, 需做预处理主程序的主要操作如下: ,,调用递归函数 调用非递归函数,,{ creat(r,n); { creat(r,n);,,l=1;h=n; quicksort1(r,n);,,quicksort2(r,l,h); 输出r;,,输出r; },,},3） 快速排序算法空间时间及稳定性分析,,快速排序的非递归算法引用了辅助栈, 它的深度为log2n 假设每一次分区处理所得的两个子区长度相近, 那么可入栈的子区长度分别为: n/21, n/22, n/23, …, n/2k, 又因为n/2k=1,所以k= log2n分母中2的指数恰好反映出需要入栈的子区个数, 它就是log2n, 也即栈的深度在最坏情况下, 比如原文件关键字已经有序, 每次分区处理仅能得到一个子区。 可入的子区个数接近n, 此时栈的最大深度为n,,快速排序主体算法时间运算量约O(log,2,n), 划分子区函数运算量约O(n), 所以总的时间复杂度为O(n log,2,n), 它显然优于冒泡排序O(n2)可是算法的优势并不是绝对的, 试分析, 当原文件关键字有序时,快速排序时间复杂度是O(n2),这种情况下快速排序不快而这种情况的冒泡排序是O(n), 反而很快在原文件记录关键字无序时的多种排序方法中, 快速排序被认为是最好的一种排序方法 ,,例9.5 试对［6, 7, 51, 2, 52, 8］进行快速排序 ,,排序过程简述如下: ,,67512528初始状态,,［52 7 51］ 6 ［7 8］,,［2］ 52 ［51］6 7 ［8］,,［2 52 51 6 7 8］ 最后状态,9.4 选择排序,,9.4.1 简单选择排序,,简单选择排序(simple selection sort)也是直接选择排序 此方法在一些高级语言课程中做过介绍, 是一种较为容易理解的方法 ,,对于一组关键字{K,1,, K,2,,…, K,n,}, 将其由小到大进行简单排序的具体思路是: ,,首先从K,1,, K,2,,…, K,n,中选择最小值, 假如它是K,z,, 则将K,z,与K,1,对换; 然后从K,2,, K,3,, …, K,n,中选择最小值K,z,, 再将K,z,与K,z,对换; 如此进行选择和调换n-2趟。 第(n-1)趟, 从K,n-1,、 K,n,中选择最小值K,z,, 将K,z,与K,n-1,对换, 最后剩下的就是该序列中的最大值, 一个由小到大的有序序列就这样形成的该算法的时间复杂度为O(n,2,)由此可见, 对于n个记录的关键字, 需要处理n-1趟; 而在每趟之中, 又有一个内循环图9.6是一个有5个关键字{3,4,1,5,2}的简单选择排序过程的示意图假设用变量z记下较小值的下标, 则算法如算法 9.8 ,,算法 9.8,,void sisort(struct node r［MAXSIZE］,int n),,{ for (i=1;i 若是一个上大、 底小的堆, 只需把“=”即可堆是一种数据元素之间的逻辑关系, 常用向量做存储结构 对于第 6 章中介绍的满二叉树, 当对它的结点由上而下,,自左至右编号之后, 编号为i的结点是编号为2i和2i+1结点的双亲反过来讲, 结点2i是结点i的左孩子, 结点2i+1是结点i的右孩子图9.7表示完全二叉树和它在向量中的存储状态 结点编号对应向量中的下标号 ,,用堆的概念分析向量中的数据, 它显然满足（上小、 底大）堆的关系 不难看出, 满足堆的逻辑关系的一组数据, 可画成二叉树的形状, 并且它是一棵完全二叉树树形因此, 也可借助完全二叉树来描述堆的概念若完全二叉树中任一非叶子结点的值小于等于（或大于等于）其左、 右孩子结点的值, 则从根结点开始按结点编号排列所得的结点序列就是一个堆在图9.8中(a)、 (c)是堆, (b)、 (d)不是堆 ,堆排序的思路是: 把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) 堆排序 首先输出堆顶元素（一般是最小值）, 让堆中最后一个元素上移到原堆顶位置, 然后恢复堆因为经过第一步输出堆顶元素的操作后, 往往破坏了堆关系, 所以要恢复堆; 重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤, 直到全部元素输出完为止例9.6 设有n个记录(n=8)的关键字是{46,55,13,42,94,17,5,80}, 试对它们进行堆排序 ,,第一步: 初建堆因为n=8, 所以从i=4开始, 见图9.9 ,,调整成为堆是一个较复杂的过程, 当i值确定之后用k,z,记下k,i,的值, 用k,z,分别与k,2i,和k,2i+1,比较, 可理解为kz值与结点i的左、 右孩子的关键字比较 如果一开始kz比k,2,和k,2+1,均小, 则不进行任何调整例如i=4时, k,4, 在图9.9(c)中, i=1时, k,2,、 k,3,都小于k,z,(42,5<46), 则让k3(即5)移上去 此时需要让kz与更下一层的左、 右孩子的关键字进行比较, 直到某一层的左、右孩子的关键字不小于k,z,, 或左、 右孩子不存在为止 此时将k,z,填入适当位置, 使之成为堆在图9.9(c)中, 先把5调整上来, 然后把13移到5原来的位置上, 最后将kz(即46)填到13原来的位置上 ,,第二步: 堆排序 这是一个反复输出堆顶元素, 将堆尾元素移至堆顶, 再调整恢复堆的过程恢复堆的过程与初建堆中i=1时所进行的操作完全相同请注意: 每输出一次堆顶元素，堆尾的逻辑位置退1，直到堆中剩下一个元素为止排序过程如图 9.10所示,堆排序算法实现: 由上述可知, 有一种操作过程（即调整恢复堆）要被多次反复调用, 那就是当i值确定之后, 以ki为比较参照值, 与它的左、 右孩子的关键字比较和调整, 使得以结点i为根的子树成为堆, 因此把这个过程设计成一个函数heap另外, 当然还需再设计一个主体算法, 使在初建堆阶段, 让i从［n/2］变化到1, 循环调用函数heap而在堆排序阶段, 每输出一次堆顶元素同时将堆尾元素移至堆顶之后, 就调用一次heap函数来恢复堆。 主体算法由函数heapsort实现 ,,以编号为i的结点为根, 调整为堆的算法为: ,,算法 9.9,void heap(struct node r［MAXSIZE］,int i, int m),,/*i是根结点编号, m是以i结点为根的子树的最后一个结点编号*/,,{ x=r［i］;j=2*i; /*x保存根记录内容, j为左孩子编号*/,,while (j<=m),,{ if (jr［j+1］.key) j++;,,/*当结点i有左、 右两个孩子时, j取关键字较小的孩子结点编号*/,,if (r［j］.key 由图9.10可知输出的是一个由小到大的升序序列, 而最后r向量中记录的关键字从r［1］.key到r［n］.key是一个由大到小的降序序列堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的树深［log2n］+1 相关 而heapsort中对heap的调用数量级为n, 所以整个堆排序的时间复杂度为O(nlog2n)在内存空间占用方面, 基本没有额外的辅助空间, 仅有一个x现在来分析堆排序的稳定性问题设有一组关键字: {6,7,51,2,52,8},经排序后的结果是: {2,52,51,6,7,8} 本来51在前面, 排序后52移到51的前面, 所以说堆排序是不稳定的堆排序的部分处理过程如图9.11所示 ,9.5 归并排序,归并排序(merge sort)是一类与插入排序、交换排序、选择排序不同的另一种排序方法 归并的含义是将两个或两个以上的有序表合并成一个新的有序表 归并排序有多路归并排序和两路归并排序； 可用于内排序, 也可以用于外排序 这里仅对内排序的两路归并方法进行讨论 ,,两路归并排序算法思路: ,,（1）把n个记录看成n个长度为l的有序子表; ,,（2）进行两两归并使记录关键字有序, 得到［n/2］个长度为2的有序子表; ,,（3） 重复第（2）步， 直到所有记录归并成一个长度为n的有序表为止。 ,例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为止, 把这一过程写成一个主体框架函数mergesort。 然后对于某确定的子表表长l, 将n个记录分成若干组子表, 两两归并, 这里显然要循环若干次, 把这一步写成一个函数mergepass, 可由mergesort调用 最后再看每一组（一对）子表的归并, 其原理是相同的, 只是子表表长不同换句话说, 是子表的首记录号与尾记录号不同, 把这个归并操作作为核心算法写成函数merge, 由mergepass来调用 ,,主体框架算法描述如下: ,,算法 9.11,,void mergesort(struct node r［MAXSIZE］,int n),,/*r是包含有n个记录的原文件, 归并过程中另需一个r2作为辅助存储空间*/,,{ l=1; /*子表初始长度*/,,while (l 前几节所介绍的排序方法主要是通过比较记录的关键字来实现的, 而基数排序法不必经过关键字的比较来实现排序, 而是根据关键字每个位上的有效数字的值, 借助于“分配”和“收集”两种操作来实现排序的 ,,本章假设记录的关键字为整型（实质上关键字并不限于整型） 基数排序有两种方法: 一种方法是首先根据最高位有效数字进行排序, 然后根据次高位有效数字进行排序, 依次类推, 直到根据最低位（个位）有效数字进行排序, 产生一个有序序列这种方法称最高位优先法(Most Significant Digit First), 简称MSD法另一方法是首先根据关键字最低位（个位）有效数字进行排序, 然后根据次低位（十位）有效数字进行排序, 依次类推, 直到根据最高位有效数字进行排序, 产生一个有序序列 这种方法称最低位优先法(Least Significant Digit First), 简称LSD法 ,,现用LSD法进行基数排序假设有n个记录, 其关键字在0～999之间, 每一位上有效数字值在0～9之间共10种可能性, 则认为基数是10, 在进行“分配”操作时涉及10个队列, 即队列的个数与基数相同 此处关键字最多位数是3, 那么就需进行3趟“分配”和“收集”操作。 算法思路: ,1） 第一趟“分配”, 根据关键字个位有效数字, 把所有记录分配到相应的10个队列中去 用f［0］, e［0］表示 0 号队列的头、 尾指针, f［9］, e［9］表示9号队列的头、 尾指针 例如, 关键字为184的记录就分配到4号队列中去 ,,（2）第一趟“收集”把所有非空队列（10个队列中可能有空队）按队列号由小到大的顺序头、尾相接, 收集成一个新的序列此序列若观察其关键字的个位, 则它是有序的; 若观察其关键字的高位, 则它尚处于无序状态 ,,（3）以后各趟分别根据关键字的十位、 百位有效数字重复第（1）、（2）步的“分配”与“收集”操作, 最终得到一个按关键字由小到大的序列 ,,例9.8 有一组关键字{278,109,063,930,589,184,505,269,008,083}, 将它们按由小到大的顺序排序 ,图9.13(a)是待排序的关键字序列的初始状态 ,,图9.13(b)是按每个关键字的个位有效数字将它们分配到相应的队列中去 例如, 关键字008、278都分配到了8号队列中去, e［8］指向队尾, f［8］指向队头,,图9.13(c)是将6个非空队列（0号, 3号, 4号, 5号, 8号, 9号）头尾相接收集在一起之后得到的一个新的序列。 ,,图9.13(d)是按每个关键字十位上的有效数字重新将它们分配到相应的队列中去, 例如, 关键字589、 184、 083都分配到了8号队列中去然后再次收集, 形成如图9.13(e)所示的新的序列 图9.13(f)则是按百位上的有效数字分配之后的各队列状态 图9.13(g)则是再次收集后的结果, 这也是基数排序所得到的最终的有序序列 ,在本章前几节的讨论中, 待排序的记录是用向量r做存储结构的 基数排序又是“分配”队列, 又要“收集”起来, 故适用于链表形式存储 本节不采用动态链表而仍用向量r存储（即一维数组）, 让每个存放记录的数组元素增加一个指针域此域为整型, 用来存放该 记录的下一个相邻记录所在数组元素的下标 这种结构称为静态链表结构所谓队列的头、尾指针也是整型, 它们记下可做某号队列队头或队尾元素的记录在数组r中的下标值 记录结构为: ,,struct node,,{ int key; /*关键字域*/,,int oth; /*其它信息域*/,,int point; /*指针域*/,,},基数排序算法: 设n个待排序的记录存储在向量r中, 限定关键字为整型并且有效数字位数d<5; 基数显然是10; 10个队列的头指针、 尾指针分别用向量f和e来表示, 代表头指针的数组元素是f［0］, f［1］, …, f［9］, 代表尾指针的数组元素分别是e［0］, e［1］, e［2］, …, e［9］, 则算法描述如下: ,,算法 9.14 ,,int radixsort(struct node r［MAXSIZE］,int n),,{ int f［10］,e［10］;,,for (i=1;i 基数排序时间复杂度为O(d(n+rd)), 这是因为总共循环d趟, 每趟分配运算量数量级为O(n), 收集运算量数量级为O(rd), 所以总时间复杂度为O(d(n+rd)) 它的空间占用情况是, 向量r多了n个指针域, 辅助空间为2rd个队列指针 基数排序是稳定的 ,９.7 内部排序总结,表9.1列出了8种排序方法的性能比较１） 当问题的规模不大, 即待排序的记录数n不大时(n<=50), 可选用表中前三种排序方法之一它们的时间复杂度虽为O(n2), 但方法简单易掌握 直接插入排序和冒泡排序在原文件记录按关键字“基本有序”时, 排序速度比较快其中直接插入排序更为常用 ,,（２）当n值很大, 并不强求排序稳定性, 并且内存容量不宽余时, 应该选用快速排序或堆排序一般来讲, 它们排序速度非常快但快速排序对原序列基本有序的情况, 速度减慢接近O(n2),而堆排序不会出现最坏情况 ,（３） 当n值很大, 对排序稳定性有要求, 存储容量较宽余时, 用归并排序最为合适 排序速度很快, 并且稳定性好 ,,（４） 当n值很大并且关键字位数较小时, 采用静态链表基数排序不仅速度较快, 并且稳定性好。 ,9.8 有关排序算法的C语言源程序,本章介绍了多种算法, 其中直接插入排序、 折半插入排序、 冒泡排序和简单选择排序的程序在各种程序设计语言中都有详细的介绍 这里我们提供希尔排序、 快速排序、 堆排序、 归并排序和基数排序的程序清单（均已上机通过）, 供大家在消化算法和实验时参考struct node,/*记录结构 为简化问题, 设定记录中只含关键字*／,,{ int key;,,} r［20］;,main( ),,{ oid print(struct node a［20］,int n); ,,int creat( );,,oid shell(struct node a［20］,int n); ,,int hoare(struct node a［20］,int l,int h);,,oid quick1(struct node a［20］,int n);,,oid quick2(struct node a［20］,int l,int h);,,oid heap(struct node a［20］,int i,int m);,,oid heapsort(struct node a［20］,int n);,,oid merge(struct node a［20］,struct node a2［20］,int h1,int mid,int h2);,oid mergepass(struct node a［20］,struct node a2［20］,int l,int n);,,oid mergesort(struct node a［20］,int n);,,int yx(int m,int i);,,int radixsort(struct rnode a［20］,int n);,,int num,l,h,c;,,struct rnode s［20］;c=1;,,while (c![KG-*2]=0),{ printf(" 主菜单"); ,,printf("1. 输入关键字, 以-9999表示结束。 \n");,,printf("2. 希尔排序\n");,,printf("3. 非递归的快速排序\n");,,printf("4. 递归的快速排序\n");,,printf("5. 堆排序\n");,,printf("6. 归并排序\n");,,printf("7. 基数排序\n");,,printf("输入选择 (1-7,0 表示结束):");,scanf("%d",,,switch(c),,{ case 1:num=creat();print(r,num);break;,,case 2:shell(r,num);print(r,num);break;,,case 3:quick1(r,num);print(r,num);break;,,case 4:l=0;h=num-1;quick2(r,l,h);,,printf("output quick2sort result:\n");,,print(r,num);break;,,case 5:heapsort(r,num);break;,,case 6:mergesort(r,num);print(r,num);break;,,case 7:radixsort(s,num);,},,},,} /*main end*/ ,,oid prin t(struct node a［20］,int n) ／*打印记录*／,,{ int i;,,for (i=0;i
