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

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

1、第十章第十章 内部排序内部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择选择排序排序10.5 归归并排序并排序10.6 基数排序基数排序10.7 各种排序方法比各种排序方法比较较101概述概述一、排序的定一、排序的定一、排序的定一、排序的定义义义义 假假假假设设设设有有有有n n个个个个记录记录记录记录的序列的序列的序列的序列为为为为：R1R1，R2R2，,Rn,Rn 其其其其对应对应对应对应的关的关的关的关键键键键字字字字为为为为K1K1，K2K2，,Kn,Kn 须须须须要确定要确定要确定要确定1 1，2 2，,n,n的一种排列的一种排列的一种排列的

2、一种排列P1P1，P2P2，,Pn,Pn 使：使：使：使：Kp1Kp1K p2K p2K p nK p n 则则则则R p1R p1，R p2R p2，,R pn,R pn为为为为一个按关一个按关一个按关一个按关键键键键字有序的序列。字有序的序列。字有序的序列。字有序的序列。其中，其中，其中，其中，KiKi可以是可以是可以是可以是记录记录记录记录RiRi的主关的主关的主关的主关键键键键字、次关字、次关字、次关字、次关键键键键字或若干数字或若干数字或若干数字或若干数据据据据项项项项的的的的组组组组合。合。合。合。二、排序方法的二、排序方法的二、排序方法的二、排序方法的稳稳稳稳定性定性定性定性 若

3、若若若K Ki i=K=Kj j,(1,(1 i i j j n),n),且排序前，且排序前，且排序前，且排序前，R Ri i在在在在R Rj j前面，前面，前面，前面，若排序后，若排序后，若排序后，若排序后，R Ri i仍在仍在仍在仍在R Rj j前面前面前面前面 则则则则称称称称该该该该排序算法是排序算法是排序算法是排序算法是稳稳稳稳定的，否定的，否定的，否定的，否则则则则是不是不是不是不稳稳稳稳定的。定的。定的。定的。三、排序分三、排序分三、排序分三、排序分类类类类依据待排序的依据待排序的依据待排序的依据待排序的记录记录记录记录的数量划分：的数量划分：的数量划分：的数量划分：内部排序：内

4、部排序：内部排序：内部排序：待排序的待排序的待排序的待排序的记录记录记录记录存放在存放在存放在存放在计计计计算机的内存中的排序算机的内存中的排序算机的内存中的排序算机的内存中的排序过过过过程程程程外部排序：外部排序：外部排序：外部排序：待待待待排排排排序序序序的的的的记记记记录录录录数数数数量量量量很很很很大大大大，内内内内存存存存一一一一次次次次放放放放不不不不下下下下全全全全部部部部记记记记录录录录，在在在在排序排序排序排序过过过过程中程中程中程中还还还还需需需需访问访问访问访问外存的排序外存的排序外存的排序外存的排序过过过过程。程。程。程。四、内部排序方法四、内部排序方法四、内部排序方法

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

6、另设设设设一一一一组组组组索引指索引指索引指索引指针针针针#define MAXSIZE 20#define MAXSIZE 20 /一一一一个个个个用用用用作作作作示示示示例例例例的的的的小小小小依依依依次次次次表表表表的最大的最大的最大的最大长长长长度度度度typedef int KeyType;/typedef int KeyType;/定定定定义义义义关关关关键键键键字字字字类类类类型型型型为为为为整数整数整数整数类类类类型型型型typedef structtypedef struct KeyType key;KeyType key;/关关关关键键键键字字字字 InfoType oth

7、erinfo;InfoType otherinfo;/其它数据其它数据其它数据其它数据项项项项RedType;RedType;/记录类记录类记录类记录类型型型型typedef structtypedef struct RedType rMAXSIZE;RedType rMAXSIZE;/r0/r0赋赋赋赋闲闲闲闲或或或或用用用用作作作作哨哨哨哨兵兵兵兵单单单单元元元元 int length;int length;/依次表依次表依次表依次表长长长长度度度度SqList;SqList;102插入排序插入排序insert sorting一、干脆插入排序一、干脆插入排序一、干脆插入排序一、干脆插入排序

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

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

10、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 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.

11、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.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/In

