数据结构第9章排序.ppt

《数据结构第9章排序.ppt》由会员分享，可在线阅读，更多相关《数据结构第9章排序.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第9章章 排排 序序 在信息处理过程中，最基本的操作是查找。从查在信息处理过程中，最基本的操作是查找。从查找来说，效率最高的是折半查找，折半查找的前提是所找来说，效率最高的是折半查找，折半查找的前提是所有的数据元素有的数据元素(记录记录)是按关键字有序的。需要将一个无是按关键字有序的。需要将一个无序的数据文件转变为一个有序的数据文件。序的数据文件转变为一个有序的数据文件。将任一文件中的记录通过某种方法整理成为按将任一文件中的记录通过某种方法整理成为按(记记录录)关键字有序排列的处理过程称为关键字有序排列的处理过程称为排序排序。排序是排序是数据处理数据处理中一种中一种最常用的操作最常用的操作。

2、9.1 排序的基本概念排序的基本概念 排序排序(Sorting)排序排序是将一批是将一批(组组)任意次序的记录重新排列成任意次序的记录重新排列成按按关键字有序关键字有序的记录序列的过程，其定义为的记录序列的过程，其定义为：给定一组记录序列给定一组记录序列：R1,R2,Rn，其相应的其相应的关键字序列是关键字序列是K1,K2,Kn。确定确定1,2,n的一个的一个排列排列p1,p2,pn，使其相应的关键字满足如下非递使其相应的关键字满足如下非递减减(或非递增或非递增)关系关系：Kp1Kp2 Kpn的序列的序列Kp1,Kp2,Kpn，这种操作称为排序。这种操作称为排序。关键字关键字Ki可以是记录可以

3、是记录Ri的主关键字的主关键字，也可以是次关也可以是次关键字或若干数据项的组合。键字或若干数据项的组合。Ki是主关键字：排序后得到的结果是唯一的；是主关键字：排序后得到的结果是唯一的；Ki是次关键字：排序后得到的结果是不唯一的。是次关键字：排序后得到的结果是不唯一的。排序的稳定性排序的稳定性 若记录序列中有若记录序列中有两个或两个以上关键字相等两个或两个以上关键字相等的记的记录：录：Ki=Kj(ij，i,j=1,2,n)，且在排序前且在排序前Ri先于先于Rj(ij)，排序后的记录序列仍然是排序后的记录序列仍然是Ri先于先于Rj，称排序方称排序方法是稳定的，否则是不稳定的。法是稳定的，否则是不稳

4、定的。排序算法有许多，但就全面性能而言，还没有一种排序算法有许多，但就全面性能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合公认为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。不同的数据量和硬件配置。评价排序算法的标准有：评价排序算法的标准有：执行时间执行时间和和所需的辅助空所需的辅助空间间，其次是，其次是算法的稳定性算法的稳定性。若排序算法所需的辅助空间不依赖问题的规模若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是即空间复杂度是O(1)，则称排序方法是则称排序方法是就地排序就地排序，否则，否则是是非就地排序非就地排序。排序的分类排序的分类 待

5、排序的记录数量不同，排序过程中涉及的存储器待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。的不同，有不同的排序分类。待排序的记录数不太多待排序的记录数不太多：所有的记录都能存放在：所有的记录都能存放在内存中进行排序，称为内存中进行排序，称为内部排序内部排序；待排序的记录数太多待排序的记录数太多：所有的记录不可能存放在：所有的记录不可能存放在内存中，内存中，排序过程中必须在内、外存之间进行数据排序过程中必须在内、外存之间进行数据交换，这样的排序称为交换，这样的排序称为外部排序外部排序。内部排序的基本操作内部排序的基本操作 对内部排序地而言，其基本操作有两种对内部排序地而言，

6、其基本操作有两种：比较两个关键字的大小；比较两个关键字的大小；存储位置的移动：从一个位置移到另一个位置。存储位置的移动：从一个位置移到另一个位置。第一种操作是必不可少的；而第二种操作却不是必第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是：须的，取决于记录的存储方式，具体情况是：记录存储在一组连续地址的存储空间记录存储在一组连续地址的存储空间：记录之间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必不可少的记录的移动是必不可少的；记录采用链式存储方式记录采用链式存储方式：记录之间的逻辑顺序

