《数据结构课程讲义8ppt课件》由会员分享，可在线阅读，更多相关《数据结构课程讲义8ppt课件（106页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程讲义8ppt课件Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望1内排序内排序 (Sorting)？简单地说，排序就是将一组杂乱无章的数简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。据按一定的规律排列起来（递增或递减）。排序是计算机中经常遇到的操作，通常称排序是计算机中经常遇到的操作，通常称为分类或整序。为分类或整序。排序的几个基本概念排序的几个基本概念数据表数据表数据表数据表(Data List)(Data List)(Data List)(
2、Data List) 待排序的数据对象的有限集待排序的数据对象的有限集待排序的数据对象的有限集待排序的数据对象的有限集合。合。合。合。关键字关键字关键字关键字(Key)(Key) 作为排序依据的数据对象中的属性作为排序依据的数据对象中的属性作为排序依据的数据对象中的属性作为排序依据的数据对象中的属性域。域。域。域。主关键字主关键字主关键字主关键字 不同的数据对象若不同的数据对象若不同的数据对象若不同的数据对象若关键字互不相同关键字互不相同关键字互不相同关键字互不相同，则这种关键字称为主关键字。则这种关键字称为主关键字。则这种关键字称为主关键字。则这种关键字称为主关键字。排序的确切定义排序的确切
3、定义 使一组任意排列的对象变成使一组任意排列的对象变成使一组任意排列的对象变成使一组任意排列的对象变成一组一组一组一组按关键字线性有序按关键字线性有序按关键字线性有序按关键字线性有序的对象。的对象。的对象。的对象。用于排序测度的关键字通常称为排序码。用于排序测度的关键字通常称为排序码。用于排序测度的关键字通常称为排序码。用于排序测度的关键字通常称为排序码。排序的几个基本概念排序的几个基本概念排序算法的稳定性排序算法的稳定性排序算法的稳定性排序算法的稳定性 判断标准：排序码相同的数据判断标准：排序码相同的数据判断标准：排序码相同的数据判断标准：排序码相同的数据对象在排序过程中是否保持前后次序不变
4、。如对象在排序过程中是否保持前后次序不变。如对象在排序过程中是否保持前后次序不变。如对象在排序过程中是否保持前后次序不变。如 2, 2, 2*,12*,1，排序后若为，排序后若为，排序后若为，排序后若为1, 2*, 2 1, 2*, 2 则该排序方法是不稳定的。则该排序方法是不稳定的。则该排序方法是不稳定的。则该排序方法是不稳定的。内排序内排序内排序内排序与外排序与外排序 区分标准：区分标准：排序过程是否全部排序过程是否全部排序过程是否全部排序过程是否全部在在在在内存内存内存内存进行。进行。进行。进行。排序的时间开销排序的时间开销排序的时间开销排序的时间开销 它是衡量算法好坏的最重要的标它是衡
5、量算法好坏的最重要的标它是衡量算法好坏的最重要的标它是衡量算法好坏的最重要的标志。通常用算法执行中的志。通常用算法执行中的志。通常用算法执行中的志。通常用算法执行中的数据比较次数数据比较次数数据比较次数数据比较次数和和和和数据移动数据移动数据移动数据移动次数次数次数次数来衡量。来衡量。来衡量。来衡量。 排序的方法有很多，但简单地判断那一种算排序的方法有很多，但简单地判断那一种算 法最好，以便能够普遍选用则是困难的。法最好，以便能够普遍选用则是困难的。 评价排序算法好坏的标准主要有两条：算法评价排序算法好坏的标准主要有两条：算法 执行所需要的时间和所需要的附加空间。执行所需要的时间和所需要的附加
6、空间。 另外，算法本身的复杂程度也是需要考虑另外，算法本身的复杂程度也是需要考虑 的一个因素。的一个因素。 排序算法所需要的附加空间一般都不大，矛排序算法所需要的附加空间一般都不大，矛 盾并不突出。而排序是一种经常执行的一盾并不突出。而排序是一种经常执行的一 种运算，往往属于系统的核心部分，因此种运算，往往属于系统的核心部分，因此 排序的时间开销是算法好坏的最重要的标排序的时间开销是算法好坏的最重要的标 志。志。排排序序亦亦称称分分类类，是是计计算算机机进进行行数数据据处处理理的的一一种种基基本本运运算算，其其功功能能是是将将一一个个数数据据元元素素的的无无序序序序列列调调整整为为一一个个有有
7、序序序序列列。目目的的是是达达到到当当计计算算机机中中的的数数据据经经过过排排序序后后，提提高高工工作作效效率率和质量。是在线性表上施加的操作。和质量。是在线性表上施加的操作。排排序序码码就就是是指指作作为为排排序序依依据据的的数数据据项项。数数据元素可以有多个排序码。据元素可以有多个排序码。排序的精确定义：排序的精确定义：有有n个记录（元素）：个记录（元素）：R1，R2，R3，Rn及其对应的排序码序列：及其对应的排序码序列：K1，K2，K3，Kn所所确确定定的的1，2，.n的的一一种种排排列列p1,p2,p3,pn，使使得得相相应应的的排排序序码码满满足非递减（或非递增）关系：足非递减（或非
8、递增）关系：Kp1Kp2Kp3Kpn或或Kp1Kp2Kp3Kpn即成为即成为：Rp1,Rp2,Rp3,Rpn自自然然，不不同同的的排排序序策策略略就就得得到到不不同同的的排序过程；排序过程；策策略略相相同同但但排排序序所所采采用用的的排排序序方方法法不不同，都会有不同的排序算法。同，都会有不同的排序算法。常见的排序策略和方法有：常见的排序策略和方法有：直接插入排序直接插入排序shell插入排序（缩小增量排序）插入排序（缩小增量排序）插入策略插入策略二分插入排序二分插入排序表插入排序表插入排序直接交换排序（冒泡排序）直接交换排序（冒泡排序）交换策略交换策略快速排序快速排序直接选择排序直接选择排序
9、选择策略选择策略堆排序堆排序归并策略归并策略分配策略分配策略基数排序基数排序 为简单起见，数据的存储结构采用记为简单起见，数据的存储结构采用记录数组形式。记录数组的类型说明如下：录数组形式。记录数组的类型说明如下：typedef struct typedef struct keytype key; keytype key; datatype other; datatype other; rectype; rectype;rectype Rn;rectype Rn; 其中其中n为记录总数加为记录总数加12插入排序插入排序 基本原理，每步将一个待排序的基本原理，每步将一个待排序的对象，按其关键字大
10、小，插入到前面对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，已经排好序的一组对象适当位置上，直到对象全部插入为止。直到对象全部插入为止。直接插入排序直接插入排序(InsertSort)希尔排序希尔排序(ShellSort)2.1 直接插入排序直接插入排序(Insert Sort) 基本思想：当插入第基本思想：当插入第i个对象时，个对象时，前面的前面的V0,V1,Vi-1已经排好序，已经排好序，此时，用此时，用vi的关键字与的关键字与Vi-1, Vi-2,的关键字顺序进行比较，找到插的关键字顺序进行比较，找到插入位置即将入位置即将Vi插入，原来位置上对插入，原来位置上对象向后顺
11、移。象向后顺移。直接插入排序举例直接插入排序举例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* 49 08 08 5 08 16 21 25 25* 49 直接插入排序算法直接插入排序算法INSERTSORT(rectype R)INSERTSORT(rectype R)INSERTSORT(rectype R)INSERTSORT(rectype R) int i,j;
12、int i,j;int i,j;int i,j; for (i=1;in;i+) for (i=1;in;i+) for (i=1;in;i+) for (i=1;i=0&temp.key=0&temp.key=0&temp.key=0&temp.keyRj.key) Rj+1 Rj+1 Rj+1 Rj+1Rj;j+;Rj;j+;Rj;j+;Rj;j+; Rj+1 Rj+1 Rj+1 Rj+1temp; temp; temp; temp; 算法中引入附加记录算法中引入附加记录temp的作用：是进入的作用：是进入查找循环之前，它保存了查找循环之前，它保存了Ri的副本，使得的副本，使得不至于因记录
13、的后移而丢失不至于因记录的后移而丢失Ri中的内容。中的内容。算法分析算法分析直接插入排序算法由两重循环组成，对于有直接插入排序算法由两重循环组成，对于有直接插入排序算法由两重循环组成，对于有直接插入排序算法由两重循环组成，对于有n n个记录的排序，内循环表明完成一趟排序所需个记录的排序，内循环表明完成一趟排序所需个记录的排序，内循环表明完成一趟排序所需个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。进行的记录关键字间的比较和记录的后移。进行的记录关键字间的比较和记录的后移。进行的记录关键字间的比较和记录的后移。若初始时关键字递增有序，这是最好情况。每若初始时关键字
14、递增有序，这是最好情况。每若初始时关键字递增有序，这是最好情况。每若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以一趟排序中仅需进行一次关键字的比较，所以一趟排序中仅需进行一次关键字的比较，所以一趟排序中仅需进行一次关键字的比较，所以总的比较次数为总的比较次数为总的比较次数为总的比较次数为n-1n-1。在。在。在。在whilewhile循环之前和之中，循环之前和之中，循环之前和之中，循环之前和之中，至少要移动记录两次，所以总的比较次数为至少要移动记录两次，所以总的比较次数为至少要移动记录两次，所以总的比较次数为至少要移动记录两次，所以总的比较次数为2(n-1)2
15、(n-1)。若初始时关键字递减有序，这是最坏情况。这若初始时关键字递减有序，这是最坏情况。这若初始时关键字递减有序，这是最坏情况。这若初始时关键字递减有序，这是最坏情况。这时的记录比较和移动次数分别为：时的记录比较和移动次数分别为：时的记录比较和移动次数分别为：时的记录比较和移动次数分别为：直接插入排序的稳定性直接插入排序的稳定性直接插入排序是一种稳定的排序方直接插入排序是一种稳定的排序方法。法。原理：关键字相同的两个对象，在原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而整个排序过程中，不会通过比较而相互交换。相互交换。2.2 希尔希尔(shell)排序排序1959年由年由D.L
16、. Shell提出，又称缩小提出，又称缩小增量排序增量排序(Diminishing-increment sort) 。基本思想：在插入排序中，只比较相基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就后能够一次跨过较大的距离，这样就可以提高排序的速度。可以提高排序的速度。希尔排序的基本过程希尔排序的基本过程 设待排序的对象序列有设待排序的对象序列有n个对象，个对象，首先取一个整数首先取一个整
17、数gapn作为间隔，将全作为间隔，将全部对象分为部对象分为gap个子序列，所有距离为个子序列，所有距离为gap的对象放在同一个序列中，在每一的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然个子序列中分别施行直接插入排序，然后缩小间隔后缩小间隔gap，如取，如取gap=gap/2，重，重复上述的子序列划分和排序工作，直到复上述的子序列划分和排序工作，直到最后取最后取gap为为1为止。为止。希尔排序示例希尔排序示例i (0) (1) (2) (3) (4) (5) gapi (0) (1) (2) (3) (4) (5) gap 21 25 49 25* 16 08 21 25 4
18、9 25* 16 08 1 21 - - 25* 31 21 - - 25* 3 25 - - 16 25 - - 16 49 - - 08 49 - - 08 21 16 08 25* 25 49 21 16 08 25* 25 492 21 - 08 - 25 22 21 - 08 - 25 2 16 - 25* - 49 16 - 25* - 49 08 16 21 25* 25 49 08 16 21 25* 25 493 08 16 21 25* 25 49 13 08 16 21 25* 25 49 1 08 16 21 25* 25 49 08 16 21 25* 25 49希尔
19、排序算法希尔排序算法rectype Rn+d1;rectype Rn+d1;int dt;int dt;SHELLSORT(rectype R,int d)SHELLSORT(rectype R,int d) int i,j,k,h; int i,j,k,h; rectype temp; rectype temp; k k0;0; dl=1; dl=1; do do h hdk;dk; for (i=h+dl;in+dl;i+) for (i=h+dl;in+dl;i+) temp tempRi;Ri; j ji-h;i-h; while (temp.keyRj.key) while (tem
20、p.keyRj.key) pj+h pj+hRj;Rj; j jj-h;j-h; Rj+h Rj+htemp;temp; k+; k+; while(h!=1); while(h!=1); 为什么为什么shellshell排序的时间性能优于直接插入排排序的时间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当需的比较和移动次数均较少。另一方面，当n n值较值较小时，小时，n n和和n n2 2的差别也较小，即直接插
21、入排序的最好的差别也较小，即直接插入排序的最好时间复杂度时间复杂度O(n)O(n)和最坏时间复杂度和最坏时间复杂度O(nO(n2 2) )差别不大。差别不大。在在shellshell排序开始时增量较大，分组较多，每组的排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。接近有序状态，所以新的一趟排序过程也较块
22、。希尔排序中希尔排序中gapgap的取法的取法Shell最初的方案是最初的方案是 gap= n/2, gap=gap/2，直到，直到gap=1.Knuth的方案是的方案是gap = gap/3+1其它方案有：都取奇数为好；或其它方案有：都取奇数为好；或gap互质为好等等。互质为好等等。希尔排序的时间复杂度希尔排序的时间复杂度对希尔排序的复杂度的分析很困难，在对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学之间的依赖关系，并要给出完整的数学分
23、析，目前还做不到。分析，目前还做不到。Knuth的统计结论是，平均比较次数和的统计结论是，平均比较次数和对象平均移动次数在对象平均移动次数在n1.25 与与1.6n1.25之间。之间。希尔排序的稳定性希尔排序的稳定性希尔排序是一种不稳定的排序方法。希尔排序是一种不稳定的排序方法。如序列如序列 3 2 2* 53交换排序交换排序两种常见的交换排序两种常见的交换排序冒泡排序冒泡排序(Bubble Sort)快速排序快速排序(Quick Sort)基本原理基本原理：每一次两两比较待排序的记录每一次两两比较待排序的记录的排序码，只要是逆序的记录对，则进行的排序码，只要是逆序的记录对，则进行交换，直到所
24、有的逆序对都交换完为止。交换，直到所有的逆序对都交换完为止。冒泡排序的基本思想冒泡排序的基本思想首首先先依依序序比比较较n个个待待排排序序记记录录的的一一端端开开始始，依依次次两两两两比比较较排排序序码码，只只要要是是逆逆序序，则则交交换换，这这样样完完成成一一趟趟交交换换排排序序，结结果果就就是是将将最最大大（或或最最小小）的的记记录录交交换换到到最最后后面面（或或最最前前面面）；然然后后其其余余的的记记录录同同法法进进行行两两两两比比较较，每每一一趟趟都都将将较较大大（小小）元元素素交交换换到到最最后后（前前）面面，一一直直进进行行下下去去，直直到到最最后后一一个个记记录录排排完完或或没没
25、有要交换的元素的时候为止。有要交换的元素的时候为止。3. 1 冒泡排序冒泡排序冒泡排序的基本过程冒泡排序的基本过程首首先先从从R0到到Rn-1对对n个个元元素素比比较较其其排排序序码码，对对逆逆序序元元素素进进行行交交换换，完完成成一一趟趟排排序序时时，将将排排序序码码值值最最到到的的元元素素几几交交换换到到最最后后一一个个位位置置，即即Rn-1，该过程相当于一趟冒泡；，该过程相当于一趟冒泡；然然后后，又又从从R0到到Rn-2中中又又进进行行一一趟趟交交换换冒冒泡泡，这这样样一一直直进进行行下下去去，直直到到最最后后一一个个元元素素R0或某一趟没有交换元素为止。或某一趟没有交换元素为止。3.
26、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* 49 4 08 16 21 25 25* 49冒泡排序算法冒泡排序算法voidbubblesort(R)for(i=0;i=i;j+) if (Rj+1.key= temp.key)&(i= temp.key)&(i= temp.key)&(i= temp.key)&(ij) j-; if (ij) Ri+=Rj; if (ij) Ri+=
27、Rj; if (ij) Ri+=Rj; if (ij) Ri+=Rj; while (Ri.key=temp.key)&(ij) i+; while (Ri.key=temp.key)&(ij) i+; while (Ri.key=temp.key)&(ij) i+; while (Ri.key=temp.key)&(ij) i+; if (ij) Rj-=Ri; if (ij) Rj-=Ri; if (ij) Rj-=Ri; if (ij) Rj-=Ri; while (i!=j); while (i!=j); while (i!=j); while (i!=j); Ri=temp; Ri=
28、temp; Ri=temp; Ri=temp; return i; return i; return i; return i; QUICKSORT(rectype R,int s1,int t1)QUICKSORT(rectype R,int s1,int t1) int i;int i;int i;int i; if (s1t1) if (s1t1) if (s1t1) if (s1t1) i=PARTITION(R,s1,t1); i=PARTITION(R,s1,t1); i=PARTITION(R,s1,t1); i=PARTITION(R,s1,t1); QUICKSORT(R,s1
29、,i-1); QUICKSORT(R,s1,i-1); QUICKSORT(R,s1,i-1); QUICKSORT(R,s1,i-1); QUICKSORT(R,i+1,t1); QUICKSORT(R,i+1,t1); QUICKSORT(R,i+1,t1); QUICKSORT(R,i+1,t1); 快速排序的时间复杂度快速排序的时间复杂度2 2、最好情况是每次所取的基准都是当前无序区的、最好情况是每次所取的基准都是当前无序区的、最好情况是每次所取的基准都是当前无序区的、最好情况是每次所取的基准都是当前无序区的“ “中值中值中值中值” ”记录，划分的结果是基准的左右两个无序子区记录，划分
30、的结果是基准的左右两个无序子区记录，划分的结果是基准的左右两个无序子区记录，划分的结果是基准的左右两个无序子区的长度大致相等。的长度大致相等。的长度大致相等。的长度大致相等。考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数1 1、最坏情况是每次划分选取的基准都是当前无序区、最坏情况是每次划分选取的基准都是当前无序区、最坏情况是每次划分选取的基准都是当前无序区、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基中关键字最小（或最大）的记录，划分的结果是基中关键字最小（或最大
31、）的记录，划分的结果是基中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素准的左边（或右边）为空，划分前后无序区的元素准的左边（或右边）为空，划分前后无序区的元素准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做个数减少一个，因此，排序必须做个数减少一个，因此，排序必须做个数减少一个，因此，排序必须做n-1n-1趟，每一趟中趟，每一趟中趟，每一趟中趟，每一趟中需做需做需做需做n-in-i次比较，所以最大比较次数为次比较，所以最大比较次数为次比较，所以最大比较次数为次比较，所以最大比较次数为 设设设设C(n)C(n)表示对长度为表示对
32、长度为表示对长度为表示对长度为n n的序列进行快速排序所的序列进行快速排序所的序列进行快速排序所的序列进行快速排序所需的比较次数，显然，它应该等于对长度为需的比较次数，显然，它应该等于对长度为需的比较次数，显然，它应该等于对长度为需的比较次数，显然，它应该等于对长度为n n的无的无的无的无序区进行划分所需的比较次数序区进行划分所需的比较次数序区进行划分所需的比较次数序区进行划分所需的比较次数n-1n-1，加上递归地对，加上递归地对，加上递归地对，加上递归地对划分所得的左右两个无序子区进行快速排序所需划分所得的左右两个无序子区进行快速排序所需划分所得的左右两个无序子区进行快速排序所需划分所得的左
33、右两个无序子区进行快速排序所需的比较次数。假设文件长度的比较次数。假设文件长度的比较次数。假设文件长度的比较次数。假设文件长度n=2n=2k k ，k=logk=log2 2n n，因，因，因，因此有：此有：此有：此有： 快速排序的记录移动次数不会大于比较快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为；最好时间复杂度为O(nlog2n)。 可以证明，快速排序的平均时间复杂度可以证明，快速排序的平均时间复杂度也是也是O(nlog2n)。 快速排序是不稳定的排序方法。快速排序是不稳定的排序方法。4选择排序选
34、择排序两种常见的选择排序两种常见的选择排序直接选择排序直接选择排序堆排序堆排序基本原理基本原理: 将待排序的结点分为已排序将待排序的结点分为已排序(初始为空初始为空)和为未排序两组，依次将未排和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组序的结点中值最小的结点插入已排序的组中。中。直接选择排序的基本思想直接选择排序的基本思想在在所所有有的的记记录录中中选选择择出出排排序序码码最最小小的的记记录，将其与第一个元素交换；录，将其与第一个元素交换；然然后后其其余余的的记记录录中中选选择择出出次次小小的的记记录录与与第二个元素交换，一直进行下去；第二个元素交换，一直进行下去；直到最后一
35、个记录排完为止。直到最后一个记录排完为止。4.1 直接选择排序直接选择排序直接选择排序过程直接选择排序过程首首先先从从R0到到Rn-1中中选选择择出出最最小小的的记记录录，将其与将其与R0交换；交换；然然后后，又又从从R1到到Rn-1中中选选择择出出最最小小的的记记录与录与R1交换；交换；这这样样，当当第第i趟趟时时从从R0到到Ri-1就就是是已已经经排排好序的，直到最后一个元素好序的，直到最后一个元素Rn-1排好为止。排好为止。4.1 直接选择排序直接选择排序直直接接选选择择排排序序示示例例493865977613274913386597764927491327659776493849132
36、73897764965491327384976976549132738494997657613273849496597761327384949657697直接选择排序算法直接选择排序算法SELECTSORT(rectype R)SELECTSORT(rectype R) int i,j,k;int i,j,k;int i,j,k;int i,j,k; rectype temp; rectype temp; rectype temp; rectype temp; for (i=0;in-1;i+) for (i=0;in-1;i+) for (i=0;in-1;i+) for (i=0;in-1
37、;i+) k=i; k=i; k=i; k=i; for (j=i+1;jn;j+) for (j=i+1;jn;j+) for (j=i+1;jn;j+) for (j=i+1;jn;j+) if (Rj.keyRk.key) k=j; if (Rj.keyRk.key) k=j; if (Rj.keyRk.key) k=j; if (Rj.key= low(n/2)i = low(n/2)的结的结点都是叶子，因此以这些结点为根的子点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序树都已是堆。这样，我们只需依次将序号为号为low(n/2)low(n/2)，low(n/2)-
38、1low(n/2)-1，.，1 1的的结点作为根的子树都调整为堆即可。结点作为根的子树都调整为堆即可。 我们以大根堆为例进行说明我们以大根堆为例进行说明 若已知结点若已知结点RiRi的左右子树已是堆，如何将以的左右子树已是堆，如何将以RiRi为为根的完全二叉树也调整为堆？根的完全二叉树也调整为堆？ 解决这一问题可采用解决这一问题可采用“筛选法筛选法”，其基本思想是：因，其基本思想是：因为为RiRi的左右子树已是堆，这两棵子树的根分别是各自子的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必须在树中关键字最大的结点，所以我们必须在RiRi和它的左右和它的左右孩子中选取关
39、键字最大的结点放到孩子中选取关键字最大的结点放到RiRi的位置上。若的位置上。若RiRi的关键字已是三者中的最大者，则无须做任何调整，以的关键字已是三者中的最大者，则无须做任何调整，以RiRi为根的子树已构成堆，否则必须将为根的子树已构成堆，否则必须将RiRi和具有最大关和具有最大关键字的左孩子键字的左孩子R2iR2i或右孩子或右孩子R2i+1R2i+1进行交换。假定进行交换。假定R2iR2i的关键字最大，将的关键字最大，将RiRi和和R2iR2i交换位置，交换之后交换位置，交换之后有可能导致有可能导致R2iR2i为根的子树不再是堆，但由于为根的子树不再是堆，但由于R2iR2i的左的左右子树仍
40、然是堆，于是可以重复上述过程，将以右子树仍然是堆，于是可以重复上述过程，将以R2iR2i为为根的子树调整为堆，根的子树调整为堆，.，如此逐层递推下去，最多可能，如此逐层递推下去，最多可能调整到树叶。调整到树叶。例子：例子：关键字序列为关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从第四个结点开始，故从第四个结点开始调整调整424213139191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不调整不调整424213139191888824241
41、616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆筛选算法筛选算法SIFT(rectype R,int i;int m)SIFT(rectype R,int i;int m)SIFT(rectype R,int i;int m)SIFT(rectype R,int i;int m) int j; int j; int j; int j; rectype temp; rectype te
42、mp; rectype temp; rectype temp; temp=Ri; temp=Ri; temp=Ri; temp=Ri; j=2*i; j=2*i; j=2*i; j=2*i; while (j=m) while (j=m) while (j=m) while (j=m) if (jm)&(Rj.keyRj+1.key) j+; if (jm)&(Rj.keyRj+1.key) j+; if (jm)&(Rj.keyRj+1.key) j+; if (jm)&(Rj.keyRj+1.key) j+; if (temp.keyRj.key) if (temp.keyRj.key)
43、if (temp.keyRj.key) if (temp.key=1; i-) SIFT(R, i, n) 由于建堆的结果把关键字最大的记录选到了堆顶的由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将位置，而排序的结果应是升序，所以，应该将R1R1和和RnRn交换，这就得到了第一趟排序的结果。交换，这就得到了第一趟排序的结果。 第二趟排序的操作首先是将无序区第二趟排序的操作首先是将无序区R1R1到到Rn-1Rn-1调整调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用以，可以调用SIFTSIF
44、T函数将函数将R1R1到到Rn-1Rn-1调整为大根堆，选调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录一个记录Rn-1Rn-1交换，如此反复进行下去。交换，如此反复进行下去。919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后（c c）重建的堆）重建的堆R1R1到到R7R788882424424
45、2232313131616050591918824422313160591050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（g g）重建的堆）重建的堆R1R1到到R5R52424232316160505131342428888919
46、12423160513428891（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891（k k）重建的堆）重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891（l
47、l）第六趟排序之后）第六趟排序之后050513131616232324244242888891910513162324428891（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891堆排序算法堆排序算法HEAPSORT(rectype R)HEAPSORT(rectype R) int i; int i; rectype temp; rectype temp; for
48、(i=n/2;i=1;i-) for (i=n/2;i=1;i-) SIFT(R,i,n); SIFT(R,i,n); for (i=n;i=1;i-) for (i=n;i=1;i-) temp=R1; R1=Ri; temp=R1; R1=Ri; Ri=temp; Ri=temp; SIFT(R,1,i-1); SIFT(R,1,i-1); 堆排序的时间复杂度堆排序的时间复杂度堆排序的时间复杂性为堆排序的时间复杂性为O(n log2n) 空间复杂性为空间复杂性为 O(1)堆排序是不稳定的排序方法。堆排序是不稳定的排序方法。5归并排序归并排序基本原理，通过对两个有序结点序基本原理，通过对两个
49、有序结点序列的合并来实现排序。列的合并来实现排序。所谓归并是指将若干个已排好序的所谓归并是指将若干个已排好序的部分合并成一个有序的部分部分合并成一个有序的部分。两路归并的基本思想两路归并的基本思想归归并并排排序序是是利利用用“归归并并”技技术术来来进进行行排排序序，所所谓谓归归并并是是指指将将若若干干个个已已经经排排序序的的子子序序列列合合并并为为一一个个有有序序序序列列。其其算算法法比比较较简简单单，可可以以直直接接给给出。出。两路归并的示例两路归并的示例25 57 48 37 12 92 86 25 57 37 48 92 12 86 25 37 48 57 12 86 92 12 25
50、37 48 57 86 92 归并算法归并算法voidmerge(R,R1,low,mid,hign)voidmerge(R,R1,low,mid,hign)/Rlow/Rlow到到到到RmidRmid与与与与Rmid+1Rmid+1到到到到RhighRhigh是是是是两两两两个个个个有有有有序序序序序序序序 列列列列 ， 结结结结 果果果果 是是是是 合合合合 并并并并 为为为为 一一一一 个个个个 有有有有 序序序序 序序序序 列列列列 R1lowR1low到到到到R1high/R1high/i=low;j=mid+1;k=low;i=low;j=mid+1;k=low; while(i=
51、mid&j=high) while(i=mid&j=high) if(Ri.key=Rj.key) if(Ri.key=Rj.key) R1k+=Ri+; R1k+=Ri+; else R1k+=Rj+; else R1k+=Rj+; while(i=mid ) R1k+=Ri+; while(i=mid ) R1k+=Ri+; while(j=high) R1k+=Rj+; while(j=high) R1k+=Rj+; 归并排序就是利用上述归并操作实归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序列现排序的。其基本思想是：将待排序列R0R0到到Rn-1Rn-1看成看成n n个
52、长度为个长度为1 1的有序子的有序子序列，把这些子序列两两归并，便得到序列，把这些子序列两两归并，便得到high(n/2)high(n/2)个有序的子序列。然后再把这个有序的子序列。然后再把这high(n/2)high(n/2)个有序的子序列两两归并，如个有序的子序列两两归并，如此反复，直到最后得到一个长度为此反复，直到最后得到一个长度为n n的有的有序序列。上述每次的归并操作，都是将序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这就是两个子序列归并为一个子序列，这就是“二路归并二路归并”，类似地还可以有，类似地还可以有“三路三路归并归并”或或“多路归并多路归并”。归并过程示例
53、归并过程示例(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个个）长长
54、度度为为2的的有有序序序序列列，然然后后继继续续进进行行，直直到到最最后后得得到到一一个个长长度度为为n的的有有序序序列为止。这就是序列为止。这就是2-路归并排序。路归并排序。其其中中，最最关关键键的的是是将将两两个个长长度度为为l的的有有序序序列归并为长度为序列归并为长度为2l的有序序列。的有序序列。一趟归并算法一趟归并算法MERGEPASS(rectype R,rectype R1,int length)MERGEPASS(rectype R,rectype R1,int length) int i,j;int i,j;int i,j;int i,j; i=0; i=0; i=0; i=0
55、; while (i+2*length-1n) while (i+2*length-1n) while (i+2*length-1n) while (i+2*length-1n) MERGE(R,R1,i,i+length-1,i+2*length-1); MERGE(R,R1,i,i+length-1,i+2*length-1); MERGE(R,R1,i,i+length-1,i+2*length-1); MERGE(R,R1,i,i+length-1,i+2*length-1); i=i+2*length; i=i+2*length; i=i+2*length; i=i+2*length
56、; if (i+length-1n-1) if (i+length-1n-1) if (i+length-1n-1) if (i+length-1n-1) MERGE(R,R1,i,i+length-1,n-1); MERGE(R,R1,i,i+length-1,n-1); MERGE(R,R1,i,i+length-1,n-1); MERGE(R,R1,i,i+length-1,n-1); else else else else for (j=i;jn;j+) R1j=Rj; for (j=i;jn;j+) R1j=Rj; for (j=i;jn;j+) R1j=Rj; for (j=i;j
57、n;j+) R1j=Rj; 在在上上述述一一趟趟归归并并过过程程中中，如如果果正正好好配配成成对对时时候候，即即可可正正常常完完成成，否否则则最最后后一一次次归归并时，可能有两种情况：并时，可能有两种情况：（1）(2k+1)*lenn2(k+1)*len表表示示有有两两个个有有序序序序列列，但但后后一一个个长长度度不不足足len，此此时时归归并并方方法法与与前前相相同同，仅仅仅仅是是参参数不同而已。数不同而已。（2）2k*lenn2(k+1)*len表表示示只只有有一一个个有有序序序序列列，此此时时已已经经是是有有序的，故只需要复制到序的，故只需要复制到R1中即可。中即可。归并排序就是从长度为
58、归并排序就是从长度为1的有序序列逐的有序序列逐渐归并为长度为渐归并为长度为2，4，,n的循环过程。的循环过程。归并排序算法归并排序算法MERGESORT(rectype R)MERGESORT(rectype R) int length=1; int length=1; int length=1; int length=1; while (lengthn) while (lengthn) while (lengthn) while (lengthn) MERGEPASS(R,R1,length); MERGEPASS(R,R1,length); MERGEPASS(R,R1,length);
59、MERGEPASS(R,R1,length); length=2*length; length=2*length; length=2*length; length=2*length; MERGEPASS(R1,R,length); MERGEPASS(R1,R,length); MERGEPASS(R1,R,length); MERGEPASS(R1,R,length); length=2*length; length=2*length; length=2*length; length=2*length; 算法复杂性分析算法复杂性分析 归并排序是稳定的排序方法。归并排序是稳定的排序方法。 归并
60、排序在第归并排序在第i 趟归并后，有序子文件趟归并后，有序子文件长度为长度为2i，因此，因此，对于具有，因此，因此，对于具有n个记录个记录的序列来说，必须做的序列来说，必须做high(log2n)趟归并，趟归并，每趟归并所花的时间为每趟归并所花的时间为O(n)。所以，二路。所以，二路归并排序算法的时间复杂度为归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为辅助数组所需的空间为O(n)。6基数排序基数排序基本原理，采用基本原理，采用“分配分配”和和“收收集集”的办法，用对多关键字进行的办法，用对多关键字进行排序的思想实现对单关键字进行排序的思想实现对单关键字进行排序的方法。排序
61、的方法。下面先介绍多关键字排序下面先介绍多关键字排序多关键字排序方法示例多关键字排序方法示例如对扑克牌的排序如对扑克牌的排序每张扑克牌有两个每张扑克牌有两个“关键字关键字”：花：花色和面值它们之间有次序的优先。色和面值它们之间有次序的优先。对以上排序，可以先对花色排序，对以上排序，可以先对花色排序，或先对面值排序。或先对面值排序。多关键字有序的概念多关键字有序的概念考虑对象序列考虑对象序列V0,V1,., Vn-1，每个，每个对象对象Vi含含d个关键字个关键字(Ki1,Ki2,., Kid)。若对序列中的任意两个对象若对序列中的任意两个对象Vi和和Vj都有都有 (Ki1,Ki2,., Kid)
62、 (Kj1,Kj2,., Kjd)则称序列对关键字则称序列对关键字(Ki1,Ki2,., Kid)有有序，且序，且K1称为最高位关键字，称为最高位关键字，Kd称为最称为最低位关键字。低位关键字。多关键字排序多关键字排序原理：根据组成关键字的各位的值原理：根据组成关键字的各位的值进行排序。进行排序。 实现基数排序的两种方法：实现基数排序的两种方法： 1 最高位优先最高位优先(MSD)排序：从关键排序：从关键 字的高位到低位字的高位到低位 2 最低位优先最低位优先(LSD)排序：从关键排序：从关键字字 的低位到高位的低位到高位MSD方法通常是一个递归的过程。方法通常是一个递归的过程。多关键字排序（
63、续）多关键字排序（续）LSD和和MSD方法也可应用于对一个方法也可应用于对一个关键字进行的排序。此时可将单关关键字进行的排序。此时可将单关键字键字Ki看成是一个子关键字组：看成是一个子关键字组： (Ki1,Ki2,., Kid)如对关键字取值范围为如对关键字取值范围为0到到999的一的一组对象，可看成是组对象，可看成是(K1,K2,K3)的组合。的组合。MSD方法按方法按K1,K2,K3的顺序对所有的顺序对所有对象排序；对象排序；LSD方法按方法按K3 ,K2 , K1的顺序对所有对象排序。的顺序对所有对象排序。链式的基数排序链式的基数排序基数排序是一种典型的基数排序是一种典型的LSD排序方法
64、，排序方法，它利用它利用“分配分配”和和“收集收集”两种运算对两种运算对单关键字进行排序。单关键字进行排序。此时可将单关键字此时可将单关键字K看成是一个子关键看成是一个子关键字组：字组： (Ki1,Ki2,., Kid)排序过程：设关键字共有排序过程：设关键字共有d位，让位，让j= d, d-1,.,1, 依次执行依次执行d次次“分配分配”与与“收集收集”。1792083069385998455927133B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f
65、B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 27193339845530620817985992719333984553062081798599B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f 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
66、B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 33984306208955859271179933062089335585927117998493B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f 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 B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e
67、B9.e 17930698485993355932082719335593179208271306859984分配排序算法分配排序算法typedef structtypedef struct int keyd; int keyd; int next; int next; datatype other; datatype other; rectype; rectype;rectype Rn;rectype Rn;typedef structtypedef struct int f,e; int f,e; queue; queue;queue Bm;queue Bm;while (p!=-1)wh
68、ile (p!=-1) k=Rp.keyj; k=Rp.keyj; if (Bk.f=-1) Bk.f=p; if (Bk.f=-1) Bk.f=p; else RBk.e.next=p; else RBk.e.next=p; Bk.e=p; Bk.e=p; p=Rp.next; p=Rp.next; i=0; i=0; while (Bi.f=-1) i+; while (Bi.f=-1) i+; t=Bi.e; p=Bi.f; t=Bi.e; p=Bi.f; while (im-1) while (im-1) i+; i+; if (Bi.f!=-1) if (Bi.f!=-1) Rt.n
69、ext=Bi.f; t=Bi.e; Rt.next=Bi.f; t=Bi.e; Rt.next=-1; Rt.next=-1; return p; return p; int RADIXSORTint RADIXSORTint RADIXSORTint RADIXSORT (rectype R) (rectype R) (rectype R) (rectype R) int i,j,k,t,p; int i,j,k,t,p; int i,j,k,t,p; int i,j,k,t,p; for (i=0;in-1;i+) for (i=0;in-1;i+) for (i=0;in-1;i+) f
70、or (i=0;i=0;j-) for (j=d-1;j=0;j-) for (j=d-1;j=0;j-) for (j=d-1;j=0;j-) for (i=0;im;i+) for (i=0;im;i+) for (i=0;im;i+) for (i=0;im;i+) Bi.f=-1; Bi.f=-1; Bi.f=-1; Bi.f=-1; Bi.e=-1; Bi.e=-1; Bi.e=-1; Bi.e=-1; /初初初初始始始始化化化化每每每每趟趟趟趟分分分分配配配配前前前前的的的的所所所所有有有有队队队队列列列列空空空空/CH7 CH7 内排序内排序直接插入排序直接插入排序shell插入
71、排序（缩小增量排序）插入排序（缩小增量排序）插入策略插入策略二分插入排序二分插入排序表插入排序表插入排序直接交换排序（冒泡排序）直接交换排序（冒泡排序）交换策略交换策略快速排序快速排序直接选择排序直接选择排序选择策略选择策略堆排序堆排序归并策略归并策略分配策略分配策略基数排序基数排序内部排序方法的比较和选择内部排序方法的比较和选择选取排序方法时需要考虑的因素有：选取排序方法时需要考虑的因素有： 待排序的记录数目待排序的记录数目 记录本身信息量的大小记录本身信息量的大小 关键字的结构及其分布情况关键字的结构及其分布情况 对排序稳定性的要求对排序稳定性的要求 语言工具的条件、辅助空间的大小语言工具的条件、辅助空间的大小外部排序简介外部排序简介 如果待排序的记录数很大，无法将所如果待排序的记录数很大，无法将所有记录都调入内存，只能将它们存放在外有记录都调入内存，只能将它们存放在外存上，我们称这时的排序为外部排序。存上，我们称这时的排序为外部排序。 外部排序的实现，主要是依靠数据的外部排序的实现，主要是依靠数据的内外存交换和内外存交换和“内部归并内部归并”。
