第十章---内部排序课件

第十章第十章 内部排序内部排序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，则称所用的排序方法是稳定的；反，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中之，若可能使排序后的序列中Rj仍领先于仍领先于Ri，则称所，则称所用的排序方法是不稳定的。用的排序方法是不稳定的。n内部排序和外部排序内部排序和外部排序q待排序的记录存放在计算机的内存中所进行的排序待排序的记录存放在计算机的内存中所进行的排序操作称为内部排序。操作称为内部排序。q待排序的记录数量很大，以致内存一次不能容纳全待排序的记录数量很大，以致内存一次不能容纳全部记录，在排序过程中需要访问外存的排序过程称为部记录，在排序过程中需要访问外存的排序过程称为外部排序。外部排序。n排序方法度量排序方法度量q排序过程主要是比较记录的关键字和移动记录。因排序过程主要是比较记录的关键字和移动记录。因此排序的时间复杂性可以算法执行中的数据比较次数此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好。则认为该方法的时间复杂性就越好。q针对一种排序方法，不仅要分析它的时间复杂性，针对一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。而且要分析它的空间复杂性、稳定性和简单性等。10.1 排序的基本概念排序的基本概念(续续)内部排序内部排序外部排序外部排序 插入排序（插入排序（直插排序、二分插入排序直插排序、二分插入排序、希尔排序希尔排序）交换排序（冒泡排序、快速排序）交换排序（冒泡排序、快速排序）选择排序（直选排序、树型排序、堆排序）选择排序（直选排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）分配排序（多关键字排序、基数排序）多路平衡归并排序多路平衡归并排序 置换选择排序置换选择排序 最佳归并树最佳归并树排序排序将无序子序列中的将无序子序列中的一个或几个记一个或几个记录录“插入插入”到有序序列到有序序列中，从而中，从而增加记录的有序子序列的长度。增加记录的有序子序列的长度。通过通过“交换交换”无序序列中的记录无序序列中的记录从而得到其中关键字从而得到其中关键字最小或最大最小或最大的记录，并将它的记录，并将它加入到有序子序加入到有序子序列列中，以此方法增加记录的有序中，以此方法增加记录的有序子序列的长度。子序列的长度。从记录的无序子序列中从记录的无序子序列中“选择选择”关键字关键字最小或最大最小或最大的记录，并将的记录，并将它它加入到有序子序列加入到有序子序列中，以此方中，以此方法增加记录的有序子序列的长度。法增加记录的有序子序列的长度。通过通过“归并归并”两个或两个以上的两个或两个以上的记录有序子序列记录有序子序列，逐步增加记录，逐步增加记录有序序列的长度。有序序列的长度。10.2 插入排序插入排序1.直接插入排序基本思想是：n个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。有序序列有序序列R1.i-1Ri无序序列无序序列 Ri.n有序序列有序序列R1.i无序序列无序序列 Ri+1.n10.2 直接插入排序过程示例直接插入排序过程示例初始关键字序列3412492831525149*123456780监视哨监视哨i=21234492831525149*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;/记录类型typedef 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/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.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在最好情况下在最好情况下(正序正序)，元素的移动次数为，元素的移动次数为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-路插入排序在此基础上增加了辅助空间、减少了记录的移动;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；/插入位置在低半区中插入位置在低半区中 for(j=i-1;j=high+1;j-)L.rj+1=L.rj;L.rhigh+1=L.r0;/*将元素插入将元素插入*/10.2 希尔排序希尔排序3.希尔排序希尔排序(Shell(Shells Sort)s Sort)也称为缩小增量排序，也称为缩小增量排序，其改进原理主要基于以下两点:q元素基本有序时，直接插入排序的时间复杂度接近于O(n)q元素数目n较少时，直接插入排序的效率较高v希尔排序的算法思想希尔排序的算法思想先将整个待排序元素序列分割成若干个子序列（由先将整个待排序元素序列分割成若干个子序列（由相隔某个相隔某个“增量增量”的元素组成的），分别进行直接插的元素组成的），分别进行直接插入入排序，待整个序列中的元素基本有序（增量足够小）排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。时，再对全体元素进行一次直接插入排序。10.2 希尔排序过程示例希尔排序过程示例初始关键字序列：4938659776132749*123456785504910增量增量d5132749*5504493865123456789776910第一趟排序结果：第一趟排序结果：增量增量d3第二趟排序结果：第二趟排序结果：130449*3827495565123456789776910增量增量d1第三趟排序结果：第三趟排序结果：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/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 希尔排序算法希尔排序算法(续续)及及分析分析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希尔排序的分析是一个复杂问题，增量序列的设置是希尔排序的分析是一个复杂问题，增量序列的设置是关键，尚没有正式的依据说明如何设置最佳的增量序列，关键，尚没有正式的依据说明如何设置最佳的增量序列，大量的实验表明希尔排序所需的比较和移动次数可达到大量的实验表明希尔排序所需的比较和移动次数可达到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有序序列有序序列 Rn-i+1.n比较相邻记录，将关键字最大的记比较相邻记录，将关键字最大的记录录交换到交换到 n-i+1 的位置上的位置上第第 i 趟起泡排序趟起泡排序q若在一趟排序过程中没有进行过交换记录的操若在一趟排序过程中没有进行过交换记录的操作，则整个排序过程终止。作，则整个排序过程终止。10.3 起泡排序过程示例起泡排序过程示例初始关键字序列：4938659776132749*1234567838496576132749*97第一趟排序后：第一趟排序后：384965132749*7697第二趟排序后：第二趟排序后：3849132749*657697第三趟排序后：第三趟排序后：3813274949*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;/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.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，比较次数为(n+2)(n-1)/2q空间复杂度：O(1)n只需要 1 个辅助单元进行交换q稳定的排序方法q适用情况n元素数目少，或者元素的初始序列基本有序10.3 交换排序交换排序(续续)2.快速排序q快速排序(Quick Sorting)是迄今为止所有内排序算法中速度最快的一种。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序q其基本思想是：取待排序序列中的某个元素作为基基准准（一般取第一个元素一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的关键字均小于或等于基准元素的关键字，右子序列的关键字则大于基准元素的关键字，然后分别对两个子序列继续进行排序，直至整个序列有序。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*55123456780449949pivotijL.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交换；否则交换；否则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 49 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*55123456780465949pivoti j当当i与与j相等时，枢轴元素确定了位置相等时，枢轴元素确定了位置i，结束本次划分结束本次划分 快速排序是对冒泡排序的一种改进方法，算法中元快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面的单元，排序码较小的的元素一次就能够交换到后面的单元，排序码较小的记录一次就能够交换到前面的单元，记录每次移动的记录一次就能够交换到前面的单元，记录每次移动的距离较远，因而总的比较和移动次数较少。距离较远，因而总的比较和移动次数较少。38 65 97 13 27 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&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快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分 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 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比较，比较，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 55123456780465949pivotij利用利用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大则大则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.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 low,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划分划分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在最坏情况下(逆序或正序)，空间复杂度为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 中任一值的可能性相同，中任一值的可能性相同，由此可得快速排序所需时间由此可得快速排序所需时间的平均值为：的平均值为：10.3 快速排序方法的改进快速排序方法的改进v枢轴元素的选取q三者取中q随机选择v划分的过程中进行“起泡”操作v当划分出的子序列长度小于某个值时，不再递归，而进行直接插入排序v快速排序算法被认为是内部排序方法中最好的一种选择排序选择排序13 27 38 49 49*55 650497123456789最坏情况下的快速排序最坏情况下的快速排序13 27 38 49 49*55 65049713 27 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 9797return最好情况下的快速排序最好情况下的快速排序04 65 97 13 55 49*381234567849279划分划分04 38 13 49 55 49*972765划分划分13 043827划分划分6549*55 97划分划分3804 13划分划分49*976565return划分划分0410.4 选择排序选择排序1.简单选择排序q简单选择排序的基本思想是：第一趟在n个记录中选取最小记录作为有序序列的第一个记录，第二趟在n-1个记录中选取最小记录作为有序序列的第二个记录，第i趟在n-i+1个记录中选取最小的记录作为有序序列多中的第i个记录。简单选择排序过程示例简单选择排序过程示例初始关键字序列3412492831525149*123456780i=11234492831525149*i=21228493431525149*i=31228313449525149*i=41228313449525149*i=51228313449525149*i=6122831344949*5152i=7122831344949*5152return10.4 简单选择排序算法简单选择排序算法v以顺序表作为存储结构的简单选择排序算法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.length;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 简单选择排序算法分析简单选择排序算法分析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个记录的关键字两两进行比较，然后在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*34313134 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，当且仅当满当且仅当满足以下关系时，称之为堆。足以下关系时，称之为堆。或或10.4 堆排序堆排序v堆(完全二叉树)96833811279(a)大顶堆大顶堆(max heap)123685472430(b)小顶堆小顶堆(min heap)539110.4 堆排序堆排序3.堆排序(Heap Sort)q对一组待排序记录的关键字，首先把它们按堆的定义建成小(大)顶堆，然后输出堆顶的最小(大)关键字所代表的记录，再对剩余的关键字建堆，以便得到次小(大)的关键字，如此反复进行，直到全部关键字排成有序序列为止。v 实现堆排序需要解决两个问题：实现堆排序需要解决两个问题：(1)(1)如何建堆？如何建堆？(2)(2)输输出出堆堆顶顶元元素素后后，如如何何将将剩剩余余元元素素重重新新调调整整为为一一个新堆？个新堆？10.4 堆排序过程示例堆排序过程示例v下面是一个小顶堆，输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较小者与之交换，即将非堆的子树推向叶子方向12368547243053919136854724305312交换堆顶元素与序列末交换堆顶元素与序列末端的元素端的元素比较比较比较比较-交换交换return10.4 堆排序过程示例堆排序过程示例(续续)v输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较小者与之交换，即将非堆的子树推向叶子方向2436854730915312继续向叶子方向调整继续向叶子方向调整2436854791305312比较比较比较比较交换交换10.4 堆排序过程示例堆排序过程示例(续续)v一旦已调整为堆，则输出堆顶元素，重复将剩余元素重新调整为一个新堆。24368547309153125336854730912412交换堆顶元素与序列末交换堆顶元素与序列末端的元素端的元素10.4 堆排序过程示例堆排序过程示例(续续)v输出堆顶元素后，将剩余元素重新调整为一个新堆3036854753912412调整成堆调整成堆533685473091241210.4 堆排序过程分析堆排序过程分析v输出堆顶元素后，将剩余元素重新调整为一个新堆9136854753302412反复将堆顶元素与序列反复将堆顶元素与序列末端的元素的交换，并末端的元素的交换，并重新调整成堆。重新调整成堆。9185473653302412q调整堆元素调整堆元素(筛选筛选)对对于于给给出出的的关关键键字字序序列列，经经初初始始建建堆堆后后便便得得到到小小(大大)顶顶堆堆，从而得到最小从而得到最小(大大)关键字。关键字。在在输输出出堆堆顶顶元元素素之之后后，用用堆堆中中最最后后一一个个元元素素替替代代之之。此此时时由由于于以以K K2 2和和K K3 3为为根根的的子子树树仍仍具具有有堆堆的的特特性性，因此只需自上而下进行调整即可。因此只需自上而下进行调整即可。调调整整过过程程为为：首首先先令令K K1 1的的两两个个子子树树根根进进行行比比较较，令令其其中中较较小小(大大)者者与与K K1 1相相比比较较，将将最最小小(大大)元元素素交交换换至至K K1 1，使使得得K K1 1、K K2 2和和K K3 3成成为为堆堆。由由于于交交换换后后破破坏坏了了子子树树的的堆堆性性质质，则则需需再再次次进进行行与与上上述述过过程程类类似似的的调调整整，直直至至进进行行到到最最下下层层的的叶叶结结点点为为止止。调调整后即得到一个有整后即得到一个有n-1n-1个元素的新堆，从而得到次小关键字。个元素的新堆，从而得到次小关键字。10.4 堆排序过程分析堆排序过程分析(续续)v输出堆顶元素后，将剩余元素重新调整为一个新堆q调整堆元素调整堆元素(筛选筛选)对对于于给给出出的的关关键键字字序序列列，经经初初始始建建堆堆后后便便得得到到小小(大大)顶顶堆堆，从从而而得得到到最小最小(大大)关键字。关键字。在在输输出出堆堆顶顶元元素素之之后后，用用堆堆中中最最后后一一个个元元素素替替代代之之。此此时时由由于于以以K K2 2和和K K3 3为根的子树仍具有堆的特性，因此只需自上而下进行调整即可。为根的子树仍具有堆的特性，因此只需自上而下进行调整即可。首首先先令令K K1 1将将的的两两个个子子树树根根进进行行比比较较，令令其其中中较较小小(大大)者者与与K K1 1相相比比较较，将将最最小小(大大)元元素素交交换换至至K K1 1，使使得得K K1 1、K K2 2和和K K3 3成成为为堆堆。由由于于交交换换后后破破坏坏了了右右子子树树的的堆堆，则则需需再再次次进进行行与与上上述述类类似似的的调调整整，直直至至进进行行到到最最下下层层的的叶叶结结点点。调整后即得到一个有调整后即得到一个有n-1n-1个元素的新堆，从而得到次小关键字。个元素的新堆，从而得到次小关键字。重重复复上上述述过过程程，将将堆堆顶顶元元素素与与堆堆中中最最后后一一个个元元素素交交换换且且调调整整，又又得得到到了了有有n-2n-2个个元元素素的的新新堆堆。为为节节省省存存贮贮开开销销，可可以以把把输输出出的的最最小小(大大)关关键键字字放放在在K Kn n的的位位置置上上，把把第第二二次次输输出出的的次次小小(大大)关关键键字字存存放放在在K Kn-1n-1的的位位置置上上，直直至至最最大大(小小)关关键键字字放放在在K K1 1的位置上。的位置上。如此，我们已经可以在初始情况为堆的情况下完成排序，那么，如此，我们已经可以在初始情况为堆的情况下完成排序，那么，如何建立起初始堆呢？如何建立起初始堆呢？建初始小顶堆47369112533024851236854724305391v元素序列为：47,36,53,91,12,30,24,85建立小顶堆建立小顶堆建初始堆4736911253302485(a)4736851253302491(b)v从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，1等是否为堆，若否则调整为堆return建初始堆4736851224305391v从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，1等是否为堆，若否则调整为堆(C)4712853624305391(d)建初始堆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为根的子树已经是堆，因此初始建堆可从完全二叉树的第i个结点Ki开始(i=n/2)。通过调整，逐步使以Kn/2，Kn/2-1，Kn/2-2，为根的子树满足堆的定义，直至进行到以K1为根的树排成堆为止。v在对Ki为根的子树建堆时，其子树已经为堆，要使得以Ki为根的完全二叉树为堆，则可能要调整父、子结点的位置，如此下一层已建成堆的子树可能不再满足堆的定义，则需继续进行调整，如此一次次递推下去，最多可能一直延伸到树叶。这种方法就像过筛子一样，把最小(大)的关键字一层一层地筛选出来，最后输出堆顶的最小(大)关键字。10.4 堆排序算法堆排序算法(筛选算法筛选算法)vtypedef SqList HeapType;/堆采用顺序存储结构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;/堆顶记录和当前未排子序列中最后一个记录相交换堆顶记录和当前未排子序列中最后一个记录相交换 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 堆排序算法分析堆排序算法分析v由于是完全二叉树，所以采用顺序存储结构q时间复杂度：O(nlog2n)n堆排序的整个算法时间是由建立初始堆和不断调整堆这两部分时间代价构成的，建立初始堆时关键字的比较次数不超过4n，不断调整堆的时间不超过O(nlog2n)。q空间复杂度：O(1)n只需要 1 个辅助单元进行交换q不稳定的排序方法q对于记录数较少的序列来说，堆排序的优越性并不明显，但对数量大的序列来说堆排序是很有效的。归并排序归并排序筛选过程示例筛选过程示例v下面是一个大顶堆，输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较大者与之交换，即将非堆的子树推向叶子方向9153364785302412交换堆顶元素与交换堆顶元素与序列末端的元素序列末端的元素比较比较比较比较-交换交换return(a)大顶堆大顶堆1253364785302491(b)8553364712302491(c)8553364730122491(d)大顶堆大顶堆比较比较比较比较交换交换筛选过程示例筛选过程示例v下面是一个大顶堆，输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较大者与之交换，即将非堆的子树推向叶子方向9153364785302412交换堆顶元素与交换堆顶元素与序列末端的元素序列末端的元素比较比较比较比较-交换交换return(a)小顶堆小顶堆1253364785302491(b)8553364712302412(c)小顶堆小顶堆交换堆顶元素与交换堆顶元素与序列末端的元素序列末端的元素5336854791302412(d)10.5 归并排序归并排序v归并q所谓“归并”，是将两个或两个以上的有序序列合并成为一个新的有序序列。从第二章线性表的讨论中得知，将两个有序表归并为一个有序表，无论是顺序存储结构还是链式存储结构，都是容易实现的。利用归并的思想可以进行排序。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n2-路归并路归并n归并排序归并排序q可将由可将由n个记录的一个无序序列看成是由个记录的一个无序序列看成是由n个长度为个长度为1的有序子序列组成的序列，然后进行两两归并，的有序子序列组成的序列，然后进行两两归并，得到得到n/2个长度为个长度为2或或1的有序子序列，再两两归的有序子序列，再两两归并，并，如此重复，直到最后形成包含，如此重复，直到最后形成包含n个记录个记录的一个有序序列为止。这种总是反复将两个有序序的一个有序序列为止。这种总是反复将两个有序序列归并成一个有序序列的排序方法称为两路归并排列归并成一个有序序列的排序方法称为两路归并排序。序。10.5 两路归并过程示例两路归并过程示例v设初始关键字序列为:48 34 60 80 75 12 26 48*48 34 6O 80 75 12 26 48*48 34 6O 80 75 12 26 48*第一趟归并：第一趟归并：34,48,60,8034,48,60,80第三趟归并：第三趟归并：12,26,34,48,48*48*,60,75,8060,8060,8012,7512,7526,48*26,48*12,26,48*,7512,26,48*,7534,4834,48第二趟归并：第二趟归并：v合并两个序列时，将合并得到的序列与原序列分开存放合并两个序列时，将合并得到的序列与原序列分开存放v也可以用分治思路处理也可以用分治思路处理10.5 先分解再归并先分解再归并v设初始关键字序列为:48 34 60 80 75 12 26 48*48 34 6O 80 75 12 26 48*48 34 6O 80 75 12 26 48*75 12 26 48*75 12 26 48*48 34 60 8048 34 60 8048 3448 3460 8060 8075 1275 1226 48*26 48*48483434 6060808075751212 262648*48*34 4834 4860 8060 8012 7512 7526 48*26 48*12 26 48*7512 26 48*7534 48 60 8034 48 60 8012 26 34 48 4848*60 75 80分分解解归归并并10.5 两路归并排序算法两路归并排序算法v递归算法void MergeSort(待排序列待排序列)/归并排序归并排序 if(待排序列长度待排序列长度 1)MergeSort(待排序列的前半区间待排序列的前半区间)；MergeSort(待排序列的后半区间待排序列的后半区间)；已排好序的前半区间、后半区间合并成一个有序序列；已排好序的前半区间、后半区间合并成一个有序序列；/if/MergeSortv采用顺序存储结构，对于由下标采用顺序存储结构，对于由下标st界定的一个序列，前界定的一个序列，前半区间为半区间为s (s+t)/2，后半区间为后半区间为(s+t)/2+1 tvoid MergeSort(SqList&L,int s,int t)/归并排序归并排序 if(s t)m=(s+t)/2;MergeSort(L,s,m)；MergeSort(L,m+1,t)；Merge(L,s,m,t);/合并合并L.rsL.rm与与L.rm+1L.rt /if/MergeSort10.5 两路归并算法两路归并算法v以顺序表作为存储结构void Merge(RcdType SR,RcdType&TR,int i,int m,int n)/Merge for(j=m+1,k=i;i=m&j=n;+k)/for/ifi if(SRi.key SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)TRkn=SRim;if(j=n)TRkn=SRjn;10.5 归并排序算法分析归并排序算法分析v以顺序表作为存储结构的归并排序算法q时间复杂度：O(nlogn)n对于具有n个元素的一个序列，元素的移动次数可以使用下面的递归公式计算：M(1)=0M(1)=0M(n)=2M(n/2)+2nM(n)=2M(n/2)+2nq空间复杂度：O(n)n这是归并排序的严重缺点q稳定的排序方法v用迭代取代递归进行归并排序效率更高用迭代取代递归进行归并排序效率更高10.6 基数排序基数排序v基数排序(Radix Sorting)q基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法，不需要进行记录关键字间的比较。q例如：整理扑克牌、图书馆卡片的排序q多关键字排序：n个元素的序列R1,R2,.,Rn，每个元素Ri有d个关键字(K0i,K1i,.,Kd-1i)，则序列对关键字(K0i,K1i,.,Kd-1i)有