7、关：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程系是通过结点中的指针来体现，排序过程仅需修改结仅需修改结点的指针点的指针，而，而不需要移动记录不需要移动记录；记录存储在一组连续地址的存储空间记录存储在一组连续地址的存储空间：构造另一：构造另一个辅助表来保存各个记录的存放地址个辅助表来保存各个记录的存放地址(指针指针)：排：排序过程序过程不需要移动记录不需要移动记录，而，而仅需修改辅助表中的仅需修改辅助表中的指针指针，排序后视具体情况决定是否调整记录的存，排序后视具体情况决定是否调整记录的存储位置。储位置。比较适合记录数较少的情况；而比较适合记录数较少的情况；而、则适合记则适合记录数

8、较多的情况。录数较多的情况。为讨论方便，假设待排序的记录是以为讨论方便，假设待排序的记录是以的情况存的情况存储，且设排序是按升序排列的；关键字是一些可直储，且设排序是按升序排列的；关键字是一些可直接用比较运算符进行比较的类型。接用比较运算符进行比较的类型。待排序的记录类型的定义如下：待排序的记录类型的定义如下：#define MAX_SIZE 100Typedef int KeyType;typedef struct RecType KeyType key;/*关键字码关键字码 */infoType otherinfo;/*其他域其他域 */RecType;typedef struct Sql

9、ist RecType RMAX_SIZE;int length ;Sqlist;9.2 插入排序插入排序 采用的是以采用的是以“玩桥牌者玩桥牌者”的方法为基础的的方法为基础的。即在考。即在考察记录察记录Ri之前之前，设以前的所有记录，设以前的所有记录R1,R2,.,Ri-1已排已排好序好序，然后将，然后将Ri插入到插入到已排好序的诸记录的适当位置已排好序的诸记录的适当位置。最基本的插入排序是最基本的插入排序是直接插入排序直接插入排序(Straight Insertion Sort)。9.2.1 直接插入排序直接插入排序1 排序思想排序思想 将待排序的记录将待排序的记录Ri，插入到已插入到已排

10、好序的排好序的记录表记录表R1,R2,.,Ri-1中中，得到一个新的、记录数增加，得到一个新的、记录数增加1的有序表的有序表。直到所有的记录都插入完为止直到所有的记录都插入完为止。设设待排序的记录顺序存放在数组待排序的记录顺序存放在数组R1n中，在排序中，在排序的某一时刻，将记录序列分成两部分：的某一时刻，将记录序列分成两部分：R1i-1：已：已排好序的有序部分排好序的有序部分；Rin：未：未排好序的无序部分。排好序的无序部分。显然，在刚开始排序时，显然，在刚开始排序时，R1是已经是已经排好序的。排好序的。例例：设有关键字序列为：设有关键字序列为：7,4,-2,19,13,6，直接插，直接插入

