数据结构课程讲义8ppt课件.ppt

《数据结构课程讲义8ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构课程讲义8ppt课件.ppt（106页珍藏版）》请在三一办公上搜索。

1、第八章 排序,概述 插入排序 交换排序 选择排序 归并排序 分配排序 外排序,1 内排序(Sorting)？,简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。排序是计算机中经常遇到的操作，通常称为分类或整序。,排序的几个基本概念,数据表(Data List)待排序的数据对象的有限集合。关键字(Key)作为排序依据的数据对象中的属性域。主关键字 不同的数据对象若关键字互不相同，则这种关键字称为主关键字。排序的确切定义 使一组任意排列的对象变成一组按关键字线性有序的对象。用于排序测度的关键字通常称为排序码。,排序的几个基本概念,排序算法的稳定性 判断标准：排序码相同的数据

2、对象在排序过程中是否保持前后次序不变。如 2,2*,1，排序后若为1,2*,2 则该排序方法是不稳定的。内排序与外排序 区分标准：排序过程是否全部在内存进行。排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。,排序的方法有很多，但简单地判断那一种算 法最好，以便能够普遍选用则是困难的。评价排序算法好坏的标准主要有两条：算法 执行所需要的时间和所需要的附加空间。另外，算法本身的复杂程度也是需要考虑 的一个因素。排序算法所需要的附加空间一般都不大，矛 盾并不突出。而排序是一种经常执行的一 种运算，往往属于系统的核心部分，因此 排序的时间开销是算法好

3、坏的最重要的标 志。,排序亦称分类，是计算机进行数据处理的一种基本运算，其功能是将一个数据元素的无序序列调整为一个有序序列。目的是达到当计算机中的数据经过排序后，提高工作效率和质量。是在线性表上施加的操作。排序码就是指作为排序依据的数据项。数据元素可以有多个排序码。排序的精确定义：有n个记录（元素）：R1，R2，R3，Rn 及其对应的排序码序列：K1，K2，K3，Kn,所确定的1，2，.n的一种排列p1,p2,p3,pn，使得相应的排序码满足非递减（或非递增）关系：Kp1Kp2Kp3Kpn 或 Kp1Kp2Kp3Kpn 即成为：Rp1,Rp2,Rp3,Rpn 自然，不同的排序策略就得到不同的排

4、序过程；策略相同但排序所采用的排序方法不同，都会有不同的排序算法。常见的排序策略和方法有：,直接插入排序 shell插入排序（缩小增量排序）插入策略 二分插入排序 表插入排序 直接交换排序（冒泡排序）交换策略 快速排序 直接选择排序 选择策略 堆排序 归并策略 分配策略 基数排序,为简单起见，数据的存储结构采用记录数组形式。记录数组的类型说明如下：,typedef struct keytype key;datatype other;rectype;rectype Rn;,其中n为记录总数加1,2 插入排序,基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置

5、上，直到对象全部插入为止。,直接插入排序(Insert Sort)希尔排序(Shell Sort),2.1 直接插入排序(Insert Sort),基本思想：当插入第i个对象时，前面的V0,V1,Vi-1已经排好序，此时，用vi的关键字与Vi-1,Vi-2,的关键字顺序进行比较，找到插入位置即将Vi插入，原来位置上对象向后顺移。,直接插入排序举例,i(0)(1)(2)(3)(4)(5)temp 21 25 49 25*16 08 251 21 25 49 25*16 08 492 21 25 49 25*16 08 25*3 21 25 25*49 16 08 164 16 21 25 25*