12、sertSort算法分析算法分析稳定空间代价：O(n)时间代价：最佳状况：n-1次比较，O(n)最差状况：O(n2)比较次数为平均状况：O(n2)例例：在在序序列列13，27，35，48，65，72中中插插入入20或或603565132748722060二、折半插入排序二、折半插入排序Binary Insertsort 用折半用折半查查找的方法找到插入位置找的方法找到插入位置void BInsertSort(SqList&L)void BInsertSort(SqList&L)/对对对对依次表依次表依次表依次表L L做折半插入排序做折半插入排序做折半插入排序做折半插入排序 for(i=2;i=

13、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(low=hight)while(low=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/BI

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

15、基本有序：序列中满满足以下特性的足以下特性的记录较记录较少少方法：方法：17目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法Shell排序动画 12343229644534781234322964453478123432296445347812343229644534781234322964453478增量序列增量序列为为：5，3，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 ShellInse

16、rt(SqList&L,int dk)void ShellInsert(SqList&L,int dk)/对对对对依次表依次表依次表依次表L L作一趟希作一趟希作一趟希作一趟希尔尔尔尔插入排序插入排序插入排序插入排序./本算法与一趟干脆插入排序比本算法与一趟干脆插入排序比本算法与一趟干脆插入排序比本算法与一趟干脆插入排序比较较较较,作了以下修改作了以下修改作了以下修改作了以下修改 /1./1.前后前后前后前后记录记录记录记录位置的增量是位置的增量是位置的增量是位置的增量是dk,dk,而不是而不是而不是而不是1 1 /2.r0/2.r0只只只只是是是是暂暂暂暂存存存存单单单单元元元元，不不不不是

17、是是是哨哨哨哨兵兵兵兵。当当当当j=0j=0时时时时，插插插插入入入入位位位位置已找到置已找到置已找到置已找到 for(i=dk+1;i=L.length;+i)for(i=dk+1;i0<(L.r0.kry,L.rj.key);j-=dk)for(j=i-dk;j0<(L.r0.kry,L.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.rj;/记记记记录录录录后后后后移移移移，查查查查找找找找插插插插入入入入位置位置位置位置 L.rj+dk=L.r0;L.rj+dk=L.r0;/插入插入插入插入 /ShellInsert/ShellInsertvoid S

18、hellSort(SqList&L,int dlta,int t)/按增量序列按增量序列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(nlog

19、2n)算法分析算法分析103快速排序快速排序一、起泡排序一、起泡排序Bubble 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-1趟排序，趟排序，共共进进行行n(n-1)/2次比次比较较T(n

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

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

22、s,L.rs+1,L.rt分成两个子序列：分成两个子序列：分成两个子序列：分成两个子序列：L.rs,L.rs+1,L.ri-1 L.rs,L.rs+1,L.ri-1和和和和 L.ri+1,L.ri+2,L.rt L.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

23、65 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

24、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 high

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

26、轴记录轴记录轴记录轴记录 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=prio

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

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

29、/枢枢枢枢轴轴轴轴记记记记录录录录关关关关键键键键字字字字 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(l

30、owhigh&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 Qsort

31、(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

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

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

34、tSort(SqList&L)/对对对对依次表依次表依次表依次表L L作作作作简洁选择简洁选择简洁选择简洁选择排序排序排序排序 for(i=1;iL.length;for(i=1;iL.length;+i)+i)/选选选选择择择择第第第第i i个个个个最最最最小小小小的的的的记记记记录录录录，并并并并交交交交换换换换到位到位到位到位 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

35、.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(i=k+1;i=L.length;i+)if(L.r

36、i.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)算法分析算法分析 若若用用一一个个一一维维数数组组存存放放满满足足此此关关系系的的序序列列，把把这这个个一一维维数数组组看看成成是是一一棵棵完完全全二二叉叉树树，则则堆堆对对应应的的完完全全二二叉叉树树中中全全部部非非终终端端结结点点的的值值均大于或均小于其左右孩子的均大于或均小于其左右孩子的值值。三、堆排序三、

37、堆排序Heap Sort堆的定堆的定义义：n个元素的序列个元素的序列K1，K2，Kn当且当且仅仅当当满满足如下关系足如下关系时时称称为为堆堆：Ki K2i 或或 Ki K2i Ki K2i+1 Ki K2i+1大大顶顶堆堆/大大根根堆堆堆排序方法：堆排序方法：（1）由一个无序的序列建成一个堆）由一个无序的序列建成一个堆（2）输输出堆出堆顶顶的最小的最小值值（3）剩余的元素建成一个新的堆）剩余的元素建成一个新的堆（4）重复（）重复（2）（）（3）093811962783小小顶顶堆堆/小小根根堆堆308547122436915349 38 65 97 76 13 27 49输输出出13后后,用用序

38、列中最序列中最终终一一个个记录记录代替根代替根结结点点筛筛选选为为堆堆顶顶元素与它的左右子元素与它的左右子树树根根结结点比点比较较若右子若右子树树根根左子左子树树根根堆堆顶顶 根根结结点与右子点与右子树树根交根交换换若左子若左子树树根根右子右子树树根根堆堆顶顶 根根结结点与左子点与左子树树根交根交换换这这个个调调整整过过程称程称为为筛选筛选13384976972765499738497627654927384976496597对对一一个个无无序序序序列列建建立立堆堆也也是是筛筛选选过过程程,筛筛选选从从n/2个个记录记录起先。起先。49 38 65 97 76 13 27 4976274965

39、389749134965389749976576492738134997657649273813493865764927971349766549382797134976654938279713492765493876971349652749387697134965274938769713491327493876976513492749387697651349274938769765491327493876976549492738137697654949273813769765491327384976976549382713497697654938271349769765492738134976

40、97654913382749769765建建大大顶顶堆堆，排序，排序结结果果为为从小到大从小到大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中中中中记记记记录录录录的的的的关关关关键键键键字字字字除除除除H.rs.keyH.rs.key外外外外均均均均满满满满足足足足堆堆堆堆的定的定的定的定义义义义，/本本本本函函函函数数数数调调调调整整整整H.r

41、sH.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+1.key)if(j0;-i)/for(i=H.length/2;i0;-i)/把把把把H.ri.lengthH.ri.length建成大建成大建成大建成大顶顶顶顶堆堆堆堆 HeapAdjust(H,

42、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中最中最中最中最终终终终一个一个一个一个记录记录记录记录相交相交相交相交换换换换 HeapAdjust(H,1,i-1);HeapAdjust(H,1,i-1);/将将将将H.r1.i-1H.r1.i-1重新重新重新重新调调调调整整整整为为为为大大大大

43、顶顶顶顶堆堆堆堆 /HeapSort/HeapSort算法分析算法分析建堆：O(n)删除堆顶:O(logn)一次建堆，n次删除堆顶总时间代价为O(nlogn)空间代价为O(n)T(n)=O(nlog2n)105归归并排序并排序 Merge Sort 将两个以上的有序序列合并成一个新的有序序列将两个以上的有序序列合并成一个新的有序序列2路路归归并：并：把初始含有把初始含有n个个记录记录的序列看成的序列看成n个个长长度度为为1的有序子序列的有序子序列,接受两两接受两两合并的方法最合并的方法最终终合并成一个序列合并成一个序列void Merge(RedType SR,RedType&TR,void

44、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)/将将将将SRSR中中中中记录记录记录记录由小到大地并入由小到大地并入由小到大地并入由小到大地并入TRTR if LQ(SRi.key,SRj.key)TRk=SRi+;if LQ(SRi.key,SRj.key

45、)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复制到复制到复制到复制到TRTR/Merge/Mergevoid MSort(RedType SR,RedType&TR1,int s,int t)void MSort(RedType SR,RedType&TR1,int s,i

46、nt 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,TR2,s,m);/递归递归递归递归地将地将地将地将SRs.mSRs.m归归归归并并并并为为为为有序的有序的有序的有序的TR2s.mTR2s.m Msort(SR,TR2,m+1,t);Msort(SR,

47、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/Msortvoid MergeSort(SqList&L)void MergeSort(SqList&L)/对对对对依次表依次表依次表依次表L L作作作作归归归归并排序并排序并排序并排序.Msort(L.r,L.

48、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)任何状况下都是106基数排序基数排序Radix Sort 不通不通过过关关键键字之字之间间的比的比较进较进行排序行排序 一、多关一、多关键键字排序字排序最高位最高位最高位最高位优优优优先法先法先法先法MSDMSD：先按关先按关先按关先按关键键键键字字字字K0K0排序，排序，排序，排序，将序列分成若干个子序列将序列分成若干个子序列将序列分成若干个子序列将序列分成

49、若干个子序列 每个子序列每个子序列每个子序列每个子序列记录记录记录记录的的的的K0K0均相等均相等均相等均相等 然后在每个子序列中按然后在每个子序列中按然后在每个子序列中按然后在每个子序列中按K1K1排序排序排序排序 按按按按K1K1值值值值把子序列分成更小的子序列把子序列分成更小的子序列把子序列分成更小的子序列把子序列分成更小的子序列 直到最直到最直到最直到最终终终终按按按按Kd-1Kd-1排序后，排序后，排序后，排序后，整个序列有序整个序列有序整个序列有序整个序列有序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(1,3),(2,

50、4),(2,3),(3,2),(3,4),(4,4),(4,3)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)最低位最低位最低位最低位优优优优先法先法先法先法LSDLSD：依据最次关依据最次关依据最次关依据最次关键键键键字字字字Kd-1Kd-1起起起起对记录对记录对记录对记录排序排序排序排序 再依据再依据再依据再依据Kd-2Kd-2对记录对记录对记录对记录排序排序排序排序 。依据依据依据依据K0K0对记录对记录对记录对记录排序后，排序后，排序后，排序后，整个序列有序整个序列有序整个序列有序整个序列有序(1,1),(2,4),(1,3),(3,2)