11、排序的过程如下图入排序的过程如下图9-1所示：所示：初始记录的关键字初始记录的关键字：7 4 -2 19 13 6第一趟排序第一趟排序：4 7 -2 19 13 6第二趟排序第二趟排序：-2 4 7 19 13 6第三趟排序第三趟排序：-2 4 7 19 13 6第四趟排序第四趟排序：-2 4 7 13 19 6第五趟排序第五趟排序：-2 4 6 7 13 19图图9-1 直接插入排序的过程直接插入排序的过程2 算法实现算法实现void straight_insert_sort(Sqlist*L)int i,j;for(i=2;ilength;i+)L-R0=L-Ri;j=i-1;/*设置哨兵

12、设置哨兵 */while(LT(L-R0.key,L-Rj.key)L-Rj+1=L-Rj;j-;/*查找插入位置查找插入位置 */L-Rj+1=L-R0;/*插入到相应位置插入到相应位置 */3 算法说明算法说明 算法中的算法中的R0开始时并不存放任何待排序的记录，开始时并不存放任何待排序的记录，引入的作用主要有两个：引入的作用主要有两个：不需要增加辅助空间：不需要增加辅助空间：保存当前待插入的记录保存当前待插入的记录Ri，Ri会会因为记录的后移而被占用；因为记录的后移而被占用；保证查找插入位置的内循环总可以在超出循环边保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记

13、录，起界之前找到一个等于当前记录的记录，起“哨兵监视哨兵监视”作用，避免在内循环中每次都要判断作用，避免在内循环中每次都要判断j是否越界是否越界。4 算法分析算法分析 最好情况最好情况：若待排序记录按关键字从小到大排若待排序记录按关键字从小到大排列列(正序正序)，算法中的内循环无须执行，算法中的内循环无须执行，则一趟排序时：则一趟排序时：关键字比较次数关键字比较次数1次，记录移动次数次，记录移动次数2次次(RiR0,R0Rj+1)。则整个排序的关键字比较次数和记录移动次数分别则整个排序的关键字比较次数和记录移动次数分别是：是：比较次数比较次数：1=n-1ni=2移动次数移动次数：2=2(n-1

14、)ni=2 最坏情况最坏情况：若待排序记录按关键字从大到小排若待排序记录按关键字从大到小排列列(逆序逆序)，则一趟排序时：算法中的内循环体执行，则一趟排序时：算法中的内循环体执行i-1，关键字比较次数关键字比较次数i次，记录移动次数次，记录移动次数i+1。则就整个排序而言：则就整个排序而言：比较次数比较次数：i=ni=2(n-1)(n+1)2移动次数移动次数：(i+1)=ni=2(n-1)(n+4)2 一般地一般地，认为，认为待排序的记录可能出现的各种排列的待排序的记录可能出现的各种排列的概率相同概率相同，则取以上两种情况的平均值，作为排序的，则取以上两种情况的平均值，作为排序的关关键字比较次

15、数和记录移动次数键字比较次数和记录移动次数，约为约为n2/4，则，则复杂度为复杂度为O(n2)。9.2.2 其它插入排序其它插入排序1 折半插入排序折半插入排序 当将待排序的记录当将待排序的记录Ri 插入到已排好序的记录子表插入到已排好序的记录子表R1i-1中时，由于中时，由于R1,R2,Ri-1已排好序，则查找已排好序，则查找插入位置可以用插入位置可以用“折半查找折半查找”实现，则直接插入排序就实现，则直接插入排序就变成为折半插入排序。变成为折半插入排序。算法实现算法实现void Binary_insert_sort(Sqlist*L)int i,j,low,high,mid;for(i=2

16、;ilength;i+)L-R0=L-Ri;/*设置哨兵设置哨兵 */low=1;high=i-1;while(lowR0.key,L-Rmid.key)high=mid-1;else low=mid+1;/*查找插入位置查找插入位置 */for(j=i-1;j=high+1;j-)L-Rj+1=L-Rj;L-Rhigh+1=L-R0;/*插入到相应位置插入到相应位置 */从时间上比较从时间上比较，折半插入排序仅仅减少了关键字的，折半插入排序仅仅减少了关键字的比较次数比较次数，却没有减少，却没有减少记录的移动次数记录的移动次数，故时间故时间复杂度复杂度仍然为仍然为O(n2)。排序示例排序示例

17、设有一组关键字设有一组关键字30,13,70,85,39,42,6,20，采用折采用折半插入排序方法排序的过程如图半插入排序方法排序的过程如图9-2所示：所示：i=1 (30)13 70 85 39 42 6 20i=2 13 (13 30)70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85)20i=8 20 (6 13 30 39 42 70 85)20lowhighmidi=8 20 (6 13 30 39 42 70 85)20lowhighmidi=8 20 (6 13 30 39 42 70 85)20mid highlowi=8 20 (6 13

18、 20 30 39 42 70 85)图图9-2 折半插入排序过程折半插入排序过程2 2-路插入排序路插入排序 是对折半插入排序的改进是对折半插入排序的改进，以减少排序过程中移动以减少排序过程中移动记录的次数记录的次数。附加附加n个记录的辅助空间个记录的辅助空间，方法是，方法是：另设一个和另设一个和L-R同同类型的数组类型的数组d，L-R1赋给赋给d1，将，将d1看成是排好序的序列中中间位置的记录；看成是排好序的序列中中间位置的记录；分别将分别将L-R 中的第中的第i个记录依次插入到个记录依次插入到d1之之前或之后前或之后的有序序列中，具体方法的有序序列中，具体方法：L-Ri.keyRi插入到

19、插入到d1之前之前的有序表中；的有序表中；L-Ri.keyd1.key：L-Ri插入到插入到d1之后之后的有序表中；的有序表中；关键点关键点：实现时将实现时将向量向量d看成是循环向量看成是循环向量，并设两个指，并设两个指针针first和和final分别指示排序过程中得到的有序序列中的分别指示排序过程中得到的有序序列中的第一个和最后一个记录第一个和最后一个记录。排序示例排序示例设有初始关键字集合设有初始关键字集合49,38,65,13,97,27,76，采，采用用2-路插入排序的过程如右图路插入排序的过程如右图9-3所示。所示。在在2-路插入排序中，移动记录的次数约为路插入排序中，移动记录的次数

