84第9章 排序

1、数数数数数数据据据据据据结结结结结结构构构构构构学习要点学习要点 第第9 9章章 排序排序n理解和熟悉各种内部排序的基本思想和过程理解和熟悉各种内部排序的基本思想和过程n掌握内部排序算法的时间复杂度的分析方法和结掌握内部排序算法的时间复杂度的分析方法和结论论n要求能根据各种内部排序方法的优缺点及不同场要求能根据各种内部排序方法的优缺点及不同场合选择合适的排序方法合选择合适的排序方法 数数数数数数据据据据据据结结结结结结构构构构构构9.1 基本概念基本概念 排序就是把一组记录排序就是把一组记录(元素元素)按照某个域的值的递增按照某个域的值的递增(即由即由小到大小到大)或递减或递减(即由大到小即由

2、大到小)的次序重新排列的过程。的次序重新排列的过程。 一般情况下，假设含一般情况下，假设含n个记录的序列为个记录的序列为（r1, r2, , rn） 其相应关键字序列为其相应关键字序列为（k1, k2, , kn） 需确定一种排列，使关键字满足如下的递增的关系需确定一种排列，使关键字满足如下的递增的关系 ki1ki2kin 则按此关系将记录序列重新排列为则按此关系将记录序列重新排列为(ri1, ri2, , rin)的操的操作称之为排序。作称之为排序。数数数数数数据据据据据据结结结结结结构构构构构构表10-1 学生档案表学号学号姓名姓名年龄年龄性别性别990001王晓佳王晓佳18男男99000

3、2林一鹏林一鹏19男男990003谢宁谢宁17女女990004张丽娟张丽娟18女女在排序的过程中也要引入关键字的概念。所谓在排序的过程中也要引入关键字的概念。所谓关键字关键字是是指在一个记录中可以标识该数据项的值，它是排序运算的指在一个记录中可以标识该数据项的值，它是排序运算的重要依据。关键字的选取应根据需要而定，比如在学生档重要依据。关键字的选取应根据需要而定，比如在学生档案表中，可选择案表中，可选择“学号学号”为关键字来识别学生，也可选择为关键字来识别学生，也可选择“年龄年龄”为关键字对学生排序。为关键字对学生排序。 9.1 基本概念基本概念数数数数数数据据据据据据结结结结结结构构构构构构

4、 在上表中，若以每个记录的学号为关键字，可按排序码在上表中，若以每个记录的学号为关键字，可按排序码年龄年龄的递增的递增(由小到大由小到大)排序，则所有记录的排序，则所有记录的排序结果排序结果可简记为：可简记为：(99006,16),(99003,17),(99001,18),(99004,18),(99002,19),(99005,20)；也可能为也可能为：(99006,16),(99003,17),(99004,18),(99001,18),(99002,19),(99005,20)；这两个结果都是按年龄的递增排序结果。这两个结果都是按年龄的递增排序结果。 若按排序码若按排序码姓名姓名来进行

5、递增排序，则得到的来进行递增排序，则得到的排序结果排序结果为：为：(99006,李小燕李小燕),(99002,林一鹏林一鹏),(99001,王晓佳王晓佳),(99003,谢宁谢宁) (99004,张丽娟张丽娟),(99005,周涛周涛) 当然，我们还可以按排序码性别来进行递增排序，在此不再当然，我们还可以按排序码性别来进行递增排序，在此不再作进一步的分析。作进一步的分析。9.1 基本概念基本概念数数数数数数据据据据据据结结结结结结构构构构构构n排序的分类排序的分类按照排序过程中使用内、外存的不同，将排序方法分按照排序过程中使用内、外存的不同，将排序方法分为内部排序和外部排序。为内部排序和外部排

6、序。v内部排序：内部排序：如果待排序的记录放在计算机内存中进行排如果待排序的记录放在计算机内存中进行排序，整修排序过程不需要访问外存便能完成，则此类排序，整修排序过程不需要访问外存便能完成，则此类排序称为序称为。内排序分类：插入排序、交换排序、选择排序、归并内排序分类：插入排序、交换排序、选择排序、归并排序和分配排序。排序和分配排序。v外部排序：如果待外部排序：如果待排序的记录数量比较大，排序期间文排序的记录数量比较大，排序期间文件的全部记录不能同时存放在计算机的内存里，排序过件的全部记录不能同时存放在计算机的内存里，排序过程中需要不断地进行内存和外存之间的数据交换，则此程中需要不断地进行内存

