数据结构与算法内部排序分析.pptx

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

1、10101 1概述概述一、排序的定义一、排序的定义一、排序的定义一、排序的定义 假设有假设有假设有假设有n n个记录的序列为：个记录的序列为：个记录的序列为：个记录的序列为：RR1 1，R R2 2，,R,Rn n 其对应的其对应的其对应的其对应的关键字关键字关键字关键字为为为为KK1 1，K K2 2，,K,Kn n 需要确定需要确定需要确定需要确定1 1，2 2，,n,n的一种排列的一种排列的一种排列的一种排列P P1 1，P P2 2，,P,Pn n 使：使：使：使：K Kp1p1 K K p2 p2K K p n p n 则则则则RR p1 p1，R R p2 p2，,R,R pn p

2、n 为一个按关键字有序的序列。为一个按关键字有序的序列。为一个按关键字有序的序列。为一个按关键字有序的序列。其中，其中，其中，其中，K Ki i可以是记录可以是记录可以是记录可以是记录R Ri i的主关键字、次关键字或若干数的主关键字、次关键字或若干数的主关键字、次关键字或若干数的主关键字、次关键字或若干数据项的组合。据项的组合。据项的组合。据项的组合。第1页/共70页二、排序方法的稳定性二、排序方法的稳定性二、排序方法的稳定性二、排序方法的稳定性 若若若若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)

3、,且排序前，且排序前，且排序前，且排序前，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、序：内部排序：待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程外部排序：外部排序：外部排序：外部排序：待待待待排排排排序序序序的的的的记记记记录录录录数数数数量量量量很很很很大大大大，内内内内存存存存一一一一次次次次放放放放不不不不下下下下全全全全部部部部记记记记录录录录，在排序过程中还需访问外存的排序过程。在排序过程中还需访问外存的排序过程。在排序过程中还需访问外存的排序过程。在排序过程中还需访问外存的排序过程。第2页/共70页四、内部排序方法四、内部排序方法四、内部排序方

5、法四、内部排序方法 插入排序插入排序插入排序插入排序 交换排序交换排序交换排序交换排序 选择排序选择排序选择排序选择排序 归并排序归并排序归并排序归并排序 基数排序基数排序基数排序基数排序五、待排序记录的存储方式五、待排序记录的存储方式五、待排序记录的存储方式五、待排序记录的存储方式 存放在地址连续的一组存储单元存放在地址连续的一组存储单元存放在地址连续的一组存储单元存放在地址连续的一组存储单元-约定约定约定约定 存放在静态链表存放在静态链表存放在静态链表存放在静态链表 存放在地址连续的一组存储单元，另设一组索引指针存放在地址连续的一组存储单元，另设一组索引指针存放在地址连续的一组存储单元，另

6、设一组索引指针存放在地址连续的一组存储单元，另设一组索引指针第3页/共70页#define MAXSIZE 20#define MAXSIZE 20 /一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度typedef int KeyType;typedef int KeyType;/定义关键字类型为整数类型定义关键字类型为整数类型定义关键字类型为整数类型定义关键字类型为整数类型typedef structtypedef struct KeyType KeyType key key;/关键字关键字关键字关键字 Info

7、Type InfoType otherinfootherinfo;/其它数据项其它数据项其它数据项其它数据项 RedTypeRedType;/记录类型记录类型记录类型记录类型typedef structtypedef struct RedType RedType rMAXSIZE;rMAXSIZE;/r0/r0赋闲或用作哨兵单元赋闲或用作哨兵单元赋闲或用作哨兵单元赋闲或用作哨兵单元 int int lengthlength;/顺序表长度顺序表长度顺序表长度顺序表长度 SqListSqList;第4页/共70页10102 2插入排序插入排序insert sortinginsert sorting