20、约为n2/8。但当但当L-R1是待排序记录中关键字最大或最小的记录是待排序记录中关键字最大或最小的记录时，时，2-路插入排序就完全失去了优越性。路插入排序就完全失去了优越性。2776d49firstfirstfirstfirstfinalfinalfinalfinal653897971313图图9-3 2-路插入排序过程路插入排序过程3 表插入排序表插入排序前面的插入排序不可避免地要移动记录，若不移动记录前面的插入排序不可避免地要移动记录，若不移动记录就需要改变数据结构。附加就需要改变数据结构。附加n个记录的辅助空间，记录个记录的辅助空间，记录类型修改为：类型修改为：typedef struc

21、t RecNode KeyType key;infotype otherinfo;int*next;RecNode;初始化初始化：下标值为：下标值为0的分量作为表头结点的分量作为表头结点，关键字取，关键字取为最大值，各分量的指针值为空；为最大值，各分量的指针值为空；将静态链表中将静态链表中数组下标值为数组下标值为1的分量的分量(结点结点)与表与表头结点构成一个循环链表；头结点构成一个循环链表；i=2，将分量将分量Ri按关键字递减插入到循环链表；按关键字递减插入到循环链表；增加增加i，重复，重复，直到全部分量插入到循环链表。，直到全部分量插入到循环链表。例：例：设有关键字集合设有关键字集合49,

22、38,65,97,76,13,27,49，采，采用表插入排序的过程如下图用表插入排序的过程如下图9-4所示所示。0 1 2 3 4 5 6 7 8key域域next域域MAXINT 49 38 65 13 97 27 76 49 1 0 -i=2MAXINT 49 38 65 13 97 27 76 49 2 0 1 -i=3MAXINT 49 38 65 13 97 27 76 49 2 3 1 0 -i=4MAXINT 49 38 65 13 97 27 76 49 4 3 1 0 2 -i=5MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 2 0 -和直接插

23、入排序相比，不同的是修改和直接插入排序相比，不同的是修改2n次指针值以次指针值以代替移动记录，而代替移动记录，而关键字的比较次数相同关键字的比较次数相同，故时间复杂故时间复杂度为度为O(n2)。表表插入排序得到一个有序链表，对其可以方便地进插入排序得到一个有序链表，对其可以方便地进行顺序查找，但不能实现随机查找行顺序查找，但不能实现随机查找。根据需要，可以对根据需要，可以对记录进行重排，记录重排详见记录进行重排，记录重排详见P247。i=6MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 6 0 2 -i=7MAXINT 49 38 65 13 97 27 76 4

24、9 4 3 1 7 6 0 2 5 -i=8MAXINT 49 38 65 13 97 27 76 49 4 8 1 7 6 0 2 5 3图图9-4 表插入排序过程表插入排序过程9.2.3 希尔排序希尔排序 希尔排序希尔排序(Shell Sort，又称，又称缩小增量法缩小增量法)是一种是一种分组插入排序方法分组插入排序方法。1 排序思想排序思想 先取一个正整数先取一个正整数d1(d1n)作为第一个增量，将全作为第一个增量，将全部部n个记录分成个记录分成d1组，组，把所有相隔把所有相隔d1的记录放在一组的记录放在一组中，即对于每个中，即对于每个k(k=1,2,d1)，Rk,Rd1+k,R2d1

25、+k,分在分在同一组中同一组中，在各组内进行直接插入，在各组内进行直接插入排序排序。这样一次分组和排序过程称为一趟这样一次分组和排序过程称为一趟希尔排序希尔排序；取新的增量取新的增量d2d1，重复重复的的分组和排序操作；分组和排序操作；直至所取的增量直至所取的增量di=1为止，为止，即所有记录放进一个组中即所有记录放进一个组中排序为止排序为止。2 排序示排序示例例 设有设有10个待排序的记录个待排序的记录，关键字分别为，关键字分别为9,13,8,2,5,13,7,1,15,11，增量序列是，增量序列是5,3,1，希尔排序的过程，希尔排序的过程如图如图9-5所示所示。9 7 1 2 5 13 1