7、和外存之间的数据交换，则此类排序称为类排序称为 。9.1 基本概念基本概念数数数数数数据据据据据据结结结结结结构构构构构构n稳定性稳定性在待排序的序列中，关键字可以是记录的主关键字，在待排序的序列中，关键字可以是记录的主关键字，也可以是记录的次关键字，或是若干数据项的组合。也可以是记录的次关键字，或是若干数据项的组合。v由主关键字的定义可知，任何一个记录的无序序列经排由主关键字的定义可知，任何一个记录的无序序列经排序后得到的结果是唯一的。序后得到的结果是唯一的。v若是次关键字，排序的结果不唯一，因为等待排序的记若是次关键字，排序的结果不唯一，因为等待排序的记录序列中可能存在两个或两个以上关键字

8、相等的记录。录序列中可能存在两个或两个以上关键字相等的记录。若采用的排序方法使具有相同关键字的记录在排序过程若采用的排序方法使具有相同关键字的记录在排序过程中相对次序不变，则称此排序方法是稳定的，否则称为中相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。不稳定的。v例如：假定一组记录为例如：假定一组记录为(15,67,23,15,40)，其中关键字同，其中关键字同为为15的记录有两个。的记录有两个。9.1 基本概念基本概念数数数数数数据据据据据据结结结结结结构构构构构构n排序的时间复杂性排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移排序过程主要是对记录的排序码进行比较和

9、记录的移动过程。因此动过程。因此排序的时间复杂性可以算法执行中的数据排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。比较次数及数据移动次数来衡量。n有序表与无序表有序表与无序表一组记录按排序关键字的递增或递减次序排列得到的一组记录按排序关键字的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无结果被称之为有序表，相应地，把排序前的状态称为无序表。序表。n正序表与逆序表正序表与逆序表若有序表是按排序码升序排列的，则称为升序表或正若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性，我们一序表，否则称为降序表或逆序表。不失普

10、遍性，我们一般只讨论正序表。般只讨论正序表。9.1 基本概念基本概念数数数数数数据据据据据据结结结结结结构构构构构构#define maxsize 20/* 存储空间的最大值 */typedef int keytype;/* 定义关键字为整数类型 */typedef structkeytype key;/* 关键字域 */infotype otherinfo; /* 其它数据域 */ redtype;/* 记录类型 */typedef struct redtype rmaxsize+1; /* r0用作监视哨单元 */int length ;/* 顺序表长度 */ sqlist; n存储结构存

11、储结构在本章讨论的算法通常采用顺序存储结构，用一维数在本章讨论的算法通常采用顺序存储结构，用一维数组来实现，且记录按照关键字递增的顺序排列。组来实现，且记录按照关键字递增的顺序排列。9.1 基本概念基本概念数数数数数数据据据据据据结结结结结结构构构构构构9.2 插入排序插入排序n基本思想基本思想每次只考虑一个待排序的元素，用这个元素同已经每次只考虑一个待排序的元素，用这个元素同已经排序好的其他元素逐一进行比较，在找到适当的位置排序好的其他元素逐一进行比较，在找到适当的位置后，将此记录插入，从而得到一个新的有序表，然后后，将此记录插入，从而得到一个新的有序表，然后再选择下一待排列的元素。再选择下

12、一待排列的元素。9.2.1 直接插入排序直接插入排序数数数数数数据据据据据据结结结结结结构构构构构构n基本步骤基本步骤n初始状态：初始状态：排序开始之前，整个数组被排序开始之前，整个数组被r分为两个部分为两个部分：有序部分和无序部分。有序部分存放的是已经分：有序部分和无序部分。有序部分存放的是已经排序好的记录；无序部分存放的是尚未排好的记录。排序好的记录；无序部分存放的是尚未排好的记录。初始有序部分为初始有序部分为r1，无序部分为，无序部分为r2到到rn。n终止状态：终止状态：有序部分存放的是整个数组，无序部分有序部分存放的是整个数组，无序部分为空。为空。n基本操作：基本操作：每次从无序部分取

