第十章内部排序

1、第十章第十章 内部排序内部排序10.1 排序的基本概念排序的基本概念n排序(sorting)q将一个数据元素的任意序列重新排列成一个按关键字有序的序列。q假设n个元素的序列R1,R2,.,Rn，相应的关键字序列为k1, k2,., kn，确定1,2,.,n的一种排列p1,p2,.,pn ，使相应的关键字满足非递减(或非递增)关系kp1,kp2,.,kpn，从而得到一个按关键字有序的序列。这样的一个操作过程就是排序。n稳定的排序方法稳定的排序方法q若若kikj，且在排序前的序列中，且在排序前的序列中Ri领先于领先于Rj，排序，排序后后Ri仍领先于仍领先于Rj，则称所用的排序方法是稳定的；反，则称

2、所用的排序方法是稳定的；反之，若可能使排序后的序列中之，若可能使排序后的序列中Rj仍领先于仍领先于Ri ，则称所，则称所用的排序方法是不稳定的。用的排序方法是不稳定的。n内部排序和外部排序内部排序和外部排序q待排序的记录存放在计算机的内存中所进行的排序待排序的记录存放在计算机的内存中所进行的排序操作称为内部排序。操作称为内部排序。q待排序的记录数量很大，以致内存一次不能容纳全待排序的记录数量很大，以致内存一次不能容纳全部记录，在排序过程中需要访问外存的排序过程称为部记录，在排序过程中需要访问外存的排序过程称为外部排序。外部排序。n排序方法度量排序方法度量q排序过程主要是比较记录的关键字和移动记

3、录。因排序过程主要是比较记录的关键字和移动记录。因此排序的时间复杂性可以算法执行中的数据比较次数此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好。则认为该方法的时间复杂性就越好。q针对一种排序方法，不仅要分析它的时间复杂性，针对一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。而且要分析它的空间复杂性、稳定性和简单性等。10.1 排序的基本概念排序的基

4、本概念(续续)内部排序内部排序外部排序外部排序 插入排序（插入排序（直插排序、二分插入排序直插排序、二分插入排序、希尔排序希尔排序） 交换排序（冒泡排序、快速排序）交换排序（冒泡排序、快速排序） 选择排序（直选排序、树型排序、堆排序）选择排序（直选排序、树型排序、堆排序） 归并排序（二路归并排序、多路归并排序）归并排序（二路归并排序、多路归并排序） 分配排序（多关键字排序、基数排序）分配排序（多关键字排序、基数排序） 多路平衡归并排序多路平衡归并排序 置换选择排序置换选择排序 最佳归并树最佳归并树排序排序将无序子序列中的将无序子序列中的一个或几个记一个或几个记录录“插入插入”到有序序列到有序序

5、列中，从而中，从而增加记录的有序子序列的长度。增加记录的有序子序列的长度。通过通过“交换交换”无序序列中的记录无序序列中的记录从而得到其中关键字从而得到其中关键字最小或最大最小或最大的记录，并将它的记录，并将它加入到有序子序加入到有序子序列列中，以此方法增加记录的有序中，以此方法增加记录的有序子序列的长度。子序列的长度。从记录的无序子序列中从记录的无序子序列中“选择选择”关键字关键字最小或最大最小或最大的记录，并将的记录，并将它它加入到有序子序列加入到有序子序列中，以此方中，以此方法增加记录的有序子序列的长度。法增加记录的有序子序列的长度。通过通过“归并归并”两个或两个以上的两个或两个以上的记

6、录有序子序列记录有序子序列，逐步增加记录，逐步增加记录有序序列的长度。有序序列的长度。10.2 插入排序插入排序1. 直接插入排序基本思想是：n个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。有序序列有序序列R1.i-1Ri无序序列无序序列 Ri.n有序序列有序序列R1.i无序序列无序序列 Ri+1.n10.2 直接插入排序过程示例直接插入排序过程示例初始关键字序列3412492831525149*123456780监视哨监视哨i=21234492831525

7、149*12i=31234492831525149*49i=41228344931525149*28i=51228313449525149*31i=61228313449525149*52i=71228313449515249*51i=8122831344949*515249*10.2 直接插入排序算法直接插入排序算法v数据结构定义#define MAXSIZE 20typedef int Keytype; / 定义关键字类型为整型typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其他数据项RedType; / 记录类型typed