26、3 8 15 11第一趟排序后第一趟排序后:2 5 1 9 7 13 11 8 15 13第二趟排序后第二趟排序后:1 2 5 7 8 9 11 13 13 15第三趟排序后第三趟排序后:图图9-5 希尔排序过程希尔排序过程9 13 8 2 5 13 7 1 15 1171318初始关键字序列初始关键字序列:第一趟排序过程第一趟排序过程:3 算法实现算法实现 先给出一趟希尔排序的算法，类似直接插入排序先给出一趟希尔排序的算法，类似直接插入排序。void shell_pass(Sqlist*L,int d)/*对顺序表对顺序表L进行一趟希尔排序进行一趟希尔排序,增量为增量为d */int j,k

27、;for(j=d+1;jlength;j+)L-R0=L-Rj;/*设置监视哨兵设置监视哨兵 */k=j-d;while(k0<(L-R0.key,L-Rk.key)L-Rk+d=L-Rk;k=k-d;L-Rk+j=L-R0;然后在根据增量数组然后在根据增量数组dk进行希尔排序进行希尔排序。void shell_sort(Sqlist*L,int dk,int t)/*按增量序列按增量序列dk0 t-1,对顺序表对顺序表L进行希尔排序进行希尔排序 */int m;for(m=0;mR1与与L-R2的关键字进行比较的关键字进行比较，若，若为反序为反序(L-R1的关键字大于的关键字大于L-R2

28、的关键字的关键字)，则，则交换两个记录交换两个记录；然后比较然后比较L-R2与与L-R3的关键字的关键字，依此类推，直到依此类推，直到L-Rn-1与与L-Rn的关键字比较后的关键字比较后为止为止，称为一趟，称为一趟冒泡排序冒泡排序，L-Rn为关键字最大的为关键字最大的记录记录。然后进行第二趟然后进行第二趟冒泡排序冒泡排序，对前，对前n-1个记录进行个记录进行同样的操作同样的操作。一般地，第一般地，第i趟趟冒泡排序是对冒泡排序是对L-R1 n-i+1中的中的记录进行的记录进行的，因此，若待排序的记录有，因此，若待排序的记录有n个个，则要经过，则要经过n-1趟趟冒泡排序才能使所有的记录有序冒泡排序

29、才能使所有的记录有序。2 排序示排序示例例 设有设有9个待排序的记录个待排序的记录，关键字分别为，关键字分别为23,38,22,45,23,67,31,15,41，冒泡排序的过程如图，冒泡排序的过程如图9-6所示所示。3 算法实现算法实现#define FALSE 0#define TRUE 1图图9-6 冒泡排序过程冒泡排序过程23 38 22 45 23 67 31 15 41初始关键字序列初始关键字序列:第一趟排序后第一趟排序后:23 22 38 23 45 31 15 41 67第二趟排序后第二趟排序后:22 23 23 38 31 15 41 45 67第三趟排序后第三趟排序后:22

30、 23 23 31 15 38 41 45 67第四趟排序后第四趟排序后:22 23 23 15 31 38 41 45 67第五趟排序后第五趟排序后:22 23 15 23 31 38 41 45 67第六趟排序后第六趟排序后:22 15 23 23 31 38 41 45 67第七趟排序后第七趟排序后:15 22 23 23 31 38 41 45 67void Bubble_Sort(Sqlist*L)int j,k,flag;for(j=0;jlength;j+)/*共有共有n-1趟排序趟排序 */flag=TRUE;for(k=1;klength-j;k+)/*一趟排序一趟排序 */

31、if(LT(L-Rk+1.key,L-Rk.key)flag=FALSE;L-R0=L-Rk;L-Rk=L-Rk+1;L-Rk+1=L-R0;if (flag=TRUE)break;故时间复杂度故时间复杂度：T(n)=O(n)空间复杂度：空间复杂度：S(n)=O(1)4 算法分析算法分析时间复杂度时间复杂度 最好情况最好情况(正序正序)：比较次数：比较次数：n-1；移动次数：；移动次数：0；最坏情况最坏情况(逆序逆序)：比较次数比较次数：(n-i)=n-1i=1n(n-1)2移动次数移动次数：3(n-i)=n-1i=13n(n-1)29.3.2 快速排序快速排序1 排序思想排序思想 通过一趟排

32、序，将待排序记录分割成独立的两部分，其中一通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序部分记录进行下一趟排序，以达到整个序列有序。2 排序过程排序过程 设待排序的记录序列是设待排序的记录序列是Rst，在，在记录序列中记录序列中任取任取一个记一个记录录(一般取一般取Rs)作为作为参照参照(又称为又称为基准基准或或枢轴枢轴)，以，以Rs.key为为基基准重新排列其余的所有记录准重新排列其余的所有记录，方法是方法是：所有关键字比基准小的放所

33、有关键字比基准小的放Rs之前之前；所有关键字比基准大的放所有关键字比基准大的放Rs之后之后。以以Rs.key最后所在位置最后所在位置i作为分界，将序列作为分界，将序列Rst分割成两个子序列，称为一趟快速排序分割成两个子序列，称为一趟快速排序。3 一趟快速排序方法一趟快速排序方法 从序列的两端交替扫描各个记录，将从序列的两端交替扫描各个记录，将关键字小于关键字小于基准关键字的记录基准关键字的记录依次依次放置到序列的前边放置到序列的前边；而将而将关键字关键字大于基准关键字的记录大于基准关键字的记录从序列的最后端起，依次从序列的最后端起，依次放置到放置到序列的后边序列的后边，直到扫描完所有的记录，直

34、到扫描完所有的记录。设置指针设置指针low，high，初值为第，初值为第1个和最后一个记个和最后一个记录的位置。录的位置。设两个变量设两个变量i，j，初始时令初始时令i=low，j=high，以以Rlow.key作为基准作为基准(将将Rlow保存在保存在R0中中)。从从j所指位置向前搜索：将所指位置向前搜索：将R0.key与与Rj.key进进行比较行比较：若若R0.keyRj.key：令：令j=j-1，然后继续进，然后继续进行比较，行比较，直到直到i=j或或R0.keyRj.key为止为止；若若R0.keyRj.key：RjRi，腾空腾空Rj的的位置位置，且令且令i=i+1；从从i所指位置起向

35、后搜索：将所指位置起向后搜索：将R0.key与与Ri.key进行比较进行比较：若若R0.keyRi.key：令：令i=i+1，然后继续进，然后继续进行比较，行比较，直到直到i=j或或R0.keyRi.key为止为止；若若R0.keyR0=L-Ri;/*R0作为临时单元和哨兵作为临时单元和哨兵 */do while(LQ(L-R0.key,L-Rj.key)&(ji)j-;if (ji)L-Ri=L-Rj;i+;while(LQ(L-Ri.key,L-R0.key)&(ji)i+;if (ji)L-Rj=L-Ri;j-;while(i!=j);/*i=j时退出扫描时退出扫描 */L-Ri=L-R

36、0;return(i);快速排序算法实现快速排序算法实现 当进行一趟快速排序后当进行一趟快速排序后，采采用同样方法分别对用同样方法分别对两两个子序列个子序列快速排序快速排序，直到，直到子子序列记录个为序列记录个为1为止为止。递归算法递归算法 void quick_Sort(Sqlist *L,int low,int high)int k;if (lowhigh)k=quick_one_pass(L,low,high);quick_Sort(L,low,k-1);quick_Sort(L,k+1,high);/*序列分为两部分后分别对每个子序列排序序列分为两部分后分别对每个子序列排序 */非递归

37、算法非递归算法#define MAX_STACK 100void quick_Sort(Sqlist *L,int low,int high)int k,stackMAX_STACK,top=0;do while (lowhigh)k=quick_one_pass(L,low,high);stack+top=high;stack+top=k+1;/*第二个子序列的上第二个子序列的上,下界分别入栈下界分别入栈 */high=k-1;if(top!=0)low=stacktop-;high=stacktop-;while(top!=0&low1时，用时，用n-1代替代替中的中的n，得到，得到：Ta

38、vg(n)=(n-1)C+Tavg(k)n-2k=02n nTavg(n)-(n-1)Tavg(n-1)=(2n-1)C+2Tavg(n-1)，即即Tavg(n)=(n+1)/nTavg(n-1)+(2n-1)/nC(n+1)/nTavg(n-1)+2C(n+1)/nn/(n-1)Tavg(n-2)+2C+2C=(n+1)/(n-1)Tavg(n-2)+2(n+1)1/n+1/(n+1)C Tavg(1)+2(n+1)C2n+13141+1n+1n1+Tavg(n)只有只有1个记录的排序时间是个记录的排序时间是一个常数一个常数，快速排序的平均时间复杂度是快速排序的平均时间复杂度是：T(n)=O

39、(n2n)从所需要的附加空间来看从所需要的附加空间来看，快速排序算法是递归调，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较均匀用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为时，栈的最大深度为2n+1。快速排序的空间复杂度是快速排序的空间复杂度是：S(n)=O(2n)从排序的稳定性来看，快速排序是从排序的稳定性来看，快速排序是不稳定不稳定的。的。9.4 选择排序选择排序 选择排序选择排序(Selection Sort)的基本思想是：每次的基本思想是：每次从当前从当前待排序的记录待排序的记录中选取关键字最小的中选取关键字最小的记录，然后与记录，然后与待排序的

40、记录序列待排序的记录序列中的第中的第一个记录进行交换，直到整个一个记录进行交换，直到整个记录序列有序为止记录序列有序为止。9.4.1 简单选择排序简单选择排序 简单选择排序简单选择排序(Simple Selection Sort，又，又称为称为直直接选择排序接选择排序)的基本操作是的基本操作是：通过：通过n-i次关键字间的比较，次关键字间的比较，从从n-i+1个记录中选取关键字最小的记录，然后和第个记录中选取关键字最小的记录，然后和第i个记个记录进行交换，录进行交换，i=1,2,n-1。1 排序示例排序示例 例例：设有关键字序列为：设有关键字序列为：7,4,-2,19,13,6，直接选，直接选

41、择排序的过程如下图择排序的过程如下图9-8所示。所示。图图9-8 直接选择排序的过程直接选择排序的过程初始记录的关键字初始记录的关键字：7 4 -2 19 13 6第一趟排序第一趟排序：-2 4 7 19 13 6第二趟排序第二趟排序：-2 4 7 19 13 6第三趟排序第三趟排序：-2 4 6 19 13 7第四趟排序第四趟排序：-2 4 6 7 13 19第五趟排序第五趟排序：-2 4 6 7 13 19第六趟排序第六趟排序：-2 4 6 7 13 192算法实现算法实现 1.void simple_selection_sort(Sqlist*L)int m,n,k;for(m=1;ml

42、ength;m+)k=m;for (n=m+1;nlength;n+)if (LT(L-Rn.key,L-Rk.key)k=n;if (k!=m)/*记录交换记录交换 */L-R0=L-Rm;L-Rm=L-Rk;L-Rk=L-R0;3 算法分析算法分析 整个算法是二重循环整个算法是二重循环：外循环控制排序的趟数，对：外循环控制排序的趟数，对n个记录进行排序的趟数为个记录进行排序的趟数为n-1趟；内循环控制每一趟的趟；内循环控制每一趟的排序排序。进行第进行第i趟排序时趟排序时，关键字的比较次数为，关键字的比较次数为n-i，则：，则：比较次数比较次数：(n-i)=n-1i=1n(n-1)2 时间复

43、杂度时间复杂度是是：T(n)=O(n2)空间复杂度是空间复杂度是：S(n)=O(1)从排序的稳定性来看从排序的稳定性来看，直接选择排序是直接选择排序是不稳定不稳定的的。9.4.2 树形选择排序树形选择排序 借助借助“淘汰赛淘汰赛”中的对垒就很容易理解树形选择排中的对垒就很容易理解树形选择排序的思想。序的思想。首先对首先对n个记录的关键字两两进行比较个记录的关键字两两进行比较，选取，选取 n/2 个较小者个较小者；然后这；然后这 n/2 个较小者个较小者两两进行比较两两进行比较，选取，选取 n/4 个较小者个较小者 如此重复，直到只剩如此重复，直到只剩1个关键字为止个关键字为止。该过程可用一棵有

44、该过程可用一棵有n个叶子结点的完全二叉树表示，如个叶子结点的完全二叉树表示，如图图9-9所示。所示。每个枝结点的关键字都等于其左、右孩子结点中较每个枝结点的关键字都等于其左、右孩子结点中较小的关键字，小的关键字，根结点的关键字就是最小的关键字根结点的关键字就是最小的关键字。输出最小关键字后输出最小关键字后，根据，根据关系的可传递性关系的可传递性，欲选取，欲选取次小关键字，只需将叶子结点中的最小关键字改为次小关键字，只需将叶子结点中的最小关键字改为“最最大值大值”，然后重复上述步骤即可，然后重复上述步骤即可。含有含有n个叶子结点的完全二叉树的深度为个叶子结点的完全二叉树的深度为 2n+1，则总的

45、时间复杂度为则总的时间复杂度为O(n2n)。492525372828196519153415251515图图9-“淘汰赛淘汰赛”过程示意图过程示意图9.4.3 堆排序堆排序1 堆的定义堆的定义 是是n个元素的序列个元素的序列H=k1,k2,kn，满足满足：kik2i 当当2in时时kik2i+1 当当2i+1n时时或或kik2i 当当2in时时ki k2i+1 当当2i+1n时时其中其中：i=1,2,n/2 由堆的定义知由堆的定义知，堆是一棵以，堆是一棵以k1为根的完全二叉树为根的完全二叉树。若对该二叉树的结点进行编号若对该二叉树的结点进行编号(从上到下从上到下，从左到右从左到右)，得到的序列

46、就是将二叉树的结点以得到的序列就是将二叉树的结点以顺序结构存放顺序结构存放，堆的，堆的结构正好和该序列结构完全一致结构正好和该序列结构完全一致。2 堆的性质堆的性质 堆是一棵采用顺序存储结构的完全堆是一棵采用顺序存储结构的完全二叉树二叉树，k1是是根结点；根结点；堆的根结点是关键字序列中的最小堆的根结点是关键字序列中的最小(或最大或最大)值值，分别称为小分别称为小(或大或大)根堆；根堆；从根结点到每一叶子结点路径上的元素组成的序从根结点到每一叶子结点路径上的元素组成的序列都是按元素值列都是按元素值(或关键字值或关键字值)非递减非递减(或非递增或非递增)的；的；堆中的任一子树也是堆堆中的任一子树

47、也是堆。利用堆顶记录的关键字值最小利用堆顶记录的关键字值最小(或最大或最大)的性质的性质，从，从当前待排序的记录中当前待排序的记录中依次选取关键字依次选取关键字最小最小(或最大或最大)的记的记录，就可以实现对数据记录的排序，这种排序方法称为录，就可以实现对数据记录的排序，这种排序方法称为堆排序堆排序。3 堆排序思想堆排序思想 对一组待排序的记录，按堆的定义对一组待排序的记录，按堆的定义建立堆建立堆；将将堆顶记录和最后一个记录交换堆顶记录和最后一个记录交换位置位置，则前，则前n-1个记录是无序的个记录是无序的，而最后，而最后一个记录是有序的一个记录是有序的；堆顶记录堆顶记录被交换后被交换后，前，

48、前n-1个记录不再是堆个记录不再是堆，需，需将前将前n-1个待排序记录重新组织成为一个堆个待排序记录重新组织成为一个堆，然后，然后将将堆顶记录和倒数第二个记录交换堆顶记录和倒数第二个记录交换位置位置，即将整个序，即将整个序列中次小关键字值的记录调整列中次小关键字值的记录调整(排除排除)出无序区出无序区；重复上述步骤重复上述步骤，直到全部记录排好序为止，直到全部记录排好序为止。结论结论：排序过程中，排序过程中，若若采用采用小根堆小根堆，排序后得到的是，排序后得到的是非递减序列非递减序列；若；若采用采用大根堆大根堆，排序后得到的是，排序后得到的是非递增序非递增序列列。堆堆排序的关键排序的关键 如何

49、由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？成为一个新的堆？4 堆的调整堆的调整筛选筛选 堆的调整思想堆的调整思想 输出堆顶元素之后，以堆中最后一个元素替代之；输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换与其中小者进行交换；重复上述操作，直到是叶子结点；重复上述操作，直到是叶子结点或其关键字值小于等于左、右子树的关键字的值，将得或其关键字值小于等于左、右子树的关键字的值，

50、将得到新的堆。称这个从堆顶至叶子的调整过程为到新的堆。称这个从堆顶至叶子的调整过程为“筛选筛选”，如图，如图9-10所示所示。注意注意：筛选过程中，根结点的左、右子树都是堆，因筛选过程中，根结点的左、右子树都是堆，因此，筛选是从根结点到某个叶子结点的一次调整过程此，筛选是从根结点到某个叶子结点的一次调整过程。图图9-10 堆的筛选过程堆的筛选过程49253728196534182715492537281965342718154927372819653425181549253728196534181527 堆调整堆调整算法实现算法实现void Heap_adjust(Sqlist*H,int s