各种经典排序算法.ppt

本节基本内容与要求,基本内容顺序查找、二分查找、二叉树查找以及散列表上查找 及算法思想排序的基本概念以及选择、插入、交换和归并四类排序的基本思想和算法要求掌握线性表、树和散列表(或称哈希表)的查找方法及算法实现以及各种查找方法的应用熟练掌握选择、插入、交换和归并四类排序的基本思想和算法,1.4 内部排序,一、基本概念二、插入排序三、交换排序四、选择排序五、归并排序,一、基本概念,1.排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。,例如：下列是一组记录对应的关键字序列,(52,49,80,36,14,58,61,23,97,75),调整为,(14,23,36,49,52,58,61,75,80,97),2.排序的定义,假设含n个记录的序列为 R1,R2,，Rn 其相应的关键字序列为 K1,K2,，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为 Rp1,Rp2,，Rpn 的操作称作排序。,3、排序的基本操作,排序的概念：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。排序过程的组成步骤：首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。对记录的关键字大小进行比较将记录从一个位置移动到另一个位置当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。,4、排序的稳定性,若有：R1,.,Ri,.,Rj,.且关键字：Ki=Kj ij排序后：Ri,Rj,.则称该排序结果具有稳定性。,在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。,内部排序：是指在排序的整个过程中，数据全部存放在计算机的内存储器里，并且在内存储器里调整数据的位置；当文件很大以致内存不足以存放全部数据时，在排序过程中需要对外存进行存取访问，称这种借助于外存储器进行排序的方法为外部排序。注意：内排序适用于记录个数不很多的小文件 外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。,5、排序的分类,每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。把新元素（未排序的元素的关键字）逐个插入正在增长的顺序表中。寻找插入位置的方法：线性插入排序对半插入排序希尔排序,二、插入排序,有序序列L.r1.i-1,L.ri,无序序列 L.ri.n,有序序列L.r1.i,无序序列 L.ri+1.n,1、线性插入排序,基本思想：每步将一个待排序的元素按其大小插入到前面已排序的数据中的适当位置。重复该工作，直至有序区包含所有元素。,方法：,具体方法：先将第一个数据看成是一个有序的子序列，然后从第2个数据起逐个插入到这个有序的子序列中去，相应的元素要移动。,3将L.ri 插入到L.rj+1的位置上。,2将L.rj+1.i-1中的所有记录均后移 一个位置；,1在L.r1.i-1中查找L.ri的插入位置，L.r1.j L.ri L.rj+1.i-1；,该算法适合于n 较小的情况，时间复杂度为O(n2).,待排元素序列：53 27 36 15 69 42第一次排序：27 53 36 15 69 42第二次排序：27 36 53 15 69 42第三次排序：15 27 36 53 69 42第四次排序：15 27 36 53 69 42第五次排序：15 27 36 42 53 69 线性插入排序示例,对于有n个数据元素的待排序列，插入操作要进行n-1次,例：,void insertSort(RedType L,int n)int i,j;for(i=2;i=n;i+)L0=Li;/作为监视哨 for(j=i-1;L0.keyLj.key;j)Lj+1=Lj;/记录后移 Lj+1=L0;/插入,插入算法,方法:Ki与Ki-1,K i-2,K1依次比较,直到找到应插入的位置。,哨兵(监视哨),哨兵(监视哨)有两个作用作为临时变量存放Ri(当前要进行比较的关键字)的副本；在查找循环中用来监视下标变量j是否越界。,R0 R1 R2 R3 R4 R5 6 206157315 62015737 6152073367152033671520,直接插入排序的程序：#include stdio.h#define n 5 int arn;int c,t;void d_insort(a)int an;int i,j;for(i=2;i0),main()int i;printf(请输入数据:);for(i=1;i=n;i+)scanf(%d,运行结果：请输入数据:50 60 20 40 80排序后的序列:20|40|50|60|80|,性能分析,最好情况（原始记录按关键字有序排列）：O（n）,“比较”的次数：,最坏情况（原始记录按关键字逆序排列）：O（n2）,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,结论：适用原始数据基本有序或数据量不大的情况。,希尔排序（Shells method）又称为“缩小增量排序”，本质上讲是插入排序，它是对线性插入排序的改进。其基本思想是：先取一个小于n的整数d1并作为第一个增量，将文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2d1，重复上述的分组和排序，直至所取的增量dt=1(dtdt1d2d1)为止，此时，所有的记录放在同一组中进行直接插入排序。,2 希尔插入排序算法思想,如何选择增量序列才能产生最好的排序效果，这个问题至今没有得到解决。希尔本人最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。,希尔插入排序步骤,（1）首先选取一个整数d1n（n为待排序数据的个数），作为两个数据之间的距离，这样把全部数据分成d1个组，凡是距离为d1的数据放在一个组里，在各组内进行内部排序，直到各组排好序为止。（2）从上述的结果序列出发，再选择d2d1，重复上面的分组与排序工作。（3）依次取di+1di，直到dm=1（设一共需要m次分组），即所有数据放在一组中排序为止。此时，全部数据便按次序排好了。,设待排序共有10个记录，其关键字分别为47,33,61,82,71,11,25,47,57,02，增量序列取值依次为5,3,1。,希尔插入排序过程,希尔排序实质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。在每趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，所以关键字较小的记录在排序过程中是作跳跃式的移动。另外，由于开始时增量的取值较大，每组中记录较少，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。,希尔插入排序特点,希尔排序比直接插入排序的平均性能要好：在最好情况（原始记录按关键字有序排列）下，移动次数为0，比较次数界于n n2 之间。在最坏情况（原始记录按关键字逆序排列）下，移动次数和比较次数接近n2。在平均情况下，移动次数和比较次数在O（n1.3）左右，好于直接插入排序。,希尔插入排序性能效率,例1.19 希尔排序的程序#include stdio.h#define max 10 int datamax+1;int indexmax+1;int i;,void shell_sort(a)int amax+1;int i,j,n,m,skip;int alldone;for(i=1;i1)skip=skip/2;do alldone=1;for(j=1;j=max-skip;j+)i=j+skip;n=indexi;m=indexj;if(anam)indexi=m;indexj=n;alldone=0;while(alldone=0);,main()printf(请输入数据:);for(i=1;i=max;i+)scanf(%d,运行结果：请输入数据:19 41 11 17 47 43 13 37 31 23 19 41 11 17 47 43 13 37 31 23 11 13 17 19 23 31 37 41 43 47 希尔排序的分析较为复杂，因为它的时间是所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题。增量序列可以有各种取法，但需注意：应使增量序列中的值没有除1以外的公因子，并且最后一个增量值必须等于1。,2.希尔排序,三、交换排序,两两比较待排序记录的关键字，发现两个记录次序相反时即进行交换，直到没有反序的记录为止。冒泡排序快速排序,假设在排序过程中，记录序列L.r1.n的状态为：,第 i 趟冒泡排序,无序序列L.r1.n-i+1,有序序列 L.rn-i+2.n,n-i+1,无序序列L.r1.n-i,有序序列 L.rn-i+1.n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,7.3.1 冒泡排序基本思想和过程,void BubbleSort(SqList*L)for(i=L-length;i1;-i)for(j=1;jrj+1rj)Swap(L-rj,L-rj+1);,时间性能分析：,比较次数:最坏(n-1)+(n-2)+.+1;最好：n-1 移动次数:最坏：3(n-1)+(n-2)+.+1)；最好：0,7.3.1 冒泡排序算法和性能分析,2,5,5,3,1,5,7,9,8,9,i=7,i=6,for(j=1;j rj+1 rj),1,3,i=2,7.3.1 冒泡排序改进,void BubbleSort(SqList*L)i=L-length;while(i1)/定位第i个位置的记录 lastExchangeIndex=1;for(j=1;jrj+1rj)Swap(L-rj,L-rj+1);lastExchangeIndex=j;i=lastExchangeIndex;,7.3.1 冒泡排序改进算法,最好情况（记录按关键字有序排列）：只需进行一趟冒泡,“比较”的次数：,最坏情况（记录按关键字逆序排列）：需进行n-1趟冒泡,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,n-1,7.3.1 冒泡排序性能分析,首先对无序的记录序列进行“一次划分”，通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行快速排序,7.3.2 快速排序基本思想,快速排序 目标,找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录移至该记录之前，反之，移至该记录之后。一趟排序之后，无序序列L.r low.high将被分割成两个部分：,L.rlow.i-1和L.r i+1.high 且 L.r j L.r i L.r j(lowji-1)枢轴(i+1jhigh)。,快速排序 方法,关键字通常取第一个记录的值为基准值。方法：附设两个指针i和j，初值分别指向第一个记录和最后一个记录，设关键字为 key，首先从 j所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从i 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至i=j为止。,初始值 46 55 13 42 94 5 17 70,快速排序一趟算法,初始值 46 55 13 42 94 5 17 70,17 55 13 42 94 5 17 70,17 55 13 42 94 5 55 70,基准X=46,17 5 13 42 94 5 55 70,17 5 13 42 94 94 55 70,17 5 13 42 94 94 55 70,46,第一趟 13 5 17 42 46 94 55 70,快速排序例,初始值 46 55 13 42 94 5 17 70,第二趟 5 13 17 42 46 70 55 94,第三趟 5 13 17 42 46 55 70 94,第四趟 5 13 17 42 46 55 70 94,快速排序步骤,(1)令指针L1，Rn，即分别指向A1和An；(2)自尾端开始进行比较：将AR与AL比较，若ALAR，则数据就不交换，此时固定L（即L指针不动），调整尾指针，使RR-1。继续比较，直至ALAR时为止，将AR与AL交换位置，并修改左指针，使LL+1；(3)将AL与AR比较，若ALAR，则调整左指针，使LL+1，R指针不动。继续比较，直至ALAR时为止，将AL与AR交换位置，并修改右指针R，使RR-1；(4)重复(2)(3)步骤，直到从两边开始的扫描在中间相遇，即L、R指针重合于中间某一个元素，此时该元素即在排序的序列中找到了自己合适的位置，并且此元素将原序列分成了前后两个子集。虽然此时这两个子集还是无序的，但前一个子集的所有元素均小于后一个子集的所有元素。这称为一趟。,设 L.rlow=46为枢轴，在调整过程中，设立两个指针：low 和high，之后逐渐减小 high或增加 low，并保证：,将 L.rhigh和枢轴的关键字进行比较，要求L.rhigh枢轴的关键字,将 L.rlow和枢轴的关键字进行比较，要求L.rlow枢轴的关键字,L.rhigh枢轴且L.rlow枢轴,否则进行记录的“交换”。,快速排序算法,void quicksort(int r,int left,int right)int i=left,j=right;int x=ri;while(i=x)/递归调用右子区间,快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。,最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1in-1)，故总的比较次数达到最大值：n(n-1)/2=O(n2),快速排序时间分析,在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlogn),因为快速排序的记录移动次数不大于比较的次数，所以快速排序：最坏时间复杂度应为O(n2)最好时间复杂度为O(nlogn)平均时间复杂度为O(nlogn),快速排序时间分析,快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(logn)，故递归后需栈空间为O(logn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。,因为快速排序的划分次数在lognn之间，所以快速排序的：最坏空间复杂度应为O(n)最好空间复杂度为O(logn)平均空间复杂度为O(logn),快速排序空间分析,若待排记录的初始状态为按关键字有序时，快速排序将退化为冒泡排序，其时间复杂度为O(n2)。,因此，快速排序适用于原始数据杂乱无章的倾向。辅助空间数量为递归调用所开辟的栈空间。,7.3.2 快速排序适用范围,结论:快速排序的时间复杂度为O(nlogn)且适用于原始数据杂乱无章的情况。快速排序是非稳定的。,快速排序的程序：#include stdio.h#define n 10 int arn+1;int i,l1;int quick1(a,l,r)int an+1;int l,r;/*指针*/int l1;int r1,w;l1=l;r1=r;w=al1;do while(ar1=w),void q_sort(a,l,r)int an+1;int l,r;int l1;if(lr)l1=quick1(a,l,r);q_sort(a,l,l1-1);q_sort(a,l1+1,r);,main()printf(请输入数据:n);for(i=1;i=n;i+)scanf(%d,运行结果：请输入数据:42 23 74 11 65 58 94 36 99 87排序后的序列:11 23 36 42 58 65 74 87 94 99,7.3.2 快速排序过程,7.4 选择 排 序,简单选择排序,堆 排 序,假设排序过程中，待排记录序列的状态为：,有序序列L.r 1.i-1,无序序列 L.r i.n,第 i 趟简单选择排序,从中选出关键字最小的记录,有序序列L.r1.i,无序序列 L.ri+1.n,7.4.1 简单选择排序基本思想和过程,四、选择排序,直接选择排序又称为简单选择排序，是一种简单直观的排序方法。从待排序的所有记录中，选取关键字最小的记录，并将它与原始序列中的第一个记录交换，然后从去掉了关键字最小记录的剩余记录中选择关键字最小的记录将它与原始记录序列的第二个记录交换位置，以此类推，直到序列中全部记录排序完毕。,算法：/对记录序列x0 xn-1进行直接选择排序void selectsort(elemtype x,int n)int i,j,small;elemtype swap;for(i=0;in-1;i+)small=i;for(j=i+1;jn;j+)if(xj.keyxsmall.key)small=j;if(small!=i)swap=xi;Xi=xsmall;Xsmall=swap;,对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为：,移动记录的次数，最小值为 0,最大值为3(n-1)。,7.4.1 简单选择排序算法时间性能分析,堆就是一个关键字序列：并且这n个关键字的序列K1,K2.Kn要满足以下性质(堆性质)，就是:KiK2i且KiK2i+1 或者 KiK2i且KiK2i+1,2、堆排序堆的定义,(正堆),(逆堆),12,36,27,65,40,34,98,81,73,55,49,是正堆,12,36,27,65,40,14,98,81,73,55,49,不是堆,1 2 3 4 5 6 7 8 9 10 11,当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时，堆就是这样一棵二叉树：任一非叶结点的关键字均不小于(或不大于)其左右孩子结点的关键字。,2、堆排序,12,36,27,65,49,81,73,55,40,34,98,是堆,14,不,1 2 3 4 5 6 7 8,最大值,a)堆顶元素取最大值大根堆,b)堆顶元素取最小值小根堆,堆排序基本思想,因为堆顶是最大的数，所以当把一个关键字序列排成一个大根堆时，就很容易地找到最大的数，它就在序列的第一个位置上然后把这个最大的数与最后一个记录交换，这时，最后一个记录就是关键字最大的记录了。对于剩下的关键字序列，我们仍然把它排成一个大根堆，然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换。这时，在整个序列后面就有了两个有序的关键字(从小到大)。重复这样的过程，就可以把有序区不断扩大直到全部关键字都进入有序区。直到排序完成。,堆的构造,无序序列r1：n构成的完全二叉树。从它最后一个非叶子结点（第n/2个元素）开始直到根结点为止，逐步进行调整即可将此完全二叉树构成堆。调整：与其左右子树根结点值比较，取其中大的进行交换。,堆的构造例,46 55 13 42 94 05 17 70,1 2 3 4 5 6 7 8,70,17,5,94,42,13,55,46,1 2 3 4 5 6 7 8,42,17,5,94,70,13,55,46,1 2 3 4 5 6 7 8,13,13,堆的构造例,46 55 13 42 94 05 17 70,42,13,5,94,70,17,55,46,1 2 3 4 5 6 7 8,55,55,42,13,5,55,70,17,94,46,1 2 3 4 5 6 7 8,46,46,堆的构造例,46 55 13 42 94 05 17 70,42,13,5,55,70,17,46,94,1 2 3 4 5 6 7 8,46,46,42,13,5,55,46,17,70,94,1 2 3 4 5 6 7 8,成堆!,堆的构造例,46 55 13 42 94 05 17 70,46,55,13,42,70,94,05,17,初始无序结点,从42开始调整,46,55,13,70,42,94,05,17,将以13为根的子树调整成堆,46,55,17,70,42,94,05,13,将以55为根的子树调整成堆,堆的构造例,46 55 13 42 94 05 17 70,调整成堆算法,void SIFT(int r,int i,int n)/调整r1:n中结点ri,使成为一个堆int j;int T;T=ri;j=2*i;/j为i结点的左孩子序号while(jn)if(jn),i,j,T,堆排序,由给定的无序序列构造堆将堆顶元素与堆中最后一个元素交换将最后一个元素从堆中删除将余下的元素构成完全二叉树重新调整成堆反复进行，直到堆空,堆排序过程示例,94,13,5,55,46,17,70,42,94,70,5,42,46,17,55,13,94,70,55,42,13,17,46,5,94,70,55,46,13,17,42,5,94,70,55,46,42,17,13,5,94,70,55,46,42,17,13,5,94,70,55,46,42,17,13,5,堆排序结果,堆排序过程,94,13,5,55,46,17,70,42,94,70,5,42,46,17,55,13,94,70,55,42,13,17,46,5,94,70,55,46,13,17,42,5,94,70,55,46,42,17,13,5,94,70,55,46,42,17,13,5,94,70,55,46,42,17,13,5,第一趟结果:,第二趟结果:,第三趟结果:,第四趟结果:,第五趟结果:,第六趟结果:,第七趟结果:,堆排序算法,void heapsort(int r,int n)/堆排序int t;for(int i=n/2;i=0;i-)/将r调整成堆SIFT(r,i,n);for(i=n-1;i=0;i-)t=r0;r0=ri;ri=t;SIFT(r,0,i-1);,i,0,堆排序的程序：#include stdio.h#define mm 8 int amm+1;int k;void shift(a,l,m)void heapsort(a)int amm+1;int i,x;for(i=mm/2;i=1;i-)shift(a,i,mm);/*从第开始进行筛选建堆*/for(i=mm;i=2;i-)x=a1;a1=ai;ai=x;/*将堆顶元素和堆中最后一个元素交换*/shift(a,1,i-1);/*调整第一个元素使之重又成为堆*/,main()printf(请输入数据:n);for(k=1;k=mm;k+)scanf(%d,五、基数排序,前面介绍的几种排序方法都是按数据元素（或记录关键字）值的大小进行排序的 而多关键字排序是一种按组成数据元素或关键字的各位值进行排序的方法，基数排序借助的就是这种思想，它属于分布式排序，也称口袋排序。基数排序是把逻辑关键字看成由若干个子关键字复合而成的 假设有n个关键字r1，r2，rn需进行排序 每个关键字由d元组（k1k2k3kd）子关键字组成，k1是关键字值的最高位，kd是关键字值的最低位，其基数为rd,五、基数排序,前面介绍的几种排序方法都是按数据元素（或记录关键字）值的大小进行排序的 多关键字排序是一种按组成数据元素或关键字的各位值进行排序的方法，基数排序借助的就是这种思想。基数排序属于分布式排序，也称口袋排序、“桶子法”。基数排序法是属于稳定性的排序时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。,基数排序的方式可以采用：LSD（Least significant digital）的排序方式由键值的最右边开始MSD（Most significant digital）由键值的最左边开始。以LSD为例，假设原来有一串数值如下所示：73,22,93,43,55,14,28,65,39,81,73,22,93,43,55,14,28,65,39,81,首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中；接下来将这些桶子中的数值重新串接起来，成为以下的数列：,81,22,73,93,43,14,55,65,28,39,81,22,73,93,43,14,55,65,28,39,接着再进行一次分配，这次是根据十位数来分配：接下来将这些桶子中的数值重新串接起来，成为以下的数列：整个数列已经排序完毕。,14,22,28,39,43,55,65,73,81,93,如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好；MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。,基数排序,排序前先将待排序元素置于一数组 r1rn中存储，每个结点除存放排序码的值外，还有一个指向下一个结点的指针（即下一个结点的下标值）排序时从最低位kd开始，直到最高位k1，把关键字依其子关键字的值分配到rd个队列中去，同一队列中的元素用指针链接，同时队头和队尾各用一个指针指示，该头、尾指针分别存放在两个数组 fra1fra2和era1era2中（ra1和ra2为子关键字ki的取值范围）每经过一次分配后，都将各队列中的元素按次序收集在一起，经过d次的分配和收集后即得到了按序排列的序列,基数排序,例如，若关键字是十进制数值，将全部数据放在数组r中，然后按下列步骤进行：（1）初态：设置10个队列，并且使其均为空。（2）分配：依次从数组r中取出每个关键字，第i遍处理时，考察该关键字右起第i位数字（即第i个子关键字），设其值位k，则把该关键字插入第k个队列。数组r全部处理完后，全部数据被分配到队列0队列9。（3）收集：从队列0开始，依队列0队列9的头、尾指针，修改数组r中各关键字的指针，即将这次分配完的关键字依逻辑次序再链接起来。（4）循环：重复以上（1）（3）步，若关键字有d位数字，就需要执行d遍。,基数排序,考察由3位十进制数字组成的关键字，则其值在0k999范围内。可把每一个十进制数看成一个逻辑关键字k，k由三个子关键字（k1、k2、k3）组成，其中k1是百位数，k2是十位数，k3是个位数，由此分解得到的每个关键字ki都在相同的范围内（0ki9）。排序是先从最低位k3开始，按k3的大小分成若干组，每组中k3值相同，然后将各组数据收集在一起；下次再按k2大小排序，如此重复，直到对k1排序后，整个数据集即成为有序序列。,基数排序,例1.22 基数排序过程的程序 设有10个十进制数：179、208、234、056、800、178、651、245、006、958，该数列数值范围在0999之间，因此子关键字位数d3，个位数为低关键字位，百位数为高关键字位，关键字值得范围为09，基数为10。进行基数排序过程如图1.61所示。,r1 r2 r3 r4 r5 r6 r7 r8 r9 r10179208234056800178651245006958（a）初始状态,（b）按最低关键字位值分配,800651234245056006208178958179（c）第一次收集,（d）按次低关键字位值分配,800006208234245651056958178179（e）第二次收集,（f）按最高关键字位值分配,006056178179208234245651800958（g）第三次收集后得排序结果图 1.61 基数排序示例,基数排序的程序：#include stdio.h#define ra1 0#define ra2 9#define d 3#define n 10 int keyval;/*ra1=keyval=ra2*/int pn;/*1=pn=n*/struct rnode int key4;/*keyval*/int next;/*0=next=n*/;struct rnode rn+1;,int rsort(r)struct rnode rn+1;int j,k,t,i;int f10,e10;/*0.9*/int p;p=1;for(i=d;i=1;i-)for(j=ra1;j=ra2;j+)fj=0;/*头指针初始化*/while(p!=0)/*分配*/k=rp.keyi;if(fk=0)fk=p;else rek.next=p;ek=p;p=rp.next;j=0;/*收集*/while(fj=0)j=j+1;p=fj;t=ej;while(jra2)j=j+1;if(fj!=0)rt.next=fj;t=ej;rt.next=0;return(p);,main()int p;int i,j;printf(请输入数据：);for(i=1;i=n;i+)for(j=1;j=3;j+)scanf(%d,基数排序,运行结果：请输入数据：1 7 9 2 2 0 8 3 2 3 4 4 0 5 6 5 8 0 0 6 1 7 8 7 6 5 1 8 2 4 5 9 0 0 6 10 9 5 8 01 7 9 2|2 0 8 3|2 3 4 4|0 5 6 5|8 0 0 6|1 7 8 7|6 5 1 8|2 4 5 9|0 0 6 10|9 5 8 0|排序后的数据:006 056 178 179 208 234 245 651 800 958,基数排序的算法分析,从程序中可以看出：对有n个元素的序列，对一个关键字位，“分配”数据的循环需执行n次，“收集”的循环需执行rd次，因此一次分配和收集共执行n+rd次；有d个关键字位又需要重复d次“分配”和“收集”。所以基数排序的时间复杂度为(d*(n+rd)。,归并排序又称为表排序，其含义是将两个有序序列合并成为一个有序序列。1、基本思想 设待排序序列有n个记录，开始将其看作是n个长度为1 的有序子文件，然后进行归并，将相邻的有序子文件两两合并，得到n/2个长度为2或1的有序子文件(如果n为奇数，则最后一个有序子文件的长度为1)，再两两归并得到n/4个有序子文件，以此类推，直至得到长为n的有序文件。该有序序列就是原始序列经归并排序后的有序序列。在排序过程中，子序列总是两两归并，所以归并排序又被称为二路归并排序。,六、归并排序,例如对序列16，31，9，15，87，76，13，24，43进行二路归并排序过程为：,2、二路归并的算法 在编写程序实现时，实际上是把两个长度为k的有序序列连接合并成一个长度为2k的有序序列。可利用三个指针分别指向三个序列的第一个元素，将两个序列的第一个元素进行比较，取出关键字较小者作为结果序列的第一个元素，将较小者所在序列及结果序列的指针后移，继续比较和加入。最后当两个序列之一的所有元素都取完时，再将另一序列的剩余元素顺序复制到结果序列中，完成归并。,void merge(r,r1,low,mid,high)/rlow到rmid与rmid+1到rhigh是两个有序子文件/本算法将其归并成一个有序子文件从r1low到r1high rectype r,r1;int low,mid,high;int i=low;j=mid+1;k=low;while(i=mid)/复制第二个文件剩余记录,void mergepass(r,r1,length)/对r进行一趟归并，结果放在r1中rectype r,r1;int length;/length是本趟归并的有序子文件的长度int i=0,j;/指向第一对子文件起始点 while(i+2*length=n)merge(r,r1,i,i+length-1,i+2*length-1)i=i+2*length/指向下一对子文件起始点 if(i+leng-1n-1)/剩下两个子文件，其中一个长度小于length merge(r,r1,i,i+length-1,n-1);else/子文件个数为奇数，将最后一个子文件复制到r1中 for(j=i;jn;j+)r1j=rj;,void mergesort(r)rectype r;int length=1;while(lengthn)mergepass(r,r1,length);/一趟归并，结果在r1中 length=2*length;/区间扩大一倍mergepass(r1,r,length);/再次归并，结果在r中 lenth=2*length;,3、二路归并的算法分析 第i趟排序后，有序子文件长度为2i，具有那个记录的文件排序，必须做log2n趟归并，每趟所花时间为O(0)，所以二路归并排序的时间复杂度为O(nlog2n)，所需的空间为O(0)。,