8、ef struct RedType rMAXSIZE+1; / r0闲置或用作哨兵 int length; / 顺序表长度SqList; / 顺序表类型10.2 直接插入排序算法直接插入排序算法v以顺序表作为存储结构的直接插入排序算法void InsertSort(SqList &L) for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if

9、/ InsertSortv分析直接插入排序算法中关键字的比较次数和记录移动次数分析直接插入排序算法中关键字的比较次数和记录移动次数 for(i = 2; i = L.length; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.ri-1; for(j = i - 2; L.r0.key L.rj

10、.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if最好情况下最好情况下( (正序正序) )元素的比较次数为元素的比较次数为: : n - 1 元素的移动次数为元素的移动次数为: :0最坏情况下最坏情况下(逆序逆序)元素的比较次数元素的比较次数: : (n+2)(n-1)/2元素的元素的移动次数为：移动次数为： (n+4)(n-1)/2 10.2 直接插入排序算法直接插入排序算法v以顺序表作为存储结构的直接插入排序算法以顺序表作为存储结构的直接插入排序算法q时间复杂度：时间复杂度：O(nO(n2 2) )n在最好情况下在最好情况下( (正序正序) )，元素的移

11、动次数为，元素的移动次数为0 0，比较次数，比较次数为为n 1n 1；n在最坏情况下在最坏情况下( (逆序逆序) )，元素的移动次数为，元素的移动次数为(n+4)(n-1)/2(n+4)(n-1)/2，比较次数为，比较次数为 (n+2)(n-1)/2(n+2)(n-1)/2q空间复杂度：空间复杂度：O(1)O(1)n只需要只需要 1 1 个辅助单元个辅助单元q稳定的排序方法稳定的排序方法q适用情况适用情况n元素数目少，或者元素的初始序列基本有序元素数目少，或者元素的初始序列基本有序10.2 其他插入排序其他插入排序2. 其他插入排序q在寻找插入位置时采用二分查找，则称为折半插入排序;q2-路插

12、入排序在此基础上增加了辅助空间、减少了记录的移动;q表插入排序就是通过链接指针，按关键码的大小，实现从小到大的链接过程，不移动元素，用静态链表实现。 void InsertSort(SqList &L) /对顺序表对顺序表L作折半插入排序作折半插入排序 for(i=2；i = L.length; i+) L.r0 = L.ri; /保存待插入元素保存待插入元素 low = 1；high = i-1； /设置初始区间设置初始区间 while(low L.rmid.key) low = mid+1； /插入位置在高半区中插入位置在高半区中 else high = mid-1； /插入位置在

13、低半区中插入位置在低半区中 for(j = i - 1; j = high +1; j-) L.rj+1 = L.rj; L.rhigh+1 = L.r0; /* 将元素插入将元素插入 */ 10.2 希尔排序希尔排序3. 希尔排序希尔排序(Shells Sort)(Shells Sort)也称为缩小增量排序，也称为缩小增量排序，其改进原理主要基于以下两点:q元素基本有序时，直接插入排序的时间复杂度接近于O(n)q元素数目n较少时，直接插入排序的效率较高v希尔排序的算法思想希尔排序的算法思想先将整个待排序元素序列分割成若干个子序列（由先将整个待排序元素序列分割成若干个子序列（由相隔某个相隔某个

14、“增量增量”的元素组成的），分别进行直接插的元素组成的），分别进行直接插入入排序，待整个序列中的元素基本有序（增量足够小）排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。时，再对全体元素进行一次直接插入排序。10.2 希尔排序过程示例希尔排序过程示例初始关键字序列：4938659776132749*123456785504910增量增量d5132749*5504493865123456789776910第一趟排序结果：第一趟排序结果：增量增量d3第二趟排序结果：第二趟排序结果：130449*3827495565123456789776910增量增量d1第三趟

15、排序结果：第三趟排序结果：0413273849*495565123456787697910132749*5504493865977610.2 希尔排序算法希尔排序算法void ShellInsert(SqList &L,int dk) /对顺序表对顺序表L作一趟希尔排序作一趟希尔排序 for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if /

16、ShellInsertSort for(i = dk+1; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if if (L.ri.key 0 &L.r0.key L.rj.key; j -= dk) L.rj+dk = L.rj; /寻找插入位置时记录后移寻找插入位置时记录后移 L.rj+dk = L.r0; /插入插入 /if10.2 希尔排序算法希尔排序算

17、法(续续)及分析及分析void ShellInsert(SqList &L,int dk) /对顺序表对顺序表L作一趟希尔排序作一趟希尔排序L . /ShellInsertSortvoid ShellSort(SqList &L,int dlta,int t) /按增量序列按增量序列dlta0.t-1进行希尔排序进行希尔排序 for(k = 0; k t; k+) ShellInsert(L,dltak); /一趟增量为一趟增量为dltak的希尔排序的希尔排序 /ShellInsertSortv希尔排序的分析是一个复杂问题，增量序列的设置是希尔排序的分析是一个复杂问题，增量序列

18、的设置是关键，尚没有正式的依据说明如何设置最佳的增量序列，关键，尚没有正式的依据说明如何设置最佳的增量序列，大量的实验表明希尔排序所需的比较和移动次数可达到大量的实验表明希尔排序所需的比较和移动次数可达到n n1.31.3v希尔排序的空间复杂度为希尔排序的空间复杂度为O(1)O(1)，是，是不稳定的排序方法不稳定的排序方法10.3 交换排序交换排序1. 起泡排序起泡排序q基本思想是：将相邻位置的关键字进行比较，若为逆基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。序则交换之。无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序

19、列有序序列 Rn-i+1.n比较相邻记录，将关键字最大的记比较相邻记录，将关键字最大的记录交换到录交换到 n-i+1 的位置上的位置上第第 i 趟起泡排序趟起泡排序q若在一趟排序过程中没有进行过交换记录的操若在一趟排序过程中没有进行过交换记录的操作，则整个排序过程终止。作，则整个排序过程终止。10.3 起泡排序过程示例起泡排序过程示例初始关键字序列：4938659776132749*1234567838496576132749*97第一趟排序后：第一趟排序后：384965132749*7697第二趟排序后：第二趟排序后：3849132749*657697第三趟排序后：第三趟排序后：381327

20、4949*657697第四趟排序后：第四趟排序后：1327384949*657697第五趟排序后：第五趟排序后：1327384949*657697第六趟排序后：第六趟排序后：10.3 起泡排序算法起泡排序算法v以顺序表作为存储结构的起泡排序算法void BubbleSort(SqList &L) for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0;

21、 /if / BubbleSortv分析起泡排序算法中关键字的比较次数和记录移动次数分析起泡排序算法中关键字的比较次数和记录移动次数 for(i = 1, change = TRUE; i L.length & change; +i) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /for /if change =FALSE; for(j = 1; j L.rj+1.key ) L.r0 = L

22、.rj; L.rj = L.rj+1; L.rj+1 = L.r0; change =TRUE; /if最好情况下，元素的比较次数为最好情况下，元素的比较次数为: n - 1 最坏情况下，比较次数为最坏情况下，比较次数为: n(n-1)/2最好情况下，元素的移动次数为最好情况下，元素的移动次数为:0:0最坏情况下，交换次数为：最坏情况下，交换次数为：n(n-1)/2n(n-1)/210.3 起泡排序算法起泡排序算法v以顺序表作为存储结构的起泡排序算法q时间复杂度：O(n2)n在最好情况下(正序)，元素的交换次数为0，比较次数为n 1；n在最坏情况下(逆序)，元素的交换次数为n(n-1)/2，比

23、较次数为 (n+2)(n-1)/2q空间复杂度：O(1)n只需要 1 个辅助单元进行交换q稳定的排序方法q适用情况n元素数目少，或者元素的初始序列基本有序10.3 交换排序交换排序(续续)2. 快速排序q快速排序(Quick Sorting)是迄今为止所有内排序算法中速度最快的一种。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序q其基本思想是：取待排序序列中的某个元素作为基基准准（一般取第一个元素一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的关键字均小于

24、或等于基准元素的关键字，右子序列的关键字则大于基准元素的关键字，然后分别对两个子序列继续进行排序，直至整个序列有序。38 65 97 13 27 49* 551234567849049pivotij快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分(续续)38 65 97 13 27 49* 55123456784904949ijL.rj与与pivot比较，比较，L.rj小则与小则与L.ri交换；否则交换；否则j减减10449L.rj 与与L.ri交换，交换，i加加1快速排序中的一趟划分快速排序中的一趟划分(续续)38 65 97 13 27 49* 551234

25、56780449949pivotijL.ri与与pivot比较，比较，L.ri大则与大则与L.rj交换；否则交换；否则i增增1快速排序中的一趟划分快速排序中的一趟划分(续续)L.ri与与pivot比较，比较，L.ri大则与大则与L.rj交换；否则交换；否则i增增138 65 97 13 27 49* 55123456780449949pivotij4965L.ri与与L.rj交换，交换，j减减1快速排序中的一趟划分快速排序中的一趟划分(续续)38 49 97 13 27 49* 55123456780465949ijL.rj与与pivot比较，比较，L.rj小则与小则与L.ri交换；否则交换；

26、否则j减减1快速排序中的一趟划分快速排序中的一趟划分(续续)38 49 97 13 27 49* 55123456780465949pivotijL.rj与与pivot比较，比较，L.rj小则与小则与L.ri交换；否则交换；否则j减减1快速排序中的一趟划分快速排序中的一趟划分(续续)L.rj与与pivot比较，比较，L.rj小则与小则与L.ri交换；否则交换；否则j减减138 49 97 13 27 49* 55123456780465949pivotij2749L.rj小则与小则与L.ri交换，交换，i加加1快速排序中的一趟划分快速排序中的一趟划分(续续)pivot38 27 97 13 4

27、9 49* 55123456780465949pivotijL.ri与与pivot比较，比较，L.ri大则与大则与L.rj交换；否则交换；否则i增增1L.ri大则与大则与L.rj交换，交换，j减减14997快速排序中的一趟划分快速排序中的一趟划分(续续)pivotL.rj与与pivot比较，比较，L.rj小则与小则与L.ri交换；否则交换；否则j减减138 27 49 13 97 49* 55123456780465949pivotijL.rj小则与小则与L.ri交换，交换，i加加113 49快速排序中的一趟划分快速排序中的一趟划分(续续)38 27 13 49 97 49* 55123456

28、780465949pivoti j当当i与与j相等时，枢轴元素确定了位置相等时，枢轴元素确定了位置i，结束本次划分，结束本次划分 快速排序是对冒泡排序的一种改进方法，算法中元快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面的单元，排序码较小的的元素一次就能够交换到后面的单元，排序码较小的记录一次就能够交换到前面的单元，记录每次移动的记录一次就能够交换到前面的单元，记录每次移动的距离较远，因而总的比较和移动次数较少。距离较远，因而总的比较和移动次数较少。38 65 97 13 27

29、49* 551234567849049pivot快速排序中的一趟划分算法快速排序中的一趟划分算法38 27 13 49 97 49* 551234567804659一次划分一次划分int Partition(SqList &L,int low,int high) pivotkey = L.rlow.key; while (lowhigh) while (low= pivotkey) high- -; /从后往前寻找比枢轴元素小者从后往前寻找比枢轴元素小者 L.rlow L.rhigh; /比枢轴元素小者交换到前半区间比枢轴元素小者交换到前半区间 while (lowhigh &

30、 L.rlow.key = pivotkey) low+; /从前往后寻找比枢轴元素大者从前往后寻找比枢轴元素大者 L.rhigh L.rlow; /比枢轴元素大者交换到后半比枢轴元素大者交换到后半 区间区间 return low; /返回枢轴元素的位置返回枢轴元素的位置/Partition将交换改为元素的移动将交换改为元素的移动划分算法改进划分算法改进38 65 97 13 27 49* 55123456784904949ij044938 65 97 13 27 49* 55123456784904949ij0438 65 97 13 27 49 551234567849049pivotij

31、快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27 49 551234567804949pivotijaj与与pivot比较，比较，aj小则小则ajai快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27 49 551234567804949pivotij快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27 49 551234567804949pivotijai与与pivot比较，比较，ai大则大则ai aj；否；否则则i增增1快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27

32、49 551234567804949pivotijai与与pivot比较，比较，ai大则大则ai aj；否；否则则i增增1快速排序中的一趟划分快速排序中的一趟划分 3897 13 27 49 55123456780465949pivotij快速排序中的一趟划分快速排序中的一趟划分 3897 13 27 49 55123456780465949pivotijaj与与pivot比较，比较，aj小则小则aj ai; 否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 3897 13 27 49 55123456780465949pivotijaj与与pivot比较，比较，

33、aj小则小则aj ai; 否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 3897 13 27 49 55123456780465949pivotijaj与与pivot比较，比较，aj小则小则aj ai; 否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 38 27 97 1349 55123456780465949pivotijai与与pivot比较，比较，ai大则大则ai aj; 否则，利用否则，利用i向后扫描向后扫描快速排序中的一趟划分快速排序中的一趟划分 38 27 97 1349 55123456780465949pivo

34、tij利用利用i向后扫描向后扫描ai与与pivot比较，比较，ai大则大则ai aj;快速排序中的一趟划分快速排序中的一趟划分 38 2713 97 49 55123456780465949pivotij利用利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 38 2713 97 49 55123456780465949pivotijaj与与pivot比较，比较，aj小则小则aj ai; 否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 38 27 1397 49 55123456780465949pivotijai与与pivot比较，比较，ai大则大

35、则ai aj; 否则，利用否则，利用i向后扫描向后扫描快速排序中的一趟划分快速排序中的一趟划分 38 27 1397 49 55123456780465949pivotij快速排序中的一趟划分快速排序中的一趟划分 38 27 1397 49 55123456780465949pivoti ji与与j相等时，完成一次划分相等时，完成一次划分快速排序中的一趟划分快速排序中的一趟划分 38 27 13 49 97 49 551234567804659int Partition(SqList &L,int low,int high) L.r0 = L.rlow; pivotkey = L.r0

36、.key; while (lowhigh) 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;/Partition快速排序快速排序int Partition(SqList &L,int low,int high) . return i; /返回枢轴元素的位置返回枢轴元素的位置/Partitionvoid QSort(SqList &L, int lo

37、w, int high) /对对L.rlowL.rhigh的元素进行快速排序的元素进行快速排序 if (low high) pivotloc = Partition(L,low,high); /一趟划分一趟划分 QSort(L,low,pivotloc - 1); QSort(L, pivotloc+1,high); /if /QSort快速排序过程分析快速排序过程分析38 65 97 13 27 49* 551234567849049划分划分38 27 13 49 97 49* 550465划分划分38 27 1304划分划分9765 49* 55划分划分13 27 38划分划分2713划分

38、划分55 49* 65划分划分5549*2749*10.3 快速排序分析快速排序分析v以顺序表作为存储结构的快速排序算法q时间复杂度：时间复杂度：O(nlognO(nlogn) )n快速排序在最好情形下(左、右子区间的长度大致相等)，则结点数n与二叉树深度h应满足log2nhlog2n+1，所以总的比较次数不会超过(n+1)log2n。因此，快速排序的最好时间复杂度应为O(nlog2n)。理论上已经证明，快速排序的平均时间复杂度也为O(nlog2n)。n在最坏情况下(逆序或正序)，时间复杂度为 O(n2)q空间复杂度：空间复杂度：O(lognO(logn) )n在最坏情况下(逆序或正序)，空间

39、复杂度为O(n)q不稳定的排序方法不稳定的排序方法v快速排序不适合对小规模的序列进行排序10.3 快速排序分析快速排序分析假设假设一次划分所得枢轴位置一次划分所得枢轴位置 i=k，则对，则对n 个记录进行个记录进行快排所需时间为：快排所需时间为： T(n) = Tpass(n) + T(k-1) + T(n-k)其中其中 Tpass(n)为对为对 n 个记录进行一次划分所需时间。个记录进行一次划分所需时间。若待排序列中记录的关键字随机分布，则若待排序列中记录的关键字随机分布，则k 取取 1 至至 n 中任一值的可能性相同，中任一值的可能性相同，由此可得快速排序所需时由此可得快速排序所需时间的平

40、均值为：间的平均值为：nkavgavgavgknTkTnCnnT1)()1(1)(10)(2)(niavgavgiTnCnnTCCnnTnnnTavg2) 1() 1()(12) 1(1)(nCnnTnnTavg10.3 快速排序方法的改进快速排序方法的改进v枢轴元素的选取q三者取中q随机选择v划分的过程中进行“起泡”操作v当划分出的子序列长度小于某个值时，不再递归，而进行直接插入排序v快速排序算法被认为是内部排序方法中最好的一种13 27 38 49 49* 55 650497123456789最坏情况下的快速排序最坏情况下的快速排序13 27 38 49 49* 55 65049713 2

41、7 38 49 49* 55 65 9727 38 49 49* 55 65 9738 49 49* 55 65 9749 49* 55 65 9749* 55 65 9755 65 9765 9797最好情况下的快速排序最好情况下的快速排序04 65 97 13 55 49* 381234567849279划分划分04 38 13 49 55 49* 972765划分划分13 043827划分划分6549* 55 97划分划分3804 13划分划分49*976565划分划分0410.4 选择排序选择排序1. 简单选择排序q简单选择排序的基本思想是：第一趟在n个记录中选取最小记录作为有序序列的

42、第一个记录，第二趟在n-1个记录中选取最小记录作为有序序列的第二个记录，第i趟在n-i+1个记录中选取最小的记录作为有序序列多中的第i个记录。简单选择排序过程示例简单选择排序过程示例初始关键字序列3412492831525149*123456780i=11234492831525149*i=21228493431525149*i=31228313449525149*i=41228313449525149*i=51228313449525149*i=6122831344949*5152i=7122831344949*515210.4 简单选择排序算法简单选择排序算法v以顺序表作为存储结构的简单选

43、择排序算法void SelectSort(SqList &L) /对顺序表作简单选择排序对顺序表作简单选择排序 for(i = 1; i L.ength; i+) for(k = i, j =i; k = L.length; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; /for / SelectSortv分析简单选择排序算法中关键字的比较次数和记录移动次数分析简单选择排序算法中关键字的比较次数和记录移动次数 for(i = 1; i L.length; i+) for(k = i, j =i; k = L.lengt

44、h; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; /for /if for(k = i+1, j = i; k = L.length; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; 在逆序情况下在逆序情况下元素的比较次数元素的比较次数: : n(n-1)/2元素的元素的移动次数为：移动次数为：3(n-1)在正序情况下在正序情况下元素的比较次数元素的比较次数: : n(n-1)/2元素的元素的移动次数为：移动次数为：010.4 简单选择排序算法分析简单选择排序

45、算法分析v以顺序表作为存储结构的简单选择排序算法q时间复杂度：O(n2)n在n个关键字中选出最小者，需要n-1次比较，继续在剩余的n-1个元素中选出次小者需要n-2次比较，依此类推。q空间复杂度：O(1)n只需要 1 个辅助单元进行交换q不稳定的排序方法q适用情况n元素数目少的情况n无需完全排序的情况，比如，选出第i小的元素v对简单选择排序过程进行改进：利用前面已经进行过的对简单选择排序过程进行改进：利用前面已经进行过的比较结果比较结果10.4 选择排序选择排序2. 树形选择排序(Tree Selection Sort)q又称锦标赛排序(Tournament Sort):首先对n个记录的关键字

46、两两进行比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录。整个过程可用一个含有n个叶结点的二叉树表示。q例如3412492831525149*12283149*123112341212 492831525149*10.4 选择排序选择排序q选出最小记录后，将树中的该最小记录修改为，然后从该叶子结点所在子树开始，修改到达树根的路径上的结点34 492831525149*34 283149*28312834 492831525149*10.4 选择排序选择排序q以后每选出一个小元素，都只需进行(logn)次比较34 4931525149*34 493149*3431

47、3134 492831525149*10.4 选择排序选择排序2. 树形选择排序的缺陷q需要较多的辅助空间q存在与“”进行比较的冗余比较34 4931525149*34 493149*34313110.4 选择排序选择排序3. 3. 堆排序堆排序(Heap Sort)(Heap Sort)q只需要一个元素的辅助空间q算法的时间复杂度为O(nlogn)v堆的定义堆的定义对于对于n个元素的序列个元素的序列k1,k2,.,kn，当且仅当满足当且仅当满足以下关系时，称之为堆。以下关系时，称之为堆。 1i2ii2ikkkk 1i2ii2ikkkk2n,.,2,1i或或10.4 堆排序堆排序v堆(完全二叉

48、树)96833811279(a) 大顶堆大顶堆(max heap)123685472430(b) 小顶堆小顶堆(min heap)5391 1i2ii2ikkkk 1i2ii2ikkkk10.4 堆排序堆排序3. 堆排序(Heap Sort)q对一组待排序记录的关键字，首先把它们按堆的定义建成小(大)顶堆，然后输出堆顶的最小(大)关键字所代表的记录，再对剩余的关键字建堆，以便得到次小(大)的关键字，如此反复进行，直到全部关键字排成有序序列为止。v 实现堆排序需要解决两个问题：实现堆排序需要解决两个问题： (1) (1) 如何建堆？如何建堆？ (2) (2) 输出堆顶元素后，如何将剩余元素重新调

49、整为输出堆顶元素后，如何将剩余元素重新调整为一个新堆？一个新堆？10.4 堆排序过程示例堆排序过程示例v下面是一个小顶堆，输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较小者与之交换，即将非堆的子树推向叶子方向12368547243053919136854724305312交换堆顶元素与序列末交换堆顶元素与序列末端的元素端的元素比较比较比较比较-交换交换10.4 堆排序过程示例堆排序过程示例(续续)v输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较小者与之交换，即将非堆的

50、子树推向叶子方向2436854730915312继续向叶子方向调整继续向叶子方向调整2436854791305312比较比较比较比较交换交换10.4 堆排序过程示例堆排序过程示例(续续)v一旦已调整为堆，则输出堆顶元素，重复将剩余元素重新调整为一个新堆。24368547309153125336854730912412交换堆顶元素与序列末交换堆顶元素与序列末端的元素端的元素10.4 堆排序过程示例堆排序过程示例(续续)v输出堆顶元素后，将剩余元素重新调整为一个新堆3036854753912412调整成堆调整成堆533685473091241210.4 堆排序过程分析堆排序过程分析v输出堆顶元素后

51、，将剩余元素重新调整为一个新堆9136854753302412反复将堆顶元素与序列反复将堆顶元素与序列末端的元素的交换，并末端的元素的交换，并重新调整成堆。重新调整成堆。9185473653302412q调整堆元素调整堆元素( (筛选筛选) ) 对于给出的关键字序列，经初始建堆后便得到小对于给出的关键字序列，经初始建堆后便得到小( (大大) )顶顶堆，从而得到最小堆，从而得到最小( (大大) )关键字。关键字。 在输出堆顶元素之后，用堆中最后一个元素替代在输出堆顶元素之后，用堆中最后一个元素替代之。此时由于以之。此时由于以K K2 2和和K K3 3为根的子树仍具有堆的特性，为根的子树仍具有堆

52、的特性，因此只需自上而下进行调整即可。因此只需自上而下进行调整即可。 调整过程为：调整过程为：首先令首先令K K1 1的两个子树根进行比较，令其中较的两个子树根进行比较，令其中较小小( (大大) )者与者与K K1 1相比较，将最小相比较，将最小( (大大) )元素交换至元素交换至K K1 1，使得，使得K K1 1、K K2 2和和K K3 3成为堆。由于交换后破坏了子树的堆性质，则需再次进行成为堆。由于交换后破坏了子树的堆性质，则需再次进行与上述过程类似的调整，直至进行到最下层的叶结点为止。与上述过程类似的调整，直至进行到最下层的叶结点为止。调整后即得到一个有调整后即得到一个有n-1n-1

53、个元素的新堆，从而得到次小关键字。个元素的新堆，从而得到次小关键字。10.4 堆排序过程分析堆排序过程分析(续续)v输出堆顶元素后，将剩余元素重新调整为一个新堆q调整堆元素调整堆元素( (筛选筛选) ) 对于给出的关键字序列，经初始建堆后便得到小对于给出的关键字序列，经初始建堆后便得到小( (大大) )顶堆，从而得顶堆，从而得到最小到最小( (大大) )关键字。关键字。 在输出堆顶元素之后，用堆中最后一个元素替代之。此时由于以在输出堆顶元素之后，用堆中最后一个元素替代之。此时由于以K K2 2和和K K3 3为根的子树仍具有堆的特性，因此只需自上而下进行调整即可。为根的子树仍具有堆的特性，因此

54、只需自上而下进行调整即可。 首先令首先令K K1 1将的两个子树根进行比较，令其中较小将的两个子树根进行比较，令其中较小( (大大) )者与者与K K1 1相比较，相比较，将最小将最小( (大大) )元素交换至元素交换至K K1 1，使得，使得K K1 1、K K2 2和和K K3 3成为堆。由于交换后破坏了右成为堆。由于交换后破坏了右子树的堆，则需再次进行与上述类似的调整，直至进行到最下层的叶结点。子树的堆，则需再次进行与上述类似的调整，直至进行到最下层的叶结点。调整后即得到一个有调整后即得到一个有n-1n-1个元素的新堆，从而得到次小关键字。个元素的新堆，从而得到次小关键字。重复上述过程，

55、将堆顶元素与堆中最后一个元素交换且调整，重复上述过程，将堆顶元素与堆中最后一个元素交换且调整，又得到了有又得到了有n-2n-2个元素的新堆。为节省存贮开销，可以把输出个元素的新堆。为节省存贮开销，可以把输出的最小的最小( (大大) )关键字放在关键字放在K Kn n的位置上，把第二次输出的次小的位置上，把第二次输出的次小( (大大) )关键字存放在关键字存放在K Kn-1n-1的位置上的位置上，直至最大，直至最大( (小小) )关键字放在关键字放在K K1 1的位置上。的位置上。如此，我们已经可以在初始情况为堆的情况下完成排序，那么，如此，我们已经可以在初始情况为堆的情况下完成排序，那么，如何

56、建立起初始堆呢？如何建立起初始堆呢？建初始小顶堆47369112533024851236854724305391v元素序列为：47,36,53,91,12,30,24,85建立小顶堆建立小顶堆建初始堆4736911253302485(a)4736851253302491(b)v从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，1等是否为堆，若否则调整为堆建初始堆4736851224305391v从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，1等是否为堆，若否则调整为堆(C)4712853624305391(d)

57、建初始堆1247853624305391v从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，1等是否为堆，若否则调整为堆(e)1236854724305391(f)v当以下标当以下标1 1为根的完全二叉树为堆时，初始堆已建立为根的完全二叉树为堆时，初始堆已建立v也可以从空堆开始建初始堆也可以从空堆开始建初始堆10.4 堆排序堆排序v1964年弗洛伊德（Floyd）提出了筛选法建立初始堆，具体方法是：v将待排序的关键字分放到一棵完全二叉树的各个结点中（此时完全二叉树并不一定具备堆的特性），显然，所有in/2的结点Ki都没有子结点，以这样的Ki为根的子树已经

58、是堆，因此初始建堆可从完全二叉树的第i个结点Ki开始(i=n/2)。通过调整，逐步使以Kn/2，Kn/2-1，Kn/2-2，为根的子树满足堆的定义，直至进行到以K1为根的树排成堆为止。v在对Ki为根的子树建堆时，其子树已经为堆，要使得以Ki为根的完全二叉树为堆，则可能要调整父、子结点的位置，如此下一层已建成堆的子树可能不再满足堆的定义，则需继续进行调整，如此一次次递推下去，最多可能一直延伸到树叶。这种方法就像过筛子一样，把最小(大)的关键字一层一层地筛选出来，最后输出堆顶的最小(大)关键字。10.4 堆排序算法堆排序算法(筛选算法筛选算法)vtypedef SqList HeapType; /

59、堆采用顺序存储结构void HeapAdjust (HeapType &H, int s, int m) / HeapAdjust rc = H.rs; for ( j=2*s; j=m; j*=2) /沿沿key较小的孩子结点向下筛选较小的孩子结点向下筛选 if ( j H.rj+l.key) + j; /j为为key较小的记录的下标较小的记录的下标 if (rc. Key 0; -i) / 把把H建成大顶堆建成大顶堆 HeapAdjust ( H, i, H. length); for ( i = H. length; i 1; -i) H.r1 H.ri; /堆顶记录和当前未排子

60、序列中最后一个记录相交换堆顶记录和当前未排子序列中最后一个记录相交换 HeapAdjust (H, 1, i - 1); /将将H. rl . i - 1 重新调整为大顶堆重新调整为大顶堆 / HeapSort for ( i = H. length/2; i 0; -i) / 把把H建成大建成大/小顶堆小顶堆 HeapAdjust ( H, i, H. length); for ( i = H. length; i 1; -i) H.r1H.ri; /堆顶记录和当前未排子序列中最后一个记录相交换堆顶记录和当前未排子序列中最后一个记录相交换 HeapAdjust (H, 1, i - 1); /将将H. rl . i - 1 重新调整为大重新调整为大/小顶堆小顶堆 473691125330248510.4