13、出一个记录（第一个）每次从无序部分取出一个记录（第一个）将其同有序部分中的元素相比较，并按照关键字大将其同有序部分中的元素相比较，并按照关键字大小将其插入到合适位置，使有序部分始终有序。直小将其插入到合适位置，使有序部分始终有序。直至全部记录插入完毕。至全部记录插入完毕。9.2.1 直接插入排序直接插入排序数数数数数数据据据据据据结结结结结结构构构构构构9.2.1 直接插入排序直接插入排序n算法描述算法描述初值：待记录放在无序部分的数组初值：待记录放在无序部分的数组r1.n中。中。1)在有序部分中有在有序部分中有1个元素个元素r1，无序部分元素为，无序部分元素为r2.n；2)令令i=2，将，将

14、r2作为排序元素；作为排序元素；3)把把r2放到放到r0中，中， r0即作为暂存单元，又可作为后面即作为暂存单元，又可作为后面循环比较用的循环比较用的“监视哨监视哨”；4)取辅助参数取辅助参数j=i-1，其作用是记录，其作用是记录待比较元素的下标待比较元素的下标（有（有序部分），其位置在序部分），其位置在i的前面；的前面；5)将将r0的关键字与的关键字与rj的关键字相比较；的关键字相比较；数数数数数数据据据据据据结结结结结结构构构构构构9.2.1 直接插入排序直接插入排序6)若若r0的关键字小于的关键字小于rj的关键字，则的关键字，则rj后移一个位后移一个位置，并继续搜索前面的元素，即置，并继

15、续搜索前面的元素，即j=j-1，然后转向，然后转向5。7)若若r0的关键字大于的关键字大于rj的关键字，故的关键字，故r0应放在应放在rj的的后面，即在后面，即在j+1的位置。的位置。8)令令i = i +1，若此时，若此时i n，则排序完成，否则转入，则排序完成，否则转入4。数数数数数数据据据据据据结结结结结结构构构构构构n设记录关键字分别为设记录关键字分别为49,38,65,97,76,13,27,49。为了检。为了检测稳定性，我们在后一个测稳定性，我们在后一个49上加了一个横线。具体排上加了一个横线。具体排序过程如图所示：序过程如图所示：初始关键字初始关键字 r0 49 38 65 97

16、 76 13 27 49j=2 (38) 38 49 65 97 76 13 27 49 j=3 (65) 38 49 65 97 76 13 27 49j=4 (97) 38 49 65 97 76 13 27 49 j=5 (76) 38 49 65 76 97 13 27 49j=6 (13) 13 38 49 65 76 97 27 49j=7 (27) 13 27 38 49 65 76 97 49j=8 (49) 13 27 38 49 49 65 76 979.2.1 直接插入排序直接插入排序数数数数数数据据据据据据结结结结结结构构构构构构n直接插入排序算法：直接插入排序算法：v

17、oid insertsort(sqlist &l) for(i=2;i=l.length;+i) if(l.ri.keyl.ri-1.key) /需将l.ri插入有序表 l.r0=l.ri; /复制为哨兵 for(j=i-1;l.r0.keyl.rj.key;-j)l.rj+1 = l.rj; /记录后移 l.rj+1 = l.r0; /插入到正确位置 9.2.1 直接插入排序直接插入排序数数数数数数据据据据据据结结结结结结构构构构构构n时间复杂度时间复杂度v若初始记录按关键字若初始记录按关键字递增排列递增排列，所需进行关键字比较次，所需进行关键字比较次数达最小值为数达最小值为n-1，

