《数据结构与算法》第十章内部排序分析.ppt

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

1、第十章第十章 内部排序内部排序10.110.1 概述概述10.210.2 插入排序插入排序10.310.3 快速排序快速排序10.410.4 选择排序选择排序10.510.5 归并排序归并排序10.610.6 基数排序基数排序10.710.7 各种排序方法比较各种排序方法比较10101 1概述概述一、排序的定义一、排序的定义一、排序的定义一、排序的定义 假设有假设有假设有假设有n n个记录的序列为：个记录的序列为：个记录的序列为：个记录的序列为：RR1 1，R R2 2，,R,Rn n 其对应的其对应的其对应的其对应的关键字关键字关键字关键字为为为为KK1 1，KK2 2，,K,Kn n 需要

2、确定需要确定需要确定需要确定1 1，2 2，,n,n的一种排列的一种排列的一种排列的一种排列P P1 1，P P2 2，,P,Pn n 使：使：使：使：KKp1p1 KK p2 p2KK p n p n 则则则则RR p1 p1，R R p2 p2，,R,R pn pn 为一个按关键字有序的序列。为一个按关键字有序的序列。为一个按关键字有序的序列。为一个按关键字有序的序列。其中，其中，其中，其中，KKi i可以是记录可以是记录可以是记录可以是记录R Ri i的主关键字、次关键字或若干数的主关键字、次关键字或若干数的主关键字、次关键字或若干数的主关键字、次关键字或若干数据项的组合。据项的组合。据

3、项的组合。据项的组合。二、排序方法的稳定性二、排序方法的稳定性二、排序方法的稳定性二、排序方法的稳定性 若若若若K K K Ki i i i=K=K=K=Kj j j j,(1,(1,(1,(1 i i i i j j j j n),n),n),n),且排序前，且排序前，且排序前，且排序前，R R R Ri i i i在在在在R R R Rj j j j前面，前面，前面，前面，若排序后，若排序后，若排序后，若排序后，R R R Ri i i i仍在仍在仍在仍在R R R Rj j j j前面前面前面前面 则称该排序算法是稳定的，否则是不稳定的。则称该排序算法是稳定的，否则是不稳定的。则称该排序

4、算法是稳定的，否则是不稳定的。则称该排序算法是稳定的，否则是不稳定的。三、排序分类三、排序分类三、排序分类三、排序分类根据待排序的记录的数量划分根据待排序的记录的数量划分根据待排序的记录的数量划分根据待排序的记录的数量划分：内部排序：内部排序：内部排序：内部排序：待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程外部排序：外部排序：外部排序：外部排序：待待待待排排排排序序序序的的的的记记记记录录录录数数数数量量量量很很很很大大大大，内内内内存存存存一一一一次次次次放放放放不不不

5、不下下下下全全全全部部部部记记记记录录录录，在排序过程中还需访问外存的排序过程。在排序过程中还需访问外存的排序过程。在排序过程中还需访问外存的排序过程。在排序过程中还需访问外存的排序过程。四、内部排序方法四、内部排序方法四、内部排序方法四、内部排序方法 插入排序插入排序插入排序插入排序 交换排序交换排序交换排序交换排序 选择排序选择排序选择排序选择排序 归并排序归并排序归并排序归并排序 基数排序基数排序基数排序基数排序五、待排序记录的存储方式五、待排序记录的存储方式五、待排序记录的存储方式五、待排序记录的存储方式 存放在地址连续的一组存储单元存放在地址连续的一组存储单元存放在地址连续的一组存储

6、单元存放在地址连续的一组存储单元-约定约定约定约定 存放在静态链表存放在静态链表存放在静态链表存放在静态链表 存放在地址连续的一组存储单元，另设一组索引指针存放在地址连续的一组存储单元，另设一组索引指针存放在地址连续的一组存储单元，另设一组索引指针存放在地址连续的一组存储单元，另设一组索引指针#define MAXSIZE 20#define MAXSIZE 20 /一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度typedef int KeyType;typedef int KeyType;/定义关键字类型为整数