6、49 08 08 5 08 16 21 25 25*49,直接插入排序算法INSERTSORT(rectype R)int i,j;for(i=1;i=0,算法中引入附加记录temp的作用：是进入查找循环之前，它保存了Ri的副本，使得不至于因记录的后移而丢失Ri中的内容。,算法分析,直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的比较次数为2(n-1)。若初始时关键字递

7、减有序，这是最坏情况。这时的记录比较和移动次数分别为：,直接插入排序的稳定性,直接插入排序是一种稳定的排序方法。原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。,2.2 希尔(shell)排序,1959年由D.L.Shell提出，又称缩小增量排序(Diminishing-increment sort)。基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。,希尔排序的基本过程,设待排序的对象序列有n个对象，首先取一个整数gapn作为间隔，将全部对象

8、分为gap个子序列，所有距离为gap的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔gap，如取gap=gap/2，重复上述的子序列划分和排序工作，直到最后取gap为1为止。,希尔排序示例,i(0)(1)(2)(3)(4)(5)gap 21 25 49 25*16 08 1 21-25*3 25-16 49-08 21 16 08 25*25 492 21-08-25 2 16-25*-49 08 16 21 25*25 493 08 16 21 25*25 49 1 08 16 21 25*25 49,希尔排序算法rectype Rn+d1;int dt;SHELL

9、SORT(rectype R,int d)int i,j,k,h;rectype temp;k0;dl=1;,do hdk;for(i=h+dl;in+dl;i+)tempRi;ji-h;while(temp.keyRj.key)pj+hRj;jj-h;Rj+htemp;k+;while(h!=1);,为什么shell排序的时间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开

10、始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。,希尔排序中gap的取法,Shell最初的方案是 gap=n/2,gap=gap/2，直到gap=1.Knuth的方案是gap=gap/3+1其它方案有：都取奇数为好；或gap互质为好等等。,希尔排序的时间复杂度,对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到。Knuth的统计结论是，平

11、均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。,希尔排序的稳定性,希尔排序是一种不稳定的排序方法。如序列 3 2 2*5,3 交换排序,两种常见的交换排序,冒泡排序(Bubble Sort)快速排序(Quick Sort),基本原理：每一次两两比较待排序的记录的排序码，只要是逆序的记录对，则进行交换，直到所有的逆序对都交换完为止。,冒泡排序的基本思想,首先依序比较n个待排序记录的一端开始，依次两两比较排序码，只要是逆序，则交换，这样完成一趟交换排序，结果就是将最大（或最小）的记录交换到最后面（或最前面）；然后其余的记录同法进行两两比较，每一趟都将较大（小）元素交换到最后（前

12、）面，一直进行下去，直到最后一个记录排完或没有要交换的元素的时候为止。,3.1 冒泡排序,冒泡排序的基本过程,首先从R0到Rn-1对n个元素比较其排序码，对逆序元素进行交换，完成一趟排序时，将排序码值最到的元素几交换到最后一个位置，即Rn-1，该过程相当于一趟冒泡；然后，又从R0到Rn-2中又进行一趟交换冒泡，这样一直进行下去，直到最后一个元素R0或某一趟没有交换元素为止。,3.1，冒泡排序,冒泡排序示例,i(0)(1)(2)(3)(4)(5)21 25 49 25*16 08 1 08 21 25 49 25*16 2 08 16 21 25 49 25*3 08 16 21 25 25*4

13、9 4 08 16 21 25 25*49,冒泡排序算法void bubblesort(R)for(i=0;i=i;j+)if(Rj+1.keyRj.key)t=Rj+1;Rj+1=Rj;Rj=t;Flag=0;if(flag)break;,冒泡排序的时间复杂度,考虑关键字的比较次数和对象移动次数1、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为n-1，没有记录移动。2、若初始状态是反序的，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：,冒泡排序方法是稳定的。,快速排序的基本思想,在当前无序

14、区Rl到Rh任意取出一个元素作为比较的“基准”，以此为基准将当前的无序序列划分为两个部分：一部分元素中所有的元素排序码都小于基准元素；另一部分元素中所有的元素排序码都大于基准元素，则基准元素所在的位置就是该元素排序的最终位置；然后同法依次对两部分元素进行分划，继续进行下去，直到得到一个有序序列为止。,3.2 快速排序,快速排序的过程,设置两个指示器i和j,其初值分别为i=l,j=h.不妨取第一个元素Ri(=Rl)为基准，并将其保存于变量x中。令j从h开始往前扫描，直到找到第一个排序码值小于x的排序码值的时候的记录Rj,则将其移动到I的位置上（即相当于将比基准小的元素移动到左边）；然后，令i自i

15、+1起往后扫描，直到找到第一个排序码值大于x的排序码值的时候的记录Ri,则将其移动到j的位置上（即相当于将比基准大的元素移动到右边）；接着，又令j从j-1开始往前扫描、重复上述交替改变扫描方向，从两端各自向中间靠拢，直到i=j时，便是基准x最终的位置，将其放在此位置上就完成了一次划分。,3.2 快速排序,快速排序示例,49,38,65,97,76,13,27,49,38,65,97,76,13,27,49,27,38,65,97,76,13,49,49,38,97,76,13,65,49,49,38,13,97,76,65,49,49,38,13,76,97,65,49,49,38,13,49

16、,76,49,65,49,49,temp,快速排序算法int PARTITION(rectype R,int l,int h)int i,j;rectype temp;i=l;j=h;temp=Ri;do while(Rj.key=temp.key),QUICKSORT(rectype R,int s1,int t1)int i;if(s1t1)i=PARTITION(R,s1,t1);QUICKSORT(R,s1,i-1);QUICKSORT(R,i+1,t1);,快速排序的时间复杂度,2、最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等

17、。,考虑关键字的比较次数和对象移动次数1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为,设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k，k=log2n，因此有：,快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(n

18、log2n)。可以证明，快速排序的平均时间复杂度也是O(nlog2n)。快速排序是不稳定的排序方法。,4 选择排序,两种常见的选择排序,直接选择排序堆排序,基本原理:将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。,直接选择排序的基本思想,在所有的记录中选择出排序码最小的记录，将其与第一个元素交换；然后其余的记录中选择出次小的记录与第二个元素交换，一直进行下去；直到最后一个记录排完为止。,4.1 直接选择排序,直接选择排序过程,首先从R0到Rn-1中选择出最小的记录，将其与R0交换；然后，又从R1到Rn-1中选择出最小的记录与R1交换；这样

19、，当第i趟时从R0到Ri-1 就是已经排好序的，直到最后一个元素Rn-1排好为止。,4.1 直接选择排序,直接选择排序示例,49,38,65,97,76,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,直接选择排序算法SELECTSORT(rectype R)int i,j,k;rectype

20、 temp;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(Rj.keyRk.key)k=j;if(k!=i)temp=Ri;Ri=Rk;Rk=temp;,直接选择排序的时间复杂度,2.当文件为正序时，移动次数为0，文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。直接选择排序是不稳定的排序方法。,1、无论初始状态如何，在第i 趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：,4.2 堆排序,由于直接选择排序的过程中，每趟选择过程中所进行的比较，都没有进行保留，从而导致了排序效率低下。于是引入树形结构的排序。,堆排序

21、的引入,4.2 堆排序,就是树形结构的排序。也就是体育比赛中的锦标赛方式。其排序方法如下：首先对n个记录的排序码进行两两比较，得到n/2个较小元素，然后再将其进行两两比较，得到n/4个较小元素，依此进行下去，直到找到最小排序码的元素为止，则即完成一趟选择，同法，每趟选择都选择出最小的元素，直到最后一个元素时为止，即完成了排序。,1、锦标赛排序,4.2 堆排序,显然，为了保存每次比较的结果，都不得不需要大量的辅助存储空间，于是为了弥补这个缺陷，1964年由Willioms提出了只需要一个辅助存储空间即可完成的堆排序。,1、锦标赛排序,4.2 堆排序,堆的定义：n个元素序列所对应的排序码序列K1,

22、K2,K3,Kn,当且仅当 Ki K2i Ki K2i+1 或 Ki K2i Ki K2i+1,2、堆排序,4.2 堆排序,称为小根堆（大根堆）。由此，若序列K1,K2,K3,Kn是小根堆，则堆顶元素（即为完全二叉树的根）必为序列中所有元素的最小（最大）值。,2、堆排序,4.2 堆排序,每次在得到一个堆之后，输出堆顶元素后，使得剩余的n-1个元素的序列再建成一个堆，则得到n个元素的次小元素。继续进行下去，直到得到一个有序序列为止。由此可见：实现堆排序需要解决两个问题：,堆排序基本思想,4.2 堆排序,（1）怎样由一个无序的序列建立一个堆；（2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆

23、。,堆排序基本思想,4.2 堆排序,对于第二个问题，在堆一个堆输出堆顶元素之后，而且用最后一个元素代替后，就会破坏堆的特性，故需要进行适当的调整。根据堆的定义，只需要依次与左右孩子进行比较，将左右孩子中较小者与其根结点进行交换，也就相当于将根结点往下“筛”，直到每一棵子树都是小根堆为止。,堆排序基本思想,4.2 堆排序,对于第一个问题，从一个无序的序列建立成堆的过程是一个反复“筛选”过程。若将此序列组织成为一棵完全二叉树，则最后一个非叶子结点就是第n/2个元素。因此我们的筛选建堆的过程只需要从第n/2处开始。循环到根结点时，调整之后的二叉树就是所有元素构成的小根堆。,堆排序基本思想,10,15

24、,56,25,30,70,10,15,56,25,30,70,小根堆示例,70,56,30,25,15,10,70,56,30,25,15,10,大根堆示例,可见：堆排序的第一个工作是建堆，即把整个记录数组R1到Rn调整为一个堆。显然,只有一个结点的树是堆，而在完全二叉树中，所有序号i=low(n/2)的结点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序号为low(n/2)，low(n/2)-1，.，1的结点作为根的子树都调整为堆即可。我们以大根堆为例进行说明,若已知结点Ri的左右子树已是堆，如何将以Ri为根的完全二叉树也调整为堆？解决这一问题可采用“筛选法”，其基本思想是

25、：因为Ri的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必须在Ri和它的左右孩子中选取关键字最大的结点放到Ri的位置上。若Ri的关键字已是三者中的最大者，则无须做任何调整，以Ri为根的子树已构成堆，否则必须将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。假定R2i的关键字最大，将Ri和R2i交换位置，交换之后有可能导致R2i为根的子树不再是堆，但由于R2i的左右子树仍然是堆，于是可以重复上述过程，将以R2i为根的子树调整为堆，.，如此逐层递推下去，最多可能调整到树叶。,例子：关键字序列为 42，13，91，23，24，16，05，88，n=8，故从第

26、四个结点开始调整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不调整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,筛选算法SIFT(rectype R,int i;int m)int j;recty

27、pe temp;temp=Ri;j=2*i;while(j=m)if(jm),上述算法只是对一个指定的结点进行调整。有了这个算法，则将初始的无序区R1到Rn建成一个大根堆，可用以下语句实现：,for(i=n/2;i=1;i-)SIFT(R,i,n),由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将R1和Rn交换，这就得到了第一趟排序的结果。第二趟排序的操作首先是将无序区R1到Rn-1调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用SIFT函数将R1到Rn-1调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录Rn-1交

28、换，如此反复进行下去。,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（a）初始堆R1到R8,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（b）第一趟排序之后,（c）重建的堆R1到R7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（d）第二趟排序之后,（e）重建的堆R1到R6,42,24,16,23,13,05,88,91,42,24,16,23,

29、13,05,88,91,（f）第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,（g）重建的堆R1到R5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,（h）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,（i）重建的堆R1到R4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,（j）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,2

30、4,42,88,91,（k）重建的堆R1到R3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,（l）第六趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（m）重建的堆R1到R2,13,05,16,23,24,42,88,91,13,05,16,23,24,42,88,91,（n）第七趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,堆排序算法HEAPSORT(rectype R)int i;rectype temp;for(i=

31、n/2;i=1;i-)SIFT(R,i,n);for(i=n;i=1;i-)temp=R1;R1=Ri;Ri=temp;SIFT(R,1,i-1);,堆排序的时间复杂度,堆排序的时间复杂性为O(n log2n)空间复杂性为 O(1)堆排序是不稳定的排序方法。,5 归并排序,基本原理，通过对两个有序结点序列的合并来实现排序。所谓归并是指将若干个已排好序的部分合并成一个有序的部分。,两路归并的基本思想,归并排序是利用“归并”技术来进行排序，所谓归并是指将若干个已经排序的子序列合并为一个有序序列。其算法比较简单，可以直接给出。,两路归并的示例,25 57 48 37 12 92 86,25 57 3

32、7 48 92 12 86,25 37 48 57 12 86 92,12 25 37 48 57 86 92,归并算法void merge(R,R1,low,mid,hign)/Rlow到Rmid与Rmid+1到Rhigh是两个有序序列，结果是合并为一个有序序列R1low到R1high/i=low;j=mid+1;k=low;while(i=mid,归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序列R0到Rn-1看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。然后再把这high(n/2)个有序的子序列两两归并，如此反复，直到最后得到一

33、个长度为n的有序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还可以有“三路归并”或“多路归并”。,归并过程示例,(25)(57)(48)(37)(12)(92)(86),(25 57)(37 48)(12 92)(86),(25 37 48 57)(12 86 92),(12 25 37 48 57 86 92),一趟归并算法归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序的记录序列R0到Rn-1看成为n个长度为1的有序序列，将其进行两两归并，则得到n/2个（n为基数时候则为（n+1）/2个）长度为2的有序序列，然后继续进行，直到最后得到

34、一个长度为n的有序序列为止。这就是2-路归并排序。其中，最关键的是将两个长度为l的有序序列归并为长度为2l的有序序列。,一趟归并算法MERGEPASS(rectype R,rectype R1,int length)int i,j;i=0;while(i+2*length-1n)MERGE(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;if(i+length-1n-1)MERGE(R,R1,i,i+length-1,n-1);else for(j=i;jn;j+)R1j=Rj;,在上述一趟归并过程中，如果正好配成对时候，即可正常完成，否则最后一次归并

35、时，可能有两种情况：（1）(2k+1)*lenn2(k+1)*len 表示有两个有序序列，但后一个长度不足len，此时归并方法与前相同，仅仅是参数不同而已。（2）2k*lenn2(k+1)*len 表示只有一个有序序列，此时已经是有序的，故只需要复制到R1中即可。,归并排序就是从长度为1的有序序列逐渐归并为长度为2，4，,n的循环过程。,归并排序算法MERGESORT(rectype R)int length=1;while(lengthn)MERGEPASS(R,R1,length);length=2*length;MERGEPASS(R1,R,length);length=2*length

36、;,算法复杂性分析,归并排序是稳定的排序方法。,归并排序在第i 趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做high(log2n)趟归并，每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。,6 基数排序,基本原理，采用“分配”和“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。下面先介绍多关键字排序,多关键字排序方法示例,如对扑克牌的排序每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。对以上排序，可以先对花色排序，或先对面值排序。,多关键字有序的概念,考虑对象序

37、列V0,V1,.,Vn-1，每个对象Vi含d个关键字(Ki1,Ki2,.,Kid)。若对序列中的任意两个对象Vi和Vj都有(Ki1,Ki2,.,Kid)(Kj1,Kj2,.,Kjd)则称序列对关键字(Ki1,Ki2,.,Kid)有序，且K1称为最高位关键字，Kd称为最低位关键字。,多关键字排序,原理：根据组成关键字的各位的值进行排序。实现基数排序的两种方法：1 最高位优先(MSD)排序：从关键 字的高位到低位 2 最低位优先(LSD)排序：从关键字 的低位到高位MSD方法通常是一个递归的过程。,多关键字排序（续）,LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一

38、个子关键字组：(Ki1,Ki2,.,Kid)如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3,K2,K1的顺序对所有对象排序。,链式的基数排序,基数排序是一种典型的LSD排序方法，它利用“分配”和“收集”两种运算对单关键字进行排序。此时可将单关键字K看成是一个子关键字组：(Ki1,Ki2,.,Kid)排序过程：设关键字共有d位，让j=d,d-1,.,1,依次执行d次“分配”与“收集”。,179,208,306,93,859,984,55,9,271,33,B0.f B1.f B2.f B3.f B4

39、.f B5.f B6.f B7.f B8.f B9.f,B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e,271,93,33,984,55,306,208,179,859,9,271,93,33,984,55,306,208,179,859,9,B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f,B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e,33,984,306,208,9,55,859,271,179,93,306,208,9,33,55,8

40、59,271,179,984,93,B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f,B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e,179,306,984,859,9,33,55,93,208,271,9,33,55,93,179,208,271,306,859,984,分配排序算法typedef struct int keyd;int next;datatype other;rectype;rectype Rn;typedef struct int f,e;queue;queue Bm;,

41、while(p!=-1)k=Rp.keyj;if(Bk.f=-1)Bk.f=p;else RBk.e.next=p;Bk.e=p;p=Rp.next;i=0;while(Bi.f=-1)i+;t=Bi.e;p=Bi.f;while(im-1)i+;if(Bi.f!=-1)Rt.next=Bi.f;t=Bi.e;Rt.next=-1;return p;,int RADIXSORT(rectype R)int i,j,k,t,p;for(i=0;i=0;j-)for(i=0;im;i+)Bi.f=-1;Bi.e=-1;/初始化每趟分配前的所有队列空/,CH7 内排序,直接插入排序 shell插入排序（缩小增量排序）插入策略 二分插入排序 表插入排序 直接交换排序（冒泡排序）交换策略 快速排序 直接选择排序 选择策略 堆排序 归并策略 分配策略 基数排序,内部排序方法的比较和选择,选取排序方法时需要考虑的因素有：待排序的记录数目 记录本身信息量的大小 关键字的结构及其分布情况 对排序稳定性的要求 语言工具的条件、辅助空间的大小,外部排序简介,如果待排序的记录数很大，无法将所有记录都调入内存，只能将它们存放在外存上，我们称这时的排序为外部排序。外部排序的实现，主要是依靠数据的内外存交换和“内部归并”。,