18、记录不需移动。时间复杂度是，记录不需移动。时间复杂度是o(n)。v在在反序情况反序情况下，由于第下，由于第i个记录的找到相应插入位置需要个记录的找到相应插入位置需要比较比较i次，所以从第次，所以从第2到第到第n个记录共需比较的总次数为：个记录共需比较的总次数为：cmax= =(n+2)(n-1)/2=o(n2) 每次首先要将每次首先要将ri移到移到r0，故每趟移动比比较多一次，则，故每趟移动比比较多一次，则记录移动的总次数为：记录移动的总次数为： mmax= =(n+4)(n-1)/2=o(n2) v时间复杂度最好情况为时间复杂度最好情况为o(n),最坏情况为最坏情况为o(n2)。平均时间。平

19、均时间复杂度为复杂度为o(n2)，由于辅助空间只有，由于辅助空间只有r0，s(n)=o(1)。直。直接插入排序为稳定的排序方法。接插入排序为稳定的排序方法。nii2nii219.2.1 直接插入排序直接插入排序数数数数数数据据据据据据结结结结结结构构构构构构9.2.3 希尔排序希尔排序n基本思想基本思想先将整个待排序的记录序列分割为若干个子序列并先将整个待排序的记录序列分割为若干个子序列并分别进行直接插入排序，待整个序列中的记录基本有分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。序时，再对全体记录进行一次直接插入排序。n基本步骤基本步骤在直接插入排序中，

20、当在直接插入排序中，当n较小时，排序的效率比较高。较小时，排序的效率比较高。shell将待排序的记录按照距离将待排序的记录按照距离d(增量增量)分成若干个组，分成若干个组，把所有下标值相差把所有下标值相差d倍数的记录放在一组，然后在各组倍数的记录放在一组，然后在各组内进行直接插入排序。内进行直接插入排序。然后改变然后改变d的值，使其逐步缩小，各组内的记录逐渐的值，使其逐步缩小，各组内的记录逐渐增多。各组的记录随着增多。各组的记录随着d的变小而趋向有序。因而重新的变小而趋向有序。因而重新分组后，排序速度较快。当增量减小到分组后，排序速度较快。当增量减小到1时，已达到基时，已达到基本有序，最后再进

21、行直接插入排序。本有序，最后再进行直接插入排序。 数数数数数数据据据据据据结结结结结结构构构构构构n对以下序列按照非递减的顺序进行排列。49 38 65 97 76 13 27 48 55 4其中各步的步长依次为5、3和1。取d3=1三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分组：49 38 65 97 76 13 27 48 55 4取d2=3二趟分组：13

22、27 48 55 4 49 38 65 97 769.2.3 希尔排序希尔排序数数数数数数据据据据据据结结结结结结构构构构构构9.2.3 希尔排序希尔排序n希尔排序算法：void shellsort(sqlist &l,int d,int t)for(k=0;kt;+k)shellinsert(l, dk); /* 一趟增量为dk的插入排序 */void shellinsert(sqlist &l,int dk)for (i=dk+1;i=l.length;+i) if(l.ri.key0)&(l.r0.keyl.rj.key);j-=dk)l.rj+dk=l.rj;/

23、* 记录后移找插入位置*/l.rj+dk=l.r0;/* 插入l.ri*/ void insertsort(sqlist &l)for(i=2;i=l.length;+i)if(l.ri.keyl.ri-1.key)/需将l.ri插入有序表 l.r0=l.ri;/复制为哨兵for(j=i-1;l.r0.keyl.rj.key;-j)l.rj+1 = l.rj;/记录后移l.rj+1 = l.r0;/插入到正确位置数数数数数数据据据据据据结结结结结结构构构构构构n算法分析算法分析v时间复杂度时间复杂度希尔排序算法的速度是所取的增量序列希尔排序算法的速度是所取的增量序列di的函数。增量的函

24、数。增量序列的选取是一件困难的事。一般认为，希尔排序的序列的选取是一件困难的事。一般认为，希尔排序的时间复杂度为时间复杂度为o(nlog2n)。v空间复杂度空间复杂度空间复杂度为空间复杂度为o(1)。 v稳定性稳定性由于由于shell排序是分组进行排序，它是跳跃式向前移动，排序是分组进行排序，它是跳跃式向前移动，会导致相等关键字中原来在后面的关键字移到前面，会导致相等关键字中原来在后面的关键字移到前面，所以希尔排序是不稳定的排序方法。所以希尔排序是不稳定的排序方法。9.2.3 希尔排序希尔排序数数数数数数据据据据据据结结结结结结构构构构构构9.3 交换排序交换排序9.3.1 起泡排序起泡排序基

