数据结构第9章排序优秀PPT.ppt

第第9章章 排排 序序 在信息处理过程中，最基本的操作是查找。从查在信息处理过程中，最基本的操作是查找。从查找来说，效率最高的是折半查找，折半查找的前提是全找来说，效率最高的是折半查找，折半查找的前提是全部的数据元素部的数据元素(记录记录)是按关键字有序的。须要将一个无是按关键字有序的。须要将一个无序的数据文件转变为一个有序的数据文件。序的数据文件转变为一个有序的数据文件。将任一文件中的记录通过某种方法整理成为按将任一文件中的记录通过某种方法整理成为按(记记录录)关键字有序排列的处理过程称为排序。关键字有序排列的处理过程称为排序。排序是数据处理中一种最常用的操作。排序是数据处理中一种最常用的操作。9.1 排序的基本概念排序的基本概念 排序排序(Sorting)(Sorting)排序是将一批排序是将一批(组组)随意次序的记录重新随意次序的记录重新排列成按关键字有序的记录序列的过程，其定义排列成按关键字有序的记录序列的过程，其定义为：为：给定一组记录序列：给定一组记录序列：R1,R2,R1,R2,RnRn，其相应的关键字序列是，其相应的关键字序列是K1,K2,Kn K1,K2,Kn。确定。确定1,2,n1,2,n的一个排列的一个排列p1,p2,pnp1,p2,pn，使其相应的关键字满足如下非递减，使其相应的关键字满足如下非递减(或非递增或非递增)关系：关系：Kp1Kp2 Kpn Kp1Kp2 Kpn的序列的序列Kp1,Kp2,Kp1,Kp2,Kpn,Kpn，这种操作称为排序。，这种操作称为排序。关键字关键字KiKi可以是记录可以是记录RiRi的主关键字，也的主关键字，也可以是次关键字或若干数据项的组合。可以是次关键字或若干数据项的组合。Ki是主关键字：排序后得到的结果是唯一的；是主关键字：排序后得到的结果是唯一的；Ki是次关键字：排序后得到的结果是不唯一的。是次关键字：排序后得到的结果是不唯一的。排序的稳定性排序的稳定性 若记录序列中有两个或两个以上关键字相等的记录：若记录序列中有两个或两个以上关键字相等的记录：Ki=Kj(ij，i,j=1,2,n)，且在排序前，且在排序前Ri先于先于Rj(ij)，排序后的，排序后的记录序列仍旧是记录序列仍旧是Ri先于先于Rj，称排序方法是稳定的，否则是不，称排序方法是稳定的，否则是不稳定的。稳定的。排序算法有很多，但就全面性能而言，还没有一种公认排序算法有很多，但就全面性能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合不同的数为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。据量和硬件配置。评价排序算法的标准有：执行时间和所需的协助空间，评价排序算法的标准有：执行时间和所需的协助空间，其次是算法的稳定性。其次是算法的稳定性。若排序算法所需的协助空间不依靠问题的规模若排序算法所需的协助空间不依靠问题的规模n，即空间困难度是即空间困难度是O(1)，则称排序方法是就地排序，否则，则称排序方法是就地排序，否则是非就地排序。是非就地排序。排序的分类排序的分类 待排序的记录数量不同，排序过程中涉及的存储器待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。的不同，有不同的排序分类。待排序的记录数不太多：全部的记录都能存放在内待排序的记录数不太多：全部的记录都能存放在内存中进行排序，称为内部排序；存中进行排序，称为内部排序；待排序的记录数太多：全部的记录不行能存放在内待排序的记录数太多：全部的记录不行能存放在内存中，存中，排序过程中必需在内、外存之间进行数据交换，排序过程中必需在内、外存之间进行数据交换，这样的排序称为外部排序。这样的排序称为外部排序。内部排序的基本操作内部排序的基本操作 对内部排序地而言，其基本操作有两种：对内部排序地而言，其基本操作有两种：比较两个关键字的大小；比较两个关键字的大小；存储位置的移动：从一个位置移到另一个位存储位置的移动：从一个位置移到另一个位置。置。第一种操作是必不行少的；而其次种操第一种操作是必不行少的；而其次种操作却不是必需的，取决于记录的存储方式，具体作却不是必需的，取决于记录的存储方式，具体状况是：状况是：记录存储在一组连续地址的存储空间：记录记录存储在一组连续地址的存储空间：记录之间的逻辑依次关系是通过其物理存储位置的相之间的逻辑依次关系是通过其物理存储位置的相邻来体现，记录的移动是必不行少的；邻来体现，记录的移动是必不行少的；记录接受链式存储方式：记录之间的逻辑依记录接受链式存储方式：记录之间的逻辑依次关系是通过结点中的指针来体现，排序过程仅次关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不须要移动记录；需修改结点的指针，而不须要移动记录；记录存储在一组连续地址的存储空间：构造另一记录存储在一组连续地址的存储空间：构造另一个协助表来保存各个记录的存放地址个协助表来保存各个记录的存放地址(指针指针)：排：排序过程不须要移动记录，而仅需修改协助表中的序过程不须要移动记录，而仅需修改协助表中的指针，排序后视具体状况确定是否调整记录的存指针，排序后视具体状况确定是否调整记录的存储位置。储位置。比较适合记录数较少的状况；而比较适合记录数较少的状况；而、则则适合记录数较多的状况。适合记录数较多的状况。为探讨便利，假设待排序的记录是以为探讨便利，假设待排序的记录是以的状的状况存储，且设排序是按升序排列的；关键字是一况存储，且设排序是按升序排列的；关键字是一些可干脆用比较运算符进行比较的类型。些可干脆用比较运算符进行比较的类型。待排序的记录类型的定义如下：待排序的记录类型的定义如下：#define MAX_SIZE 100Typedef int KeyType;typedef struct RecType KeyType key;/*关键字码关键字码 */infoType otherinfo;/*其他域其他域 */RecType;typedef struct Sqlist RecType RMAX_SIZE;int length ;Sqlist;9.2 插入排序插入排序 接受的是以“玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的全部记录R1,R2,.,Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。最基本的插入排序是干脆插入排序(Straight Insertion Sort)。9.2.1 干脆插入排序干脆插入排序1 排序思想排序思想 将待排序的记录将待排序的记录Ri，插入到已排好序的，插入到已排好序的记录表记录表R1,R2,.,Ri-1中，得到一个新的、中，得到一个新的、记录数增加记录数增加1的有序表。的有序表。直到全部的记录都直到全部的记录都插入完为止。插入完为止。设待排序的记录依次存放在数组设待排序的记录依次存放在数组R1n中，在排序的某一时刻，将记录序中，在排序的某一时刻，将记录序列分成两部分：列分成两部分：R1i-1：已排好序的有序部分；：已排好序的有序部分；Rin：未排好序的无序部分。：未排好序的无序部分。明显，在刚起先排序时，明显，在刚起先排序时，R1是已经排是已经排好序的。好序的。例：设有关键字序列为：例：设有关键字序列为：7,4,-2,19,13,7,4,-2,19,13,6 6，干脆插入排序的过程如下图，干脆插入排序的过程如下图9-19-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;/*设置哨兵设置哨兵 */while(LT(L-R0.key,L-Rj.key)L-Rj+1=L-Rj;j-;/*查找插入位置查找插入位置 */L-Rj+1=L-R0;/*插入到相应位置插入到相应位置 */3 算法算法说说明明 算法中的算法中的R0起先起先时时并不存放任何待排序并不存放任何待排序的的记录记录，引入的作用主要有两个：，引入的作用主要有两个：不不须须要增加要增加协协助空助空间间：保存当前待插入保存当前待插入的的记录记录Ri，Ri会因会因为记录为记录的后移而被占的后移而被占用；用；保保证查证查找插入位置的内循找插入位置的内循环总环总可以在超可以在超出循出循环边环边界之前找到一个等于当前界之前找到一个等于当前记录记录的的记录记录，起，起“哨兵哨兵监视监视”作用，避开在内循作用，避开在内循环环中每次都要推断中每次都要推断j是否越界。是否越界。4 算法分析算法分析 最好状况：若待排序记录按关键字从小最好状况：若待排序记录按关键字从小到大排列到大排列(正序正序)，算法中的内循环无须执，算法中的内循环无须执行，则一趟排序时：关键字比较次数行，则一趟排序时：关键字比较次数1次，次，记录移动次数记录移动次数2次次(RiR0,R0Rj+1)。则整个排序的关键字比较次数和记录则整个排序的关键字比较次数和记录移动次数分别是：移动次数分别是：比较次数比较次数：1=n-1ni=2移动次数移动次数：2=2(n-1)ni=2 最坏状况：若待排序记录按关键字从大到最坏状况：若待排序记录按关键字从大到小排列小排列(逆序逆序)，则一趟排序时：算法中的内循，则一趟排序时：算法中的内循环体执行环体执行i-1i-1，关键字比较次数，关键字比较次数i i次，记录移动次，记录移动次数次数i+1i+1。则就整个排序而言：则就整个排序而言：比较次数比较次数：i=ni=2(n-1)(n+1)2移动次数移动次数：(i+1)=ni=2(n-1)(n+4)2 一般地，认为待排序的记录可能出现的各种排列的一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种状况的平均值，作为排序的关概率相同，则取以上两种状况的平均值，作为排序的关键字比较次数和记录移动次数，约为键字比较次数和记录移动次数，约为n2/4n2/4，则困难度为，则困难度为O(n2)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;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)O(n2)。排序示例排序示例 设有一组关键字设有一组关键字30,13,70,85,39,42,6,2030,13,70,85,39,42,6,20，接受折半插入排序方法排序的过程如图，接受折半插入排序方法排序的过程如图9-29-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 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插插入到入到d1之前的有序表中；之前的有序表中；L-Ri.keyd1.key：L-Ri插插入到入到d1之后的有序表中；之后的有序表中；关键点：实现时将向量关键点：实现时将向量d看成是循环向量，并设看成是循环向量，并设两个指针两个指针first和和final分别指示排序过程中得到的分别指示排序过程中得到的有序序列中的第一个和最终一个记录。有序序列中的第一个和最终一个记录。排序示例排序示例设有初始关键字集合设有初始关键字集合49,38,65,13,97,27,76，接受，接受2-路插入排序的过程如右图路插入排序的过程如右图9-3所示。所示。在在2-路插入排序中，移动记录的次数约为路插入排序中，移动记录的次数约为n2/8。但当。但当L-R1是待排序记录中关键字最大是待排序记录中关键字最大或最小的记录时，或最小的记录时，2-路插入排序就完全失去了优路插入排序就完全失去了优越性。越性。2776d49firstfirstfirstfirstfinalfinalfinalfinal653897971313图图9-3 2-路插入排序过程路插入排序过程3 表插入排序表插入排序前面的插入排序不行避开地要移动记前面的插入排序不行避开地要移动记录，若不移动记录就须要变更数据结录，若不移动记录就须要变更数据结构。附加构。附加n个记录的协助空间，记录类个记录的协助空间，记录类型修改为：型修改为：typedef struct RecNode KeyType key;infotype otherinfo;int*next;RecNode;初始化：下标值为初始化：下标值为0的重量作为表头结点，关键字取为的重量作为表头结点，关键字取为最大值，各重量的指针值为空；最大值，各重量的指针值为空；将静态链表中数组下标值为将静态链表中数组下标值为1的重量的重量(结点结点)与表头结与表头结点构成一个循环链表；点构成一个循环链表；i=2，将重量，将重量Ri按关键字递减插入到循环链表；按关键字递减插入到循环链表；增加增加i，重复，重复，直到全部重量插入到循环链表。，直到全部重量插入到循环链表。例：设有关键字集合例：设有关键字集合49,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 -和干脆插入排序相比，不同的是修改和干脆插入排序相比，不同的是修改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 49 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+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 13 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;for(j=d+1;jlength;j+)L-R0=L-Rj;/*设设置置监视监视哨兵哨兵 */k=j-d;while(k0&LT(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的关键字的关键字)，则，则交换两个记录交换两个记录；然后比较然后比较L-R2与与L-R3的关键字的关键字，依此类推，直到依此类推，直到L-Rn-1与与L-Rn的关键字比较后的关键字比较后为止为止，称为一趟，称为一趟冒泡排序冒泡排序，L-Rn为关键字最大的为关键字最大的记录记录。然后进行其次趟冒泡排序，对前然后进行其次趟冒泡排序，对前n-1n-1个记录进行个记录进行同样的操作。同样的操作。一般地，第一般地，第i i趟冒泡排序是对趟冒泡排序是对L-R1 n-i+1L-R1 n-i+1中的记录进行的，因此，若待排序的记录有中的记录进行的，因此，若待排序的记录有n n个，则个，则要经过要经过n-1n-1趟冒泡排序才能使全部的记录有序。趟冒泡排序才能使全部的记录有序。2 2 排序示例排序示例 设有设有9 9个待排序的记录，关键字分别为个待排序的记录，关键字分别为23,23,38,22,45,23,67,31,15,4138,22,45,23,67,31,15,41，冒泡排序的过程，冒泡排序的过程如图如图9-69-6所示。所示。3 3 算法实现算法实现#define FALSE 0#define FALSE 0#define TRUE 1#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 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+)/*一趟排序一趟排序 */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)T(n)=O(n)空间困难度：空间困难度：S(n)=O(1)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 排序思想排序思想 通过一趟排序，将待排序记录分割成独立的通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序。一趟排序，以达到整个序列有序。2 排序过程排序过程 设待排序的记录序列是设待排序的记录序列是Rst，在记录序，在记录序列中任取一个记录列中任取一个记录(一般取一般取Rs)作为参照作为参照(又称为又称为基准或枢轴基准或枢轴)，以，以Rs.key为基准重新排列其余为基准重新排列其余的全部记录，方法是：的全部记录，方法是：全部关键字比基准小的放全部关键字比基准小的放Rs之前；之前；全部关键字比基准大的放全部关键字比基准大的放Rs之后。之后。以以Rs.key最终所在位置最终所在位置i作为分界，将序列作为分界，将序列Rst分割成两个子序列，称为一趟快速排序。分割成两个子序列，称为一趟快速排序。3 一趟快速排序方法一趟快速排序方法 从序列的两端交替扫描各个记录，将关键字小于从序列的两端交替扫描各个记录，将关键字小于基准关键字的记录依次放置到序列的前边；而将关键基准关键字的记录依次放置到序列的前边；而将关键字大于基准关键字的记录从序列的最终端起，依次放字大于基准关键字的记录从序列的最终端起，依次放置到序列的后边，直到扫描完全部的记录。置到序列的后边，直到扫描完全部的记录。设置指针设置指针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所指位置起向后搜寻：将所指位置起向后搜寻：将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-R0;return(i);快速排序算法快速排序算法实现实现 当当进进行一趟快速排序后，接受同行一趟快速排序后，接受同样样方法分方法分别对别对两个子序列快速排序，直到两个子序列快速排序，直到子序列子序列记录记录个个为为1 1为为止。止。递归递归算法算法 void quick_Sort(Sqlist *L,int void quick_Sort(Sqlist *L,int low,int high)low,int high)int k;int k;if (lowhigh)if (lowhigh)k=quick_one_pass(L,low,high);k=quick_one_pass(L,low,high);quick_Sort(L,low,k-1);quick_Sort(L,low,k-1);quick_Sort(L,k+1,high);quick_Sort(L,k+1,high);/*/*序列分序列分为为两部分后分两部分后分别对别对每个每个子序列排序子序列排序 */*/非递归算法非递归算法#define MAX_STACK 100#define MAX_STACK 100void quick_Sort(Sqlist *L,int low,int void quick_Sort(Sqlist *L,int low,int high)high)int k,stackMAX_STACK,top=0;int k,stackMAX_STACK,top=0;do while (lowhigh)do while (lowhigh)k=quick_one_pass(L,low,high);k=quick_one_pass(L,low,high);stack+top=high;stack+top=k+1 stack+top=high;stack+top=k+1;/*/*其次个子序列的上其次个子序列的上,下界分别入下界分别入栈栈 */*/high=k-1;high=k-1;if(top!=0)if(top!=0)low=stacktop-;high=stacktop-low=stacktop-;high=stacktop-;while(top!=0&low1时，用时，用n-1代替代替中的中的n，得到，得到：Tavg(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(n2n)从所须要的附加空间来看，快速排序算法是递归从所须要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较调用，系统内用堆栈保存递归参数，当每次划分比较匀整时，栈的最大深度为匀整时，栈的最大深度为2n+1。快速排序的空间困难度是：快速排序的空间困难度是：S(n)=O(2n)从排序的稳定性来看，快速排序是不稳定的。从排序的稳定性来看，快速排序是不稳定的。9.4 选择排序选择排序 选择排序选择排序(Selection Sort)的基本思想是：每次的基本思想是：每次从当前从当前待排序的记录待排序的记录中选取关键字最小的中选取关键字最小的记录，然后与记录，然后与待排序的记录序列待排序的记录序列中的第中的第一个记录进行交换，直到整个一个记录进行交换，直到整个记录序列有序为止记录序列有序为止。9.4.1 简洁选择排序简洁选择排序 简洁选择排序简洁选择排序(Simple Selection Sort，又，又称为干脆选择排序称为干脆选择排序)的基本操作是：通过的基本操作是：通过n-i次关次关键字间的比较，从键字间的比较，从n-i+1个记录中选取关键字最小个记录中选取关键字最小的记录，然后和第的记录，然后和第i个记录进行交换，个记录进行交换，i=1,2,n-1。1 排序示例排序示例 例：设有关键字序列为：例：设有关键字序列为：7,4,-2,19,13,6，干脆选择排序的过程如下图干脆选择排序的过程如下图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;mlength;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 时间困难度是：时间困难度是：T(n)=O(n2)T(n)=O(n2)空间困难度是：空间困难度是：S(n)=O(1)S(n)=O(1)从排序的稳定性来看，干脆选择排序是不稳定的。从排序的稳定性来看，干脆选择排序是不稳定的。9.4.2 树形选择排序树形选择排序 借助借助“淘汰赛淘汰赛”中的对垒就很简洁理解树形选择排序的思想。中的对垒就很简洁理解树形选择排序的思想。首先对首先对n n个记录的关键字两两进行比较，选取个记录的关键字两两进行比较，选取 n/2n/2 个较小个较小者；然后这者；然后这 n/2n/2 个较小者两两进行比较，选取个较小者两两进行比较，选取 n/4n/4 个较小者个较小者 如此重复，直到只剩如此重复，直到只剩1 1个关键字为止。个关键字为止。该过程可用一棵有该过程可用一棵有n n个叶子结点的完全二叉树表示，如图个叶子结点的完全二叉树表示，如图9-99-9所示。所示。每个枝结点的关键字都等于其左、右孩子结点中较小的每个枝结点的关键字都等于其左、右孩子结点中较小的关键字，根结点的关键字就是最小的关键字。关键字，根结点的关键字就是最小的关键字。输出最小关键字后，依据关系的可传递性，欲选取输出最小关键字后，依据关系的可传递性，欲选取次小关键字，只需将叶子结点中的最小关键字改为次小关键字，只需将叶子结点中的最小关键字改为“最最大值大值”，然后重复上述步骤即可。，然后重复上述步骤即可。含有含有n n个叶子结点的完全二叉树的深度为个叶子结点的完全二叉树的深度为 2n2n+1+1，则总的时间困难度为，则总的时间困难度为O(nO(n2n)2n)。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为根的完全二叉树。为根的完全二叉树。若对该二叉树的结点进行编号若对该二叉树的结点进行编号(从上到下，从左到右从上到下，从左到右)，得到的序列就是将二叉树的结点以依次结构存放，堆的得到的序列就是将二叉树的结点以依次结构存放，堆的结构正好和该序列结构完全一样。结构正好和该序列结构完全一样。2 堆的性质堆的性质 堆是一棵接受依次存储结构的完全二叉堆是一棵接受依次存储结构的完全二叉树，树，k1是根结点；是根结点；堆的根结点是关键字序列中的最小堆的根结点是关键字序列中的最小(或或最大最大)值，分别称为小值，分别称为小(或大或大)根堆；根堆；从根结点到每一叶子结点路径上的元素从根结点到每一叶子结点路径上的元素组成的序列都是按元素值组成的序列都是按元素值(或关键字值或关键字值)非非递减递减(或非递增或非递增)的；的；堆中的任一子树也是堆。堆中的任一子树也是堆。利用堆顶记录的关键字值最小利用堆顶记录的关键字值最小(或最大或最大)的性质，从当前待排序的记录中依次选取的性质，从当前待排序的记录中依次选取关键字最小关键字最小(或最大或最大)的记录，就可以实现的记录，就可以实现对数据记录的排序，这种排序方法称为堆对数据记录的排序，这种排序方法称为堆排序。排序。3 堆排序思想堆排序思想 对对一一组组待排序的待排序的记录记录，按堆的定，按堆的定义义建立建立堆；堆；将堆将堆顶记录顶记录和最和最终终一个一个记录记录交交换换位置，位置，则则前前n-1个个记录记录是无序的，而最是无序的，而最终终一个一个记录记录是有序的；是有序的；堆堆顶记录顶记录被交被交换换后，前后，前n-1个个记录记录不再不再是堆，需将前是堆，需将前n-1个待排序个待排序记录记录重新重新组织组织成成为为一个堆，然后将堆一个堆，然后将堆顶记录顶记录和倒数其次个和倒数其次个记录记录交交换换位置，即将整个序列中次小关位置，即将整个序列中次小关键键字字值值的的记录调记录调整整(解除解除)出无序区；出无序区；重复上述步重复上述步骤骤，直到全部，直到全部记录记录排好序排好序为为止。止。结论结论：排序：排序过过程中，若接受小根堆，排序程中，若接受小根堆，排序后