8、一、直接插入排序一、直接插入排序一、直接插入排序一、直接插入排序 方法：方法：方法：方法：将一个记录插入已排好序的有序表中，得到一个将一个记录插入已排好序的有序表中，得到一个将一个记录插入已排好序的有序表中，得到一个将一个记录插入已排好序的有序表中，得到一个新的记录数增加新的记录数增加新的记录数增加新的记录数增加1 1 1 1的有序表的有序表的有序表的有序表（1 1 1 1）把序列把序列把序列把序列(R(K(R(K(R(K(R(K1 1 1 1)看成是一个有序的子序列看成是一个有序的子序列看成是一个有序的子序列看成是一个有序的子序列 把把把把R(KR(KR(KR(K2 2 2 2)插入到该序列

9、中插入到该序列中插入到该序列中插入到该序列中,使插入后序列使插入后序列使插入后序列使插入后序列 (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 2 2)中中中中，使插入后有序使插入后有序使插入后有序使插入后有序（3 3 3 3）重复（）重复（）重复（）重复（2 2 2 2），直到插入），直到插入），直到插入），直到插入R(KR(KR(KR(Kn

10、 n n n)为止。为止。为止。为止。第5页/共70页6目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法插入排序动画 1234322964453478第6页/共70页45，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 34 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 1

11、2 29 32 34 34 45 64 78第7页/共70页void 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.key)/将将将将L.riL.ri插入有序子表插入有序子表插入有序子表插入有序子表 L.r0=L.ri;L.r0=L.ri;for(j=i-1;LT(L.r0

12、.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第8页/共70页算法分析稳定空间代价：O(n)时间代价：最佳情况：n-1次比较，O(n)最差情况：O(n2)比较次数为平均情况：O(n2)第9页/共70页例：在序列例：在序列例：在序列例：在序列13131313，27272727，35353535，48484

13、848，65656565，72727272中插入中插入中插入中插入20202020或或或或606060603565132748722060二、折半插入排序二、折半插入排序二、折半插入排序二、折半插入排序Binary InsertsortBinary Insertsort 用折半查找的方法找到插入位置用折半查找的方法找到插入位置用折半查找的方法找到插入位置用折半查找的方法找到插入位置第10页/共70页void BInsertSort(SqList&L)void BInsertSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L做折半插入排序做折半插入排序做折半插入排序做折半插入排

14、序 for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)L.r0=L.ri;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;/插插插插入入入入到到到到正正正正确确确确位位位位置置置置 /BIns

15、ertSort/BInsertSort第11页/共70页四、希尔排序（缩小增量排序四、希尔排序（缩小增量排序ShellSort）思想：先将序列转化为若干小序列，在这些小序列内进行插入排序逐渐增加小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态最后对整个序列进行一趟直接插入排序直接插入排序的两个特点：在最好情况下时间代价为O(n)对于短序列，直接插入排序比较有效第14页/共70页 按增量序列将整个待排记录分割成若干个序列，分别进行直接插入排序。等整按增量序列将整个待排记录分割成若干个序列，分别进行直接插入排序。等整个序列基本有序后，再对全体记录进行一次直接插入排序。个序列基本有

16、序后，再对全体记录进行一次直接插入排序。基本有序基本有序基本有序基本有序：序列中满足以下特性的记录较少：序列中满足以下特性的记录较少方法：方法：第15页/共70页16目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法Shell排序动画 12343229644534781234322964453478123432296445347812343229644534781234322964453478第16页/共70页增量序列为：增量序列为：5 5，3 3，1 14949 3838 6565 9797 76 76 1313 2727 49491313 2727 4949 9797 76 76 49

17、49 38 38 65651313 2727 4949 9797 7676 4949 3838 65 651313 2727 4949 3838 6565 4949 9797 76 7613 27 38 13 27 38 4949 49 65 76 97 49 65 76 97第17页/共70页void ShellInsert(SqList&L,int dk)void ShellInsert(SqList&L,int dk)/对顺序表对顺序表对顺序表对顺序表L L作一趟希尔插入排序作一趟希尔插入排序作一趟希尔插入排序作一趟希尔插入排序./本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较

18、本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较,作了以下修改作了以下修改作了以下修改作了以下修改 /1./1.前后记录位置的增量是前后记录位置的增量是前后记录位置的增量是前后记录位置的增量是dk,dk,而不是而不是而不是而不是1 1 /2.r0 /2.r0只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当j=0j=0时，插入位置已找到时，插入位置已找到时，插入位置已找到时，插入位置已找到 for(i=dk+1;i=L.length;+i)for(i=dk+1;i0<(L.r0.kry,L.rj.key);j-=;j0<(L

19、.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/ShellInsert第18页/共70页void ShellSort(SqList&L,int dlta,int t)/按增量序列按增量序列dlta0.t-1对顺序表对顺序表L作希尔排序作希尔排序 for(k=0;kt;+t)ShellInsert(L,dltak);/一趟增量为一趟增量为daltk的插入

20、排序的插入排序/ShellSort第19页/共70页不稳定空间代价：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)算法分析第20页/共70页10103 3快速排序快速排序一、起泡排序一、起泡排序一、起泡排序一、起泡排序Bubble SortBubble SortBubble SortBubble Sort算法思想:依次比较相邻的记录，如果不满

21、足排序要求，就交换相邻记录，直到所有的记录都已经排好序检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束，避免不必要的比较第21页/共70页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(n2 2)第22页/共70页算法分析稳定空间代价：O(n)时间代

22、价：比较次数最少：O(n)最多：交换次数最多为O(n2)，最少为0，平均为O(n2)最坏，平均时间代价均为O(n2)最好时间代价为O(n)第23页/共70页二、快速排序二、快速排序二、快速排序二、快速排序Quick SortQuick Sort基本思想：基本思想：通过一趟排序将待排序记录分成独立的两部分，通过一趟排序将待排序记录分成独立的两部分，其中一部分记录的关键字均小于另一部分记录其中一部分记录的关键字均小于另一部分记录 的关键字，然后分别对这两部分进行递归排序的关键字，然后分别对这两部分进行递归排序 一趟排序：一趟排序：一趟排序：一趟排序：任意选取一个记录作为枢轴（支点）任意选取一个记录

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

24、：分成两个子序列：分成两个子序列：分成两个子序列：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 i第24页/共70页49 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 76 97 65 4

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

26、ivotkeypivotkey的的的的记记记记录，与枢轴记录交换录，与枢轴记录交换录，与枢轴记录交换录，与枢轴记录交换 (3)(3)重复（重复（重复（重复（1 1）（）（）（）（2 2）直到）直到）直到）直到low=highlow=high为止为止为止为止此时枢轴记录所在的位置此时枢轴记录所在的位置此时枢轴记录所在的位置此时枢轴记录所在的位置i=low=highi=low=high27 38 13 49 76 97 65 491313 2727 38384949 65 65 7676 97 97 第26页/共70页int partition(SqList&L,int low,int high)

27、int partition(SqList&L,int low,int high)/交换顺序表交换顺序表交换顺序表交换顺序表L L中的子表中的子表中的子表中的子表L.rlow.highL.rlow.high的记录的记录的记录的记录,枢轴记录到位枢轴记录到位枢轴记录到位枢轴记录到位,并返回其所在位置并返回其所在位置并返回其所在位置并返回其所在位置 /此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它 piovtkey=L.rlow.key;piovtkey=L.rlow.key;/用用用用

28、子子子子表表表表的的的的第第第第一一一一个个个个记记记记录录录录作作作作枢枢枢枢轴轴轴轴记记记记录录录录 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

29、=priotkey)while(lowhigh&L.rlow.key=priotkey)+low;+low;L.rlow L.rlow L.rhighL.rhigh;/将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端 return low;return low;/返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置/Partition/Partition第27页/共70页int partition(SqList&L,int low,int high)int partition(SqList&L,int

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

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

32、轴记录小的记录交换到低端 while(lowhigh&L.rlow.key=pivotkey)while(lowhigh&L.rlow.key=pivotkey)+low;+low;L.rhigh=L.rlow;L.rhigh=L.rlow;/将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端 L.rlow=L.r0;L.rlow=L.r0;/枢轴记录到位枢轴记录到位枢轴记录到位枢轴记录到位 return low;return low;/返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置/Partiti

33、on/Partition第28页/共70页void Qsort(SqList&L,int low,int high)void Qsort(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.rlo

34、w.high一分为二一分为二一分为二一分为二 Qsort(L,low,pivotloc-1);Qsort(L,low,pivotloc-1);/对低子表递归排序，对低子表递归排序，对低子表递归排序，对低子表递归排序，pivotlocpivotloc是枢轴位置是枢轴位置是枢轴位置是枢轴位置 Qsort(L,pivotloc+1,high);Qsort(L,pivotloc+1,high);/对高子表递归排序对高子表递归排序对高子表递归排序对高子表递归排序 /Qsort/Qsortvoid QuickSort(SqList&L)void QuickSort(SqList&L)/对顺序表对顺序表对顺

35、序表对顺序表L L作快速排序作快速排序作快速排序作快速排序 QSort(L,1,L.length);QSort(L,1,L.length);/QuickSort/QuickSort第29页/共70页枢轴记录的选择尽可能使两部分长度相等选择策略：选择最左/右/中间位置记录随机选择选择平均值第30页/共70页算法分析最差情况：时间代价：O(n2)空间代价：O(n)最佳情况：时间代价：O(nlogn)空间代价：O(logn)平均情况：时间代价：O(nlogn)空间代价：O(logn)第31页/共70页T(n)=O(nlog2n)第32页/共70页33目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与

36、算法123432296445347810104 4选择排序选择排序 一、简单选择排序一、简单选择排序一、简单选择排序一、简单选择排序Select SortSelect Sort第33页/共70页void SelectSort(SqList&L)void SelectSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L作简单选择排序作简单选择排序作简单选择排序作简单选择排序 for(i=1;iL.length;+i)for(i=1;iL.length;+i)/选择第选择第选择第选择第i i个最小的记录，并交换到位个最小的记录，并交换到位个最小的记录，并交换到位个最小的记录，并交换

37、到位 j=SelectMinkey(L,i);j=SelectMinkey(L,i);/在在在在L.ri.L.lengthL.ri.L.length中选择中选择中选择中选择keykey最小的记录最小的记录最小的记录最小的记录 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最小的记录并返回它

38、的位置最小的记录并返回它的位置最小的记录并返回它的位置最小的记录并返回它的位置 min=L.rk.key;minp=k;min=L.rk.key;minp=k;for(i=k+1;i=L.length;i+)for(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;第34页/共70页不稳定空间代价：O(n)时间代价共进行n-1趟排序 比较次数：O(n2)交换次数：n-1总时间代价：O(n2)算法分析算法分析第35页/共

39、70页 若若用用一一个个一一维维数数组组存存放放满满足足此此关关系系的的序序列列，把把这这个个一一维维数数组组看看成成是是一一棵棵完完全全二二叉叉树树，则则堆堆对对应应的的完完全全二二叉叉树树中中所所有有非非终终端端结结点点的的值值均大于或均小于其左右孩子的值。均大于或均小于其左右孩子的值。三、堆排序三、堆排序三、堆排序三、堆排序Heap SortHeap Sort堆的定义堆的定义堆的定义堆的定义：n n个元素的序列个元素的序列个元素的序列个元素的序列KK1 1，K K2 2，K Kn n 当且仅当满足如下关系时称为当且仅当满足如下关系时称为当且仅当满足如下关系时称为当且仅当满足如下关系时称为

40、堆堆堆堆：K Ki i K K2i2i 或或或或 K Ki i K K2i2i K Ki i K K2i+12i+1 K Ki i K K2i+12i+1第41页/共70页大大顶顶堆堆/大大根根堆堆堆排序方法：堆排序方法：（1 1）由一个无序的序列建成一个堆）由一个无序的序列建成一个堆（2 2）输出堆顶的最小值）输出堆顶的最小值（3 3）剩余的元素建成一个新的堆）剩余的元素建成一个新的堆（4 4）重复（）重复（2 2）（）（3 3）093811962783小小顶顶堆堆/小小根根堆堆3085471224369153第42页/共70页49 38 65 97 76 13 27 49输出输出1313后

41、后,用用序列中最后一序列中最后一个记录代替根个记录代替根结点结点筛筛选选为为堆顶元素与它的左右子树根结点比较堆顶元素与它的左右子树根结点比较若右子树根若右子树根 左子树根左子树根 堆顶堆顶 根结点与右子树根交换根结点与右子树根交换若左子树根若左子树根 右子树根右子树根 堆顶堆顶 根结点与左子树根交换根结点与左子树根交换这个调整过程称为这个调整过程称为筛选筛选13384976972765499738497627654927384976496597第43页/共70页对对一一个个无无序序序序列列建建立立堆堆也也是是筛筛选选过过程程,筛筛选选从从n/2个记录开始。个记录开始。49 38 65 97 7

42、6 13 27 497627496538974913496538974997657649273813第44页/共70页499765764927381349386576492797134976654938279713第45页/共70页497665493827971349276549387697134965274938769713第46页/共70页496527493876971349132749387697651349274938769765第47页/共70页134927493876976549132749387697654949273813769765第48页/共70页4949273813769

43、76549132738497697654938271349769765第49页/共70页494938382727131349497676979765654949272738381313494976769797656549491313383827274949767697976565建建大顶堆大顶堆，排序，排序结果为结果为从小到大从小到大第50页/共70页typedef SqList HeapType;typedef SqList HeapType;void HeapAdjust(HeapType&H,int s,int m)void HeapAdjust(HeapType&H,int s,int

44、 m)/已知已知已知已知H.rs.mH.rs.m中记录的关键字除中记录的关键字除中记录的关键字除中记录的关键字除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较大的孩子结点向下筛选较大的孩子结点向下筛选较大的孩子结点向下筛选

45、较大的孩子结点向下筛选 if(jm<(H.rj.key,H.rj+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.

46、i/H.r1.i中最后一个记录相交换中最后一个记录相交换中最后一个记录相交换中最后一个记录相交换 HeapAdjust(H,1,i-1);HeapAdjust(H,1,i-1);/将将将将H.r1.i-1H.r1.i-1重新调整为大顶堆重新调整为大顶堆重新调整为大顶堆重新调整为大顶堆 /HeapSort/HeapSort第52页/共70页算法分析建堆：O(n)删除堆顶:O(log n)一次建堆，n 次删除堆顶总时间代价为 O(nlog n)空间代价为 O(n)T(n)=O(nlog2n)第53页/共70页10105 5归并排序归并排序 Merge Sort 将两个以上的有序序列合并成一个新的有

47、序序列将两个以上的有序序列合并成一个新的有序序列2 2 2 2路归并：路归并：路归并：路归并：把初始含有把初始含有把初始含有把初始含有n n n n个记录的序列看成个记录的序列看成个记录的序列看成个记录的序列看成n n n n个长度为个长度为个长度为个长度为1 1 1 1的有序子序列的有序子序列的有序子序列的有序子序列,采用两两合并的方法最终合并成一个序列采用两两合并的方法最终合并成一个序列采用两两合并的方法最终合并成一个序列采用两两合并的方法最终合并成一个序列第54页/共70页2121252525259393626272720808373716165454494925252121 25254

48、9496262 93930808 72721616 373754540808 2121 2525 2525 4949 6262 7272 93931616 3737 54540808 1616 2121 2525 2525 3737 4949 5454 6262 7272 93932121 2525 2525 49490808 6262 7272 93931616 3737 5454第55页/共70页void Merge(RedType SR,RedType&TR,void Merge(RedType SR,RedType&TR,int i,int m,int n)int i,int m,in

49、t 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)/将将将将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(

50、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复制到复制到复制到复制到TRTR/Merge/Merge第56页/共70页void MSort(RedType SR,RedType&TR1,int s,int void MSort(RedType SR,RedType&TR1,int s,int t)t)/将将将将SRs.tSRs.t归并排序为归并排序为归并排序为归并排序为TR1s.tTR1s.