25、本思想：基本思想：首先将第一个记录的关键字和第二个记录的关键字首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第记录和第三个记录的关键字。依次类推，直至第n-1个记录和第个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得排序，其结果使得关键字最大的记录被安置到最后一个记录关键字最大的记录被安置到最后一个记录的的位置上。然后进行第二趟起泡排序，对前位置上。然后进行第二趟起泡

26、排序，对前n-1个记录进行同样操个记录进行同样操作，其结果使得关键字次大的记录被安置到第作，其结果使得关键字次大的记录被安置到第n-1个记录的位置个记录的位置上。第上。第i趟起泡排序是从趟起泡排序是从l.r1到到l.rn-i+1依次比较相邻两个记依次比较相邻两个记录的关键字，并在逆序时交换到第录的关键字，并在逆序时交换到第n-i+1的位置上。判别起泡排的位置上。判别起泡排序结束条件是：序结束条件是：在一趟排序过程中没有进行过交换记录的操作。在一趟排序过程中没有进行过交换记录的操作。数数数数数数据据据据据据结结结结结结构构构构构构初始关键字：初始关键字： 49 38 65 97 76 13 27

27、 49第一趟排序后：第一趟排序后：38 49 65 76 13 27 49 97第二趟排序后：第二趟排序后：38 49 65 13 27 49 76第三趟排序后：第三趟排序后：38 49 13 27 49 65第四趟排序后：第四趟排序后：38 13 27 49 49第五趟排序后：第五趟排序后：13 27 38 49第六趟排序后：第六趟排序后：13 27 38q 起泡排序示例起泡排序示例数数数数数数据据据据据据结结结结结结构构构构构构void bubblesort(sqlist &l) int i, j, tag; j = l.length-1; do tag=1; for(i=1; i

28、=j; i+) if( l.ri+1.key l.ri.key ) l.r0= l.ri+1; l.ri+1= l.ri; l.ri= l.r0; tag=0; if( !tag ) j-; while( !tag &j ); return; q 起泡排序算法起泡排序算法数数数数数数据据据据据据结结结结结结构构构构构构n 在对象的初始排列已经按关键字从小到大排好序时，此在对象的初始排列已经按关键字从小到大排好序时，此算法只执行一趟起泡，做算法只执行一趟起泡，做 n-1 次关键字比较，不移动对象次关键字比较，不移动对象。这是最好的情形。这是最好的情形。n 最坏的情形是算法执行了最坏的情形

29、是算法执行了n-1趟起泡，第趟起泡，第 i 趟趟 (1 in) 做了做了 n- i 次关键字比较，执行了次关键字比较，执行了n-i 次对象交换。总的时间次对象交换。总的时间复杂度为复杂度为o(n2)。n 起泡排序是一个稳定的排序方法。起泡排序是一个稳定的排序方法。q 起泡排序算法分析起泡排序算法分析数数数数数数据据据据据据结结结结结结构构构构构构v 基本思想：基本思想：通过一趟排序将待排记录分割成独立的两部通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个小

30、，则可分别对这两部分记录继续进行排序，以达到整个序列有序。序列有序。v 一趟快速排序：一趟快速排序：首先选取一个记录（通常选取第一个记首先选取一个记录（通常选取第一个记录）作为界点，然后将所有关键字较它小的记录都安置在录）作为界点，然后将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此以该位置之后。由此以该“界点界点”记录最后所落的位置记录最后所落的位置i为分界为分界线，将整个序列分割成两个子序列。线，将整个序列分割成两个子序列。 然后分别对这两个子序列重复施行上述方法，直到所然后分别对这两个子序列