7、类型定义关键字类型为整数类型定义关键字类型为整数类型定义关键字类型为整数类型typedef structtypedef struct KeyType KeyType key key;/关键字关键字关键字关键字 InfoType InfoType otherinfootherinfo;/其它数据项其它数据项其它数据项其它数据项 RedTypeRedType;/记录类型记录类型记录类型记录类型typedef structtypedef struct RedType RedType rMAXSIZE;rMAXSIZE;/r0/r0赋闲或用作哨兵单元赋闲或用作哨兵单元赋闲或用作哨兵单元赋闲或用作哨兵单

8、元 int int lengthlength;/顺序表长度顺序表长度顺序表长度顺序表长度 SqListSqList;10102 2插入排序插入排序insert sortinginsert sorting一、直接插入排序一、直接插入排序一、直接插入排序一、直接插入排序 方法：方法：方法：方法：将一个记录插入已排好序的有序表中，得到一个将一个记录插入已排好序的有序表中，得到一个将一个记录插入已排好序的有序表中，得到一个将一个记录插入已排好序的有序表中，得到一个新的记录数增加新的记录数增加新的记录数增加新的记录数增加1 1 1 1的有序表的有序表的有序表的有序表（1 1 1 1）把序列把序列把序列把

9、序列(R(K(R(K(R(K(R(K1 1 1 1)看成是一个有序的子序列看成是一个有序的子序列看成是一个有序的子序列看成是一个有序的子序列 把把把把R(KR(KR(KR(K2 2 2 2)插入到该序列中插入到该序列中插入到该序列中插入到该序列中,使插入后序列使插入后序列使插入后序列使插入后序列 (R(K(R(K(R(K(R(K1 1 1 1),R(K),R(K),R(K),R(K2 2 2 2)有序有序有序有序（2 2 2 2）把把把把R(KR(KR(KR(K3 3 3 3)插入到插入到插入到插入到(R(K(R(K(R(K(R(K1 1 1 1),R(K),R(K),R(K),R(K2 2

10、2 2)中中中中，使插入后有序使插入后有序使插入后有序使插入后有序（3 3 3 3）重复（）重复（）重复（）重复（2 2 2 2），直到插入），直到插入），直到插入），直到插入R(KR(KR(KR(Kn n n n)为止。为止。为止。为止。7目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法插入排序动画 123432296445347845，34，78，12，34，32，29，64 45 45 34 45 34 45 34 45 78 34 45 78 12 34 45 78 12 34 45 78 12 34 12 34 3434 45 78 45 78 12 32 34 12 32 3

11、4 3434 45 78 45 78 12 29 32 34 12 29 32 34 3434 45 78 45 78 12 29 32 34 34 45 64 78 12 29 32 34 34 45 64 78void InsertSort(SqList&L)void InsertSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L做直接插入排序做直接插入排序做直接插入排序做直接插入排序 for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)if(LT(L.ri.key,L.ri-1.key)if(LT(L.ri.key,L.ri-1.ke

12、y)/将将将将L.riL.ri插入有序子表插入有序子表插入有序子表插入有序子表 L.r0=L.ri;L.r0=L.ri;for(j=i-1;LT(L.r0.key,L.rj.key);-j)for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.rj;/记录后移记录后移记录后移记录后移 L.rj+1=L.r0;L.rj+1=L.r0;/插入到正确位置插入到正确位置插入到正确位置插入到正确位置 /InsertSort/InsertSort算法分析算法分析稳定空间代价：O(n)时间代价：最佳情况：n-1次比较，O(n)最差情况：O(n2)比较

13、次数为平均情况：O(n2)例例：在在序序列列1313，2727，3535，4848，6565，7272中中插插入入2020或或60603565132748722060二、折半插入排序二、折半插入排序Binary Insertsort 用折半查找的方法找到插入位置用折半查找的方法找到插入位置void BInsertSort(SqList&L)void BInsertSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L做折半插入排序做折半插入排序做折半插入排序做折半插入排序 for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)L.r0=L.ri;

14、L.r0=L.ri;/将将将将L.riL.ri暂存到暂存到暂存到暂存到L.r0L.r0 low=1;hight=i-1;low=1;hight=i-1;while(while(low=hightlow=hight+1;-j)L.rj+1=L.rj;for(j=i-1;j=hight+1;-j)L.rj+1=L.rj;/记录后移记录后移记录后移记录后移 L.rhight+1=L.r0;L.rhight+1=L.r0;/插入到正确位置插入到正确位置插入到正确位置插入到正确位置 /BInsertSort/BInsertSort四、希尔排序（缩小增量排序四、希尔排序（缩小增量排序ShellSort）思

15、想：先将序列转化为若干小序列，在这些小序列内进行插入排序逐渐增加小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态最后对整个序列进行一趟直接插入排序直接插入排序的两个特点：在最好情况下时间代价为O(n)对于短序列，直接插入排序比较有效 按增量序列将整个待排记录分割成若干个按增量序列将整个待排记录分割成若干个序列，分别进行直接插入排序。等整个序列序列，分别进行直接插入排序。等整个序列基本有序后，再对全体记录进行一次直接插基本有序后，再对全体记录进行一次直接插入排序。入排序。基本有序基本有序：序列中满足以下特性的记录较少：序列中满足以下特性的记录较少方法：方法：17目录页张铭、邹艳

16、珍、刘楚雄、闫宏飞、郝丹数据结构与算法Shell排序动画 12343229644534781234322964453478123432296445347812343229644534781234322964453478增量序列为：增量序列为：5 5，3 3，1 149 38 65 97 76 13 27 4913 27 49 97 76 49 38 6513 27 49 97 76 49 38 6513 27 49 38 65 49 97 7613 27 38 49 49 65 76 97void ShellInsert(SqList&L,int dk)void ShellInsert(SqL

17、ist&L,int dk)/对顺序表对顺序表对顺序表对顺序表L L作一趟希尔插入排序作一趟希尔插入排序作一趟希尔插入排序作一趟希尔插入排序./本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较,作了以下修改作了以下修改作了以下修改作了以下修改 /1./1.前后记录位置的增量是前后记录位置的增量是前后记录位置的增量是前后记录位置的增量是dk,dk,而不是而不是而不是而不是1 1 /2.r0 /2.r0只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当j=0j=0时，插入位置已找到时

18、，插入位置已找到时，插入位置已找到时，插入位置已找到 for(i=dk+1;i=L.length;+i)for(i=dk+1;i0<(L.r0.kry,L.rj.key);j-=;j0<(L.r0.kry,L.rj.key);j-=dkdk)L.rj+L.rj+dkdk=L.rj;=L.rj;/记录后移，查找插入位置记录后移，查找插入位置记录后移，查找插入位置记录后移，查找插入位置 L.rj+L.rj+dkdk=L.r0;=L.r0;/插入插入插入插入 /ShellInsert/ShellInsertvoid ShellSort(SqList&L,int dlta,int t)/按增量

19、序列按增量序列dlta0.t-1对顺序表对顺序表L作希尔排序作希尔排序 for(k=0;kt;+t)ShellInsert(L,dltak);/一趟增量为一趟增量为daltk的插入排序的插入排序/ShellSort不稳定空间代价：O(n)时间代价增量序列不合适时，O(n2)选择适当的增量序列,可以使得时间代价接近O(n)Hibbard增量序列2k-1，2k-1-1，7，3，1Hibbard增量序列的Shell排序的效率可以达到O(n3/2)呈2p3q形式的一系列整数：1,2,3,4,6,8,9,12时间代价为O(nlog2n)算法分析算法分析10103 3快速排序快速排序一、起泡排序一、起泡排

20、序Bubble SortBubble Sort算法思想:依次比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束，避免不必要的比较void BubbleSort(SqList&L)for(i=1;iL.length;i+)change=FALSE;for(j=1;jL.rj+1.key)change=TRUE;L.rjL.rj+1;if(!change)return;共进行共进行n-1n-1趟排序，趟排序，共进行共进行n(n-1)/2n(n-1)/2次比较次比较T(n)=O(nT(n)=O

21、(n2 2)算法分析算法分析稳定空间代价：O(n)时间代价：比较次数最少：O(n)最多：交换次数最多为O(n2)，最少为0，平均为O(n2)最坏，平均时间代价均为O(n2)最好时间代价为O(n)二、快速排序二、快速排序二、快速排序二、快速排序Quick SortQuick Sort基本思想：基本思想：通过一趟排序将待排序记录分成独立的两部分，通过一趟排序将待排序记录分成独立的两部分，其中一部分记录的关键字均小于另一部分记录其中一部分记录的关键字均小于另一部分记录 的关键字，然后分别对这两部分进行递归排序的关键字，然后分别对这两部分进行递归排序 一趟排序：一趟排序：一趟排序：一趟排序：任意选取一

22、个记录作为枢轴（支点）任意选取一个记录作为枢轴（支点）任意选取一个记录作为枢轴（支点）任意选取一个记录作为枢轴（支点）pivot,pivot,将所有关键将所有关键将所有关键将所有关键字小于它的记录排在它的前面字小于它的记录排在它的前面字小于它的记录排在它的前面字小于它的记录排在它的前面,将所有关键字大于它的将所有关键字大于它的将所有关键字大于它的将所有关键字大于它的记录排在它的后面。即以枢轴记录为分界线，使原序列记录排在它的后面。即以枢轴记录为分界线，使原序列记录排在它的后面。即以枢轴记录为分界线，使原序列记录排在它的后面。即以枢轴记录为分界线，使原序列L.rs,L.rs+1,L.rtL.rs

23、,L.rs+1,L.rt分成两个子序列：分成两个子序列：分成两个子序列：分成两个子序列：L.rs,L.rs+1,L.ri-1L.rs,L.rs+1,L.ri-1和和和和 L.ri+1,L.ri+2,L.rtL.ri+1,L.ri+2,L.rt 枢轴记录在位置枢轴记录在位置枢轴记录在位置枢轴记录在位置i i49 38 65 97 76 13 27 49i27 38 65 97 76 13 49 4927 38 49 97 76 13 65 49jiiijjijj27 38 13 97 76 49 65 49iji27 38 13 49 76 97 65 49ij27 38 1376 97 65

24、49jj具体实现：具体实现：具体实现：具体实现：low=s;high=t;pivotkey=L.rlow.key;low=s;high=t;pivotkey=L.rlow.key;(1)(1)从从从从highhigh开开开开始始始始往往往往前前前前找找找找第第第第一一一一个个个个关关关关键键键键字字字字小小小小于于于于pivotkeypivotkey的的的的记记记记录，与枢轴记录交换录，与枢轴记录交换录，与枢轴记录交换录，与枢轴记录交换 (2)(2)从从从从lowlow开开开开始始始始往往往往后后后后找找找找第第第第一一一一个个个个关关关关键键键键字字字字大大大大于于于于pivotkeypiv

25、otkey的的的的记记记记录录录录，与枢轴记录交换与枢轴记录交换与枢轴记录交换与枢轴记录交换 (3)(3)重复（重复（重复（重复（1 1）（）（）（）（2 2）直到）直到）直到）直到low=highlow=high为止为止为止为止此时枢轴记录所在的位置此时枢轴记录所在的位置此时枢轴记录所在的位置此时枢轴记录所在的位置i=low=highi=low=high27 38 13 49 76 97 65 4913 27 3849 65 76 97 int partition(SqList&L,int low,int high)int partition(SqList&L,int low,int hig

26、h)/交换顺序表交换顺序表交换顺序表交换顺序表L L中的子表中的子表中的子表中的子表L.rlow.highL.rlow.high的记录的记录的记录的记录,枢轴记录到位枢轴记录到位枢轴记录到位枢轴记录到位,并返回其所在位置并返回其所在位置并返回其所在位置并返回其所在位置 /此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它 piovtkey=L.rlow.key;piovtkey=L.rlow.key;/用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录

27、用子表的第一个记录作枢轴记录 while(lowhigh)while(lowhigh)/从表的两端交替地向中间扫描从表的两端交替地向中间扫描从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(low=priotkey)while(low=priotkey)-high-high;L.rlow L.rlow L.rhigh;L.rhigh;/将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端 while(lowhigh&L.rlow.key=priotkey)while(lowhigh&L.rlow.key=pri

28、otkey)+low;+low;L.rlow L.rlow L.rhighL.rhigh;/将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端 return low;/返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置/Partition/Partitionint partition(SqList&L,int low,int high)int partition(SqList&L,int low,int high)/交换顺序表交换顺序表交换顺序表交换顺序表L L中的子表中的子表中的子表中的子表L.rlo

29、w.highL.rlow.high的记录，枢轴记录到位，的记录，枢轴记录到位，的记录，枢轴记录到位，的记录，枢轴记录到位，/并返回其所在位置。此时在它之前（后）的记录均不大（小）于它并返回其所在位置。此时在它之前（后）的记录均不大（小）于它并返回其所在位置。此时在它之前（后）的记录均不大（小）于它并返回其所在位置。此时在它之前（后）的记录均不大（小）于它 L.r0=L.rlow;L.r0=L.rlow;/用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 pivotkey=L.rlow.key;pivotkey=L.rlow.key

30、;/枢轴记录关键字枢轴记录关键字枢轴记录关键字枢轴记录关键字 while(lowhigh)while(lowhigh)/从表的两端交替地向中间扫描从表的两端交替地向中间扫描从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(low=pivotkey)while(low=pivotkey)-high;-high;L.rlow=L.rhigh;L.rlow=L.rhigh;/将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端 while(lowhigh&L.rlow.key=pivotkey)+low;while(

31、lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rhigh=L.rlow;/将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端 L.rlow=L.r0;L.rlow=L.r0;/枢轴记录到位枢轴记录到位枢轴记录到位枢轴记录到位 return low;return low;/返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置/Partition/Partitionvoid Qsort(SqList&L,int low,int high)void Qsor

32、t(SqList&L,int low,int high)/对顺序表对顺序表对顺序表对顺序表L L中的子表中的子表中的子表中的子表L.rlow.highL.rlow.high作快速排序作快速排序作快速排序作快速排序 if(lowhigh)if(lowhigh)/长度大于长度大于长度大于长度大于1 1 pivotloc=partition(L,low,high);pivotloc=partition(L,low,high);/将将将将L.rlow.highL.rlow.high一分为二一分为二一分为二一分为二 Qsort(L,low,pivotloc-1);Qsort(L,low,pivotloc

33、-1);/对低子表递归排序，对低子表递归排序，对低子表递归排序，对低子表递归排序，pivotlocpivotloc是枢轴位置是枢轴位置是枢轴位置是枢轴位置 Qsort(L,pivotloc+1,high);Qsort(L,pivotloc+1,high);/对高子表递归排序对高子表递归排序对高子表递归排序对高子表递归排序 /Qsortvoid QuickSort(SqList&L)void QuickSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L作快速排序作快速排序作快速排序作快速排序 QSort(L,1,L.length);QSort(L,1,L.length);/Qu

34、ickSort/QuickSort枢轴记录的选择枢轴记录的选择尽可能使两部分长度相等选择策略：选择最左/右/中间位置记录随机选择选择平均值算法分析算法分析最差情况：时间代价：O(n2)空间代价：O(n)最佳情况：时间代价：O(nlogn)空间代价：O(logn)平均情况：时间代价：O(nlogn)空间代价：O(logn)T(n)=O(nlog2n)34目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法123432296445347810104 4选择排序选择排序 一、简单选择排序一、简单选择排序一、简单选择排序一、简单选择排序Select SortSelect Sortvoid Selec

35、tSort(SqList&L)void SelectSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L作简单选择排序作简单选择排序作简单选择排序作简单选择排序 for(i=1;iL.length;+i)for(i=1;iL.length;+i)/选择第选择第选择第选择第i i个最小的记录，并交换到位个最小的记录，并交换到位个最小的记录，并交换到位个最小的记录，并交换到位 j=SelectMinkey(L,i);j=SelectMinkey(L,i);/在在在在L.ri.L.lengthL.ri.L.length中选择中选择中选择中选择keykey最小的记录最小的记录最小的记录

36、最小的记录 if(i!=j)L.rj if(i!=j)L.rj L.ri;L.ri;/与第与第与第与第i i记录交换记录交换记录交换记录交换 int SelectMinKey(SqList L,int k)int SelectMinKey(SqList L,int k)/在在在在L.rk.L.lengthL.rk.L.length中选择中选择中选择中选择keykey最小的记录并返回它的位置最小的记录并返回它的位置最小的记录并返回它的位置最小的记录并返回它的位置 min=L.rk.key;minp=k;min=L.rk.key;minp=k;for(i=k+1;i=L.length;i+)for

37、(i=k+1;i=L.length;i+)if(L.ri.keymin)if(L.ri.keymin)min=L.ri.key;minp=i;min=L.ri.key;minp=i;return minp;return minp;不稳定空间代价：O(n)时间代价共进行n-1趟排序 比较次数：O(n2)交换次数：n-1总时间代价：O(n2)算法分析算法分析 若若用用一一个个一一维维数数组组存存放放满满足足此此关关系系的的序序列列，把把这这个个一一维维数数组组看看成成是是一一棵棵完完全全二二叉叉树树，则则堆堆对对应应的的完完全全二二叉叉树树中中所所有有非非终终端端结结点点的的值值均大于或均小于其左

38、右孩子的值。均大于或均小于其左右孩子的值。三、堆排序三、堆排序Heap Sort堆的定义堆的定义：n个元素的序列个元素的序列K1，K2，Kn当且仅当满足如下关系时称为当且仅当满足如下关系时称为堆堆：Ki K2i 或或 Ki K2i Ki K2i+1 Ki K2i+1大大顶顶堆堆/大大根根堆堆堆排序方法：堆排序方法：（1 1）由一个无序的序列建成一个堆）由一个无序的序列建成一个堆（2 2）输出堆顶的最小值）输出堆顶的最小值（3 3）剩余的元素建成一个新的堆）剩余的元素建成一个新的堆（4 4）重复（）重复（2 2）（）（3 3）093811962783小小顶顶堆堆/小小根根堆堆3085471224

39、36915349 38 65 97 76 13 27 49输出输出1313后后,用用序列中最后一序列中最后一个记录代替根个记录代替根结点结点筛筛选选为为堆顶元素与它的左右子树根结点比较堆顶元素与它的左右子树根结点比较若右子树根若右子树根 左子树根左子树根 堆顶堆顶 根结点与右子树根交换根结点与右子树根交换若左子树根若左子树根 右子树根右子树根 堆顶堆顶 根结点与左子树根交换根结点与左子树根交换这个调整过程称为这个调整过程称为筛选筛选13384976972765499738497627654927384976496597对对一一个个无无序序序序列列建建立立堆堆也也是是筛筛选选过过程程,筛筛选选从

40、从n/2个记录开始。个记录开始。49 38 65 97 76 13 27 49762749653897491349653897499765764927381349976576492738134938657649279713497665493827971349766549382797134927654938769713496527493876971349652749387697134913274938769765134927493876976513492749387697654913274938769765494927381376976549492738137697654913273849769

41、7654938271349769765494938382727131349497676979765654949272738381313494976769797656549491313383827274949767697976565建建大顶堆大顶堆，排序，排序结果为结果为从小到大从小到大typedef SqList HeapType;typedef SqList HeapType;void HeapAdjust(HeapType&H,int s,int m)void HeapAdjust(HeapType&H,int s,int m)/已知已知已知已知H.rs.mH.rs.m中记录的关键字除中记

42、录的关键字除中记录的关键字除中记录的关键字除H.rs.keyH.rs.key外均满足堆的定义，外均满足堆的定义，外均满足堆的定义，外均满足堆的定义，/本函数调整本函数调整本函数调整本函数调整H.rsH.rs的关键字，使的关键字，使的关键字，使的关键字，使H.rs.mH.rs.m成为一个大顶堆成为一个大顶堆成为一个大顶堆成为一个大顶堆 rc=H.rs;rc=H.rs;for(j=2*s;j=m;j*=2)for(j=2*s;j=m;j*=2)/沿沿沿沿keykey较大的孩子结点向下筛选较大的孩子结点向下筛选较大的孩子结点向下筛选较大的孩子结点向下筛选 if(jm<(H.rj.key,H.rj

43、+1.key)if(j0;-i)for(i=H.length/2;i0;-i)/把把把把H.ri.lengthH.ri.length建成大顶堆建成大顶堆建成大顶堆建成大顶堆 HeapAdjust(H,i,H.length);HeapAdjust(H,i,H.length);for(i=H.length;i1;-i)for(i=H.length;i1;-i)H.r1 H.r1 H.ri;H.ri;/将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列/H.r1.i/H.r1.i中最后一个记录相交换中最后一个记录相交换中最后一个记

44、录相交换中最后一个记录相交换 HeapAdjust(H,1,i-1);HeapAdjust(H,1,i-1);/将将将将H.r1.i-1H.r1.i-1重新调整为大顶堆重新调整为大顶堆重新调整为大顶堆重新调整为大顶堆 /HeapSort算法分析算法分析建堆：O(n)删除堆顶:O(logn)一次建堆，n次删除堆顶总时间代价为O(nlogn)空间代价为O(n)T(n)=O(nlog2n)10105 5归并排序归并排序 Merge Sort 将两个以上的有序序列合并成一个新的有序序列将两个以上的有序序列合并成一个新的有序序列2 2路归并：路归并：把初始含有把初始含有n n个记录的序列看成个记录的序列

45、看成n n个长度为个长度为1 1的有序子序列的有序子序列,采用两采用两两合并的方法最终合并成一个序列两合并的方法最终合并成一个序列void Merge(RedType SR,RedType&TR,void Merge(RedType SR,RedType&TR,int i,int m,int n)int i,int m,int n)/将有序的将有序的将有序的将有序的SRi.mSRi.m和和和和SRm+1.nSRm+1.n归并为有序的归并为有序的归并为有序的归并为有序的TRi.nTRi.n for(j=m+1,k=i;i=m&j=n;+k)for(j=m+1,k=i;i=m&j=n;+k)/将将

46、将将SRSR中记录由小到大地并入中记录由小到大地并入中记录由小到大地并入中记录由小到大地并入TRTR if LQ(SRi.key,SRj.key)TRk=SRi+;if LQ(SRi.key,SRj.key)TRk=SRi+;else TRk=SRj+;else TRk=SRj+;if(i=m)TRk.n=SRi.m;if(i=m)TRk.n=SRi.m;/将剩余的将剩余的将剩余的将剩余的SRi.mSRi.m复制到复制到复制到复制到TRTR if(j=n)TRk.n=SRj.n;if(j=n)TRk.n=SRj.n;/将剩余的将剩余的将剩余的将剩余的SRj.nSRj.n复制到复制到复制到复制到

47、TRTR/Merge/Mergevoid MSort(RedType SR,RedType&TR1,int s,int t)void MSort(RedType SR,RedType&TR1,int s,int t)/将将将将SRs.tSRs.t归并排序为归并排序为归并排序为归并排序为TR1s.tTR1s.t if(s=t)TR1s=SRs;if(s=t)TR1s=SRs;else else m=(s+t)/2;m=(s+t)/2;/将将将将SRs.tSRs.t平分为平分为平分为平分为SRs.mSRs.m和和和和SRm+1.tSRm+1.t Msort(SR,TR2,s,m);Msort(SR

48、,TR2,s,m);/递归地将递归地将递归地将递归地将SRs.mSRs.m归并为有序的归并为有序的归并为有序的归并为有序的TR2s.mTR2s.m Msort(SR,TR2,m+1,t);Msort(SR,TR2,m+1,t);/递归地将递归地将递归地将递归地将SRm+1.tSRm+1.t归并为有序的归并为有序的归并为有序的归并为有序的TR2m+1.tTR2m+1.t Merge(TR2,TR1,s,m,t);Merge(TR2,TR1,s,m,t);/将将将将TR2s.mTR2s.m和和和和TR2m+1.tTR2m+1.t归并到归并到归并到归并到TR1s.tTR1s.t /Msort/Mso

49、rtvoid MergeSort(SqList&L)void MergeSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L作归并排序作归并排序作归并排序作归并排序.Msort(L.r,L.r,1,L.length);Msort(L.r,L.r,1,L.length);/MergeSort/MergeSort算法分析稳定空间代价：O(n)时间代价：T(n)=2T(n/2)+cnT(1)=1归并排序总时间代价为O(nlogn)任何情况下都是10106 6基数排序基数排序Radix SortRadix Sort 不通过关键字之间的比较进行排序不通过关键字之间的比较进行排序 一、多关

50、键字排序一、多关键字排序最高位优先法最高位优先法最高位优先法最高位优先法MSDMSDMSDMSD：先按关键字先按关键字先按关键字先按关键字K K K K0 0 0 0排序，排序，排序，排序，将序列分成若干个子序列将序列分成若干个子序列将序列分成若干个子序列将序列分成若干个子序列 每个子序列记录的每个子序列记录的每个子序列记录的每个子序列记录的K K K K0 0 0 0均相等均相等均相等均相等 然后在每个子序列中按然后在每个子序列中按然后在每个子序列中按然后在每个子序列中按K K K K1 1 1 1排序排序排序排序 按按按按K K K K1 1 1 1值把子序列分成更小的子序列值把子序列分成