31、重复施行上述方法，直到所有的对象都排在相应位置上为止。有的对象都排在相应位置上为止。9.3.2 快速排序快速排序数数数数数数据据据据据据结结结结结结构构构构构构v 具体做法：具体做法： 附设两个指针附设两个指针low和和high，其初值分别指向数组的单元，其初值分别指向数组的单元1和单元和单元n。选择第一个记录为界点，其关键字为选择第一个记录为界点，其关键字为pivotkey。将。将pivotkey复制复制到到r0中，从中，从high所指的位置起向前搜索找到第一个关键字小于所指的位置起向前搜索找到第一个关键字小于pivotkey的记录复制到的记录复制到low所指位置中，然后从所指位置中，然后从

32、low所指位置起向所指位置起向后搜索，找到第一个关键字大于后搜索，找到第一个关键字大于pivotkey的记录复制到的记录复制到high所指所指位置中，重复这两步直到位置中，重复这两步直到lowhigh为止。为止。v快速排序是对冒泡排序的一种改进方法，算法中元素的比较快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，关键字较大的元素一次就能够和交换是从两端向中间进行的，关键字较大的元素一次就能够交换到后面单元，关键字较小的记录一次就能够交换到前面单交换到后面单元，关键字较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。元，记录每

33、次移动的距离较远，因而总的比较和移动次数较少。 9.3.2 快速排序快速排序数数数数数数据据据据据据结结结结结结构构构构构构 0 1 2 3 4 5 6 7 84938659776132749*初始关键字初始关键字pivotkeylowhigh 0 1 2 3 4 5 6 7 82738659776132749*第一次交换第一次交换lowhigh49 0 1 2 3 4 5 6 7 82738659776136549*第二次交换第二次交换lowhigh499.3.2 快速排序快速排序数数数数数数据据据据据据结结结结结结构构构构构构 0 1 2 3 4 5 6 7 827381397761365

34、49*第三次交换第三次交换lowhigh49 0 1 2 3 4 5 6 7 82738139776976549*第四次交换第四次交换lowhigh49 0 1 2 3 4 5 6 7 82738134976976549*第一趟完成第一趟完成low high499.3.2 快速排序快速排序数数数数数数据据据据据据结结结结结结构构构构构构q 快速排序全过程快速排序全过程 初始状态初始状态 49 38 65 97 76 13 27 49 49 38 65 97 76 13 27 49 一趟快速排序后一趟快速排序后 27 38 13 49 76 97 65 49 27 38 13 49 76 97

35、65 49 分别进行快速排序分别进行快速排序 13 27 38 13 27 38 结束结束结束结束 49 65 76 97 49 65 76 97 49 65 49 65 结束结束结束结束 有序序列有序序列 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 整个快速排序过程可整个快速排序过程可递归进行递归进行数数数数数数据据据据据据结结结结结结构构构构构构v 一趟快速排序算法实现：一趟快速排序算法实现： int partition(sqlist &l, int low, int high) l.r0 = l.rlow; pivotkey =

36、 l.rlow.key; while (low high) while (low= pivotkey) -high; l.rlow = l.rhigh; while (lowhigh & l.rlow.key = pivotkey) +low; l.rhigh = l.rlow; l.rlow=l.r0; return low; 9.3.2 快速排序快速排序数数数数数数据据据据据据结结结结结结构构构构构构递归形式的快速排序算法：递归形式的快速排序算法：void qsort(sqlist &l, int low, int high) if (low high) pivotloc

37、= partition(l,low,high); qsort(l,low, pivotloc-1); qsort(l,pivotloc+1, high); void quicksort(sqlist &l) qsort(l,1,l.length); 9.3.2 快速排序快速排序数数数数数数据据据据据据结结结结结结构构构构构构算法分析算法分析 从时间上看，快速排序平均计算时间是从时间上看，快速排序平均计算时间是o(nlog2n)。实。实验结果表明验结果表明: 就平均计算时间而言就平均计算时间而言, 快速排序是所有内排序快速排序是所有内排序方法中最好的一个。在最坏的情况方法中最好的一个。在

38、最坏的情况, 即待排序对象序列已经即待排序对象序列已经按其排序码从小到大排好序的情况下，其时间复杂度为按其排序码从小到大排好序的情况下，其时间复杂度为o(n2)。 从空间上看，快速排序是递归的，最大递归调用层次从空间上看，快速排序是递归的，最大递归调用层次数与递归树的高度一致，理想情况为数与递归树的高度一致，理想情况为 log2(n+1) 。因此，。因此，要求存储开销为要求存储开销为 o(log2n)。 快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。9.3.2 快速排序快速排序数数数数数数据据据据据据结结结结结结构构构构构构9.4 选择排序选择排序9.4.1 简单选择排序简单

39、选择排序n基本思想基本思想每一趟从待排的无序区中选出关键字最小的记录，顺每一趟从待排的无序区中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直至记录全部排完。序放在已排好序的子文件的最后，直至记录全部排完。n具体步骤具体步骤首先在无序区首先在无序区r1.n中选出关键字最小的记录，将它中选出关键字最小的记录，将它与与r1交换。然后在无序区交换。然后在无序区r2.n中选出关键字最小的中选出关键字最小的记录，将它与记录，将它与r2交换。重复此过程。当第交换。重复此过程。当第i趟排序时趟排序时r1.i-1已是有序区，从无序区已是有序区，从无序区ri.n中选出关键字最小中选出关键字最小的记录的记

40、录rk，将它与，将它与ri交换，使交换，使r1.i为有序区。可见，为有序区。可见，整个过程需要整个过程需要n-1趟排序。趟排序。 数数数数数数据据据据据据结结结结结结构构构构构构例例9.4.1 简单选择排序简单选择排序初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 3

41、8 49 65 76 97 排序结束： 13 27 38 49 65 76 97数数数数数数据据据据据据结结结结结结构构构构构构n直接选择算法直接选择算法void selectsort(sqlist&l) /* 对r1.n进行直接选择排序 */for(i=1;in;+i)/*做n-1趟排序*/min=i; /*min记录最小元素下标*/for(j=i+1;j=n;j+) /* 在当前无序区ri.n中选关键字最小的记录rmin */if (l.rj.keyl.rmin.key) min=j;if(min!=i) /* 交换ri和rmin */temp=l.ri;l.ri=l.rmin;

42、l.rmin=temp; 9.4.1 简单选择排序简单选择排序数数数数数数据据据据据据结结结结结结构构构构构构q 时间复杂度时间复杂度时间复杂度v 记录移动次数 最好情况：0 最坏情况：3(n-1)v 比较次数：整个排序过程共需n-1趟比较，在第i趟中需比较n-i次，故总比较次数为： v 故直接选择排序的时间复杂度为o（n2）。2) 1()(11maxnnincni9.4.1 简单选择排序简单选择排序数数数数数数据据据据据据结结结结结结构构构构构构9.4.3 堆排序堆排序n 基本思想基本思想堆排序（heapsort）是对选择排序的一种改进方法，属于树形排序法。在排序过程中，将r1.n看成是一棵

43、完全二叉树的顺序存储结构，利用双亲结点和孩子结点间的内在关系来选择关键字最小的记录。 n 堆的概念堆的概念设有n个元素的序列 k1，k2，kn，当且仅当满足下述关系之一时，称之为堆。kik2i和kik2i+1或kik2i和kik2i+1其中，ki必是数列中的最大值或最小值，可分别成为大根堆和小根堆。下图是两种堆的示例。 数数数数数数据据据据据据结结结结结结构构构构构构2412473885913053大根堆大根堆小根堆小根堆n 排序过程 以初始关键字序列，建立堆； 输出堆顶最小元素； 调整余下的元素，使其成为一个新堆； 重复, n 次，得到一个有序序列。9.4.3 堆排序堆排序8591364724165330数数数数数数据据据据据据结结结结结结构构构构构构n 实现堆排序关键要解决和两个问题： 一是如何由一个无序序列建成一个堆? 二是输出堆顶元素后，如何调整余下的元素成为一个新堆?v 输出堆顶元素后，堆的重建：解决这一问题可采用“筛选法”。筛选法的基本思想为：设有n个元素的堆，输出堆顶元素后，剩下n-1个元素。将堆底推向堆顶。然后将结点ri的关键字和其左右孩子的关