1、12023-9-41第10章 排序22023-9-42本章目录v10.1 概述概述v10.2 插入排序插入排序 10.2.1 直接插入排序直接插入排序 10.2.2 折半插入排序折半插入排序 *10.2.3 二路插入排序二路插入排序 *10.2.4 表插入排序表插入排序 10.2.5 希尔排序希尔排序v10.3 交换排序交换排序 10.3.1 起泡排序起泡排序 10.3.2 快速排序快速排序v10.4 选择排序选择排序 10.4.1 直接选择排序直接选择排序 10.4.2 树形选择排序树形选择排序10.4.3 堆排序堆排序v10.5 归并排序归并排序v10.6 分配排序分配排序v10.7 内部
2、排序方法的比较内部排序方法的比较v10.8 外部排序外部排序 10.8.1 文件管理文件管理 10.8.2 外部排序外部排序 10.8.3 多路归并排序多路归并排序 10.8.4 置换选择排序置换选择排序 *10.8.5 最佳归并树最佳归并树 *10.8.6 磁带排序磁带排序32023-9-43主要内容v知识点知识点v1、排序的定义，排序可以看作是线性表的一种操作排序的定义，排序可以看作是线性表的一种操作v2、排序的分类，稳定排序与不稳定排序的定义。、排序的分类，稳定排序与不稳定排序的定义。v3、插入排序（直接插入、插入排序（直接插入、对分插入对分插入、二路插入、表插入、希尔插、二路插入、表插
3、入、希尔插入排序）。入排序）。v4、交换排序（冒泡排序、交换排序（冒泡排序、快速排序快速排序）。）。v5、选择排序（简单选择排序、树形选择排序、选择排序（简单选择排序、树形选择排序、堆排序堆排序）。）。v6、归并排序、基数排序。、归并排序、基数排序。v7、外部排序、外部排序v重点难点重点难点v1、各种排序所基于的基本思想。、各种排序所基于的基本思想。v2、排序性能的分析，是否是稳定排序。、排序性能的分析，是否是稳定排序。v3、折半插入、希尔排序折半插入、希尔排序。v4、快速排序快速排序。v5、堆排序堆排序。v6、败者树、置换选择排序、败者树、置换选择排序、最佳归并树最佳归并树。v7、对每种排序
4、方法的学习，能举一反三。、对每种排序方法的学习，能举一反三。42023-9-44基本概念 v排序：排序：假设含假设含n个记录的序列为个记录的序列为R1,R2,Rn，其相应的关键字序列为其相应的关键字序列为 K1,K2,Kn，这些关键字相互之间可以进行比较，即在它这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系们之间存在着这样一个关系Ks1Ks2Ksn，按此固有关系将按此固有关系将n个记录的序列重新排列为个记录的序列重新排列为 Rs1,Rs2,Rsn 的操作称作的操作称作排序排序。52023-9-45基本概念稳定排序稳定排序：若若Ki为关键字，为关键字，Ki=Kj（ij），且在排序
5、），且在排序前的序列中前的序列中Ri领先于领先于Rj。经过排序后，。经过排序后，Ri与与Rj的相对次的相对次序保持不变（即序保持不变（即Ri仍领先于仍领先于Rj），则称这种排序方法是），则称这种排序方法是稳定的稳定的，否则称之为，否则称之为不稳定的。不稳定的。内部排序内部排序 ：若整个排序过程不需要访问外存便能完成，：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序则称此类排序问题为内部排序 外部排序外部排序：若参加排序的记录数量很大，整个序列的排：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问题为序过程不可能一次在内存中完成，则称此类排序问
6、题为外部排序外部排序 62023-9-46排序的类型定义#define n 待排序记录的个数待排序记录的个数typedef struct int key;AnyType other;记录其它数据域记录其它数据域 RecType;RecType Rn+1;72023-9-47基本思想基本思想：假定第一个记录有序假定第一个记录有序，从第从第2 2个记录开个记录开始，将待排序的记录插入到有序序列中，使有序序始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。列逐渐扩大，直至所有记录都进入有序序列中。插入排序 插入排序种类插入排序种类：直接插入排序直接插入排序 折半插
7、入排序折半插入排序 二路插入排序二路插入排序 表插入排序表插入排序 希尔排序希尔排序 82023-9-48直接插入排序基本思想基本思想：将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i 92023-9-49示例初始关键字序列：51 33 62 96 87 17 28 51i=2(33)33 51 62 96 87 17 28 51i=3(62)33 51 62 96 87 17 28 51i=4(96)33 51 62 96 87 17 28 51i=5(87)33 51 62 87 96 17 28 51i=6(17)17 33 51 62
8、87 96 28 51i=7(28)17 28 33 51 62 87 96 51i=8(51)17 28 33 51 51 62 87 96102023-9-410一趟直接插入排序算法void StrOnePass(RecType R，int i)已知已知R1.i-1中的记录按关键字非递减有序排列，本算法中的记录按关键字非递减有序排列，本算法 插入插入Ri,使使R1.i中的记录按关键字非递减有序排列中的记录按关键字非递减有序排列 R0=Ri;j=i-1;将待排序记录放进监视哨将待排序记录放进监视哨 x=R0.key;从后向前查找插入位置，将大于待排序记录向后移动从后向前查找插入位置，将大于待
9、排序记录向后移动 while(x Rj.key)Rj+1=Rj;j-;记录后移记录后移 Rj+1=R0;将待排序记录放到合适位置将待排序记录放到合适位置 StrOnePass112023-9-411直接插入排序算法void StrInsSort1(RecType R，int n)本算法对本算法对R1.n进行直接插入排序进行直接插入排序 for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 StrOnePass(R，i)；122023-9-412直接插入排序性能分析w最坏情况最坏情况比较次数为 =(n+2)(n-1)/2 n2ii移动次数为 =(n+4)(n-1)/2 n2)21(
10、ii最好情况最好情况比较次数为n-1次移动次数为2（n-1）次132023-9-413直接插入排序的优缺点 直接插入排序直接插入排序算法简单算法简单，当待排序记录数量，当待排序记录数量n很小时，局部有序时，较为适用。很小时，局部有序时，较为适用。当当n很大时，其效率不高很大时，其效率不高。若对直接插入排序算法进行改进，可从减少若对直接插入排序算法进行改进，可从减少“比较比较”和和“移动移动”次数这两方面着手次数这两方面着手。折半存入排序折半存入排序、二路插入排序二路插入排序、表插入排序表插入排序、希尔排序希尔排序都是对直接插入排序的改进都是对直接插入排序的改进。142023-9-414折半插入
11、排序折半插入排序vvoid BinsSort(RecType R，int n)v 对对R1.n进行折半插入排序进行折半插入排序v for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 v R0=Ri;将待排记录将待排记录Ri暂存到暂存到R0v low=1;high=i-1;设置折半查找的范围设置折半查找的范围 Rlow.highv while(low=high)v m=(low+high)/2;折半折半v if(R0.keyhigh;j-)Rj+1=Rj;记录后移记录后移v Rhigh+1=R0;插入插入v forvBinsSort152023-9-415折半插入排序性能分析折半
12、插入排序性能分析v减少了比较次数，移动次数不变。v时间复杂度仍为O（n2）。162023-9-416 在对一组记录在对一组记录（5454，3838，9696，2323，1515，7272，6060，4545，8383）进行直接排序时，当把第进行直接排序时，当把第7 7个记录个记录6060插入到有插入到有序表时，为寻找插入位置需比较多少次序表时，为寻找插入位置需比较多少次自测题自测题 1172023-9-417二路插入排序二路插入排序v对折半插入排序改进，减少了移动记录的次数，对折半插入排序改进，减少了移动记录的次数，但它要借助但它要借助n个记录的辅助空间，即其空间复杂个记录的辅助空间，即其空间
13、复杂度为度为O（n）。）。v基本思想：另设一数组基本思想：另设一数组d，将，将R1赋值给赋值给d1，并将并将d1看作排好序的中间记录，从第二个记看作排好序的中间记录，从第二个记录起依次将关键字小于录起依次将关键字小于d1的记录插入的记录插入d1之前之前的有序序列，将关键字大于的有序序列，将关键字大于d1的记录插入的记录插入d1之后的有序序列。之后的有序序列。v借助两个变量借助两个变量first和和final来指示排序过程中有来指示排序过程中有序序列第一个记录和最后一个记录在序序列第一个记录和最后一个记录在d中的位置。中的位置。182023-9-418v初始关键字序列：初始关键字序列：51 33
14、 62 96 87 17 28 51 vi=1 51v firstfinalvi=2 51 33v final firstvi=3 51 62 33v final firstvi=4 51 62 96 33v final firstvi=5 51 62 87 96 33v final firstvi=6 51 62 87 96 17 33v final first vi=7 51 62 87 96 17 28 33v final first vi=8 51 51 62 87 96 17 28 33v final first 192023-9-419二路插入排序算法二路插入排序算法vvoid B
15、iInsertSort(RecType R，int n)v二路插入排序的算法二路插入排序的算法v int dn+1;辅助存储辅助存储v d1=R1;first=1;final=1;v for(i=2;i=d1.key)插入后部插入后部v low=1;high=final;v while(low=high)折半查找插入位置折半查找插入位置v m=(low+high)/2;v if(Ri.key=high+1;j-)dj+1=dj;移动元素移动元素v dhigh+1=Ri;final+;插入有序位置插入有序位置v 202023-9-420 else if(first=1)插入前部插入前部v fir
16、st=n;dn=Ri;v else low=first;high=n;v while(low=high)v m=(low+high)/2;v if(Ri.key dm.key)high=m-1;v else low=m+1;v whilev for(j=first;j=high;j+)dj-1=dj;v 移动元素移动元素v dhigh=Ri;first-;v ifv if v /for v212023-9-421表插入排序表插入排序v静态链表静态链表v#define n 待排序记录的个数待排序记录的个数vtypedef structv int key;v AnyType other;记录其他数
17、据域记录其他数据域v int next;v STListType;vSTListType SLn+1;222023-9-422表插入排序算法表插入排序算法vvoid ListInsSort(STListType SL,int n)v 对记录序列对记录序列SL1.n作表插入排序。作表插入排序。v SL0.key=MAXINT;v SL0.next=1;SL1.next=0;v for(i=2;i=n;i+)查找插入位置查找插入位置v j=0;v for(k=SL0.next;SLk.key=SLi.key;)v j=k,k=SLk.next;v SLj.next=i;SLi.next=k;v 结
18、点结点i插入在结点插入在结点j和结点和结点k之间之间v for v ListInsSort232023-9-423表物理排序表物理排序vvoid Arrange(STListType SL，int n)v 调整静态链表调整静态链表SL中各结点的指针值，使记录按关键字有序排列中各结点的指针值，使记录按关键字有序排列v p=SL0.next;p指示第一个记录的当前位置指示第一个记录的当前位置v for(i=1;in;i+)v SL1.i-1 记录已按关键字有序，第记录已按关键字有序，第i个记录的当前位置应不小于个记录的当前位置应不小于iv while(p=1;d=d/2)for(i=1+d;i0&
19、R0.keyaj+1.key），），则将其则将其交换交换，最终达到有序化，最终达到有序化 302023-9-430起泡排序示例初始初始关键关键字字5133629687172851第第一一趟趟33516287172851第第四四趟趟3317 285151628796第第三三趟趟3351172851628796第第二二趟趟3351621728518796第第五五趟趟17 28335151628796第第六六趟趟17 28335151628796312023-9-431void BubbleSort(RecType R，int n)起泡排序起泡排序 i=n;i 指示无序序列中最后一个记录的位置指示无
20、序序列中最后一个记录的位置 while(i1)LastExchange=1;记最后一次交换发生的位置记最后一次交换发生的位置 for(j=1;jRj+1.key)RjRj+1;逆序时交换逆序时交换 LastExchange=j;if i=LastExchange;while 起泡排序算法322023-9-432起泡排序性能分析01n移动次数比较次数最佳情况2/)1(32/)1(11nnnnini移动次数比较次数最差情况平均时间复杂度：平均时间复杂度：O(n2)332023-9-433一组关键字（一组关键字（19,01,26,92,87,11,43,87,2119,01,26,92,87,11,
21、43,87,21），），进行冒泡排序，进行冒泡排序，试列出每一趟排序后的关键字序列试列出每一趟排序后的关键字序列 自测题自测题 3 冒泡排序冒泡排序示例342023-9-434快速排序 基本思想基本思想：从排序序列中任选一记录作为从排序序列中任选一记录作为枢轴枢轴（或支点），凡其（或支点），凡其关键字小于枢轴的关键字小于枢轴的记录均移动至该记录之前，而关键字大于记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后枢轴的记录均移动至该记录之后。一趟排。一趟排序后序后“枢轴枢轴”到位，并将序列分成两部分，到位，并将序列分成两部分，再分别对这两部分排序。再分别对这两部分排序。由由Hoar
22、e(图灵奖获得者图灵奖获得者)1962年提出，被评年提出，被评为为20世纪十大优秀算法之一世纪十大优秀算法之一。352023-9-435快速排序图示不大于不大于不小于不小于1n枢枢轴轴362023-9-436快速排序示例初始关键字序列初始关键字序列：51 33 62 96 87 17 28 51R0=51 i(枢轴枢轴)jj向前扫描向前扫描 i j第一次交换之后：第一次交换之后：28 33 62 96 87 17 51 i ji向后扫描向后扫描 i j第二次交换之后：第二次交换之后：28 33 96 87 17 62 51 i jj向前扫描向前扫描 i j 第三次交换之后：第三次交换之后：28
23、 33 17 96 87 62 51i向后扫描向后扫描 i j 第四次交换之后：第四次交换之后：28 33 17 87 96 62 51j向前扫描向前扫描 i j 完成一趟排序：完成一趟排序：28 33 17 51 87 96 62 51 ij 372023-9-437快速排序示例初始关键字序列初始关键字序列：51 33 62 96 87 17 28 51一趟排序之后一趟排序之后：28 33 17 51 87 96 62 51 分别进行快速排序：分别进行快速排序：17 28 33 结束结束 结束结束 51 62 87 96 51 62 结束结束 结束结束快速排序后的序列：快速排序后的序列：17
24、 28 33 51 51 62 87 96382023-9-438快速排序算法int Partition(RecType R，int l，int h)交换记录子序列交换记录子序列Rl.h中的记录，使枢轴记录到位并返回其所在位置中的记录，使枢轴记录到位并返回其所在位置 int i=l;j=h;用变量用变量i,j记录待排序记录首尾位置记录待排序记录首尾位置 R0=Ri;以子表的第一个记录作枢轴，将其暂存到记录以子表的第一个记录作枢轴，将其暂存到记录R0中中 x=Ri.key;用变量用变量x存放枢轴记录的关键字存放枢轴记录的关键字 while(ij)从表的两端交替地向中间扫描从表的两端交替地向中间扫
25、描 while(i=x)j-;Ri=Rj;将比枢轴小的记录移到低端将比枢轴小的记录移到低端 while(ij&Ri.key=x)i+;Rj=Ri;将比枢轴大的记录移到高端将比枢轴大的记录移到高端 while Ri=R0;枢轴记录到位枢轴记录到位 return i;返回枢轴位置返回枢轴位置Partition 392023-9-439快速排序算法void QuickSort(RecType R，int s，int t)对记录序列对记录序列Rs.t进行快速排序进行快速排序 if(st)k=Partition(R,s,t);QuickSort(R,s,k-1);QuickSort(R,k+1,t);i
26、f QuickSort 快速排序的快速排序的平均时间复杂度平均时间复杂度为为O（nlog2n）最差为最差为O(n2)402023-9-440对下列一组关键字对下列一组关键字（46,58,15,45,90,18,10,6246,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果试写出快速排序的每一趟的排序结果 自测题自测题 4 快速排序快速排序示例412023-9-441 设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排，使得红色砾石在前，白色砾石居中，蓝色砾石居后。对每粒砾石的颜色只能察看一次，且只允许交换操作来调整砾石的位置。【
27、上海大学 2019 二 2(18分)】算法举例算法举例 10.110.1 快速排序快速排序422023-9-442红、白、兰三色排序算法红、白、兰三色排序算法vvoid QkSort(rectype r,int n)vint i=1,j=1,k=n;v while(j=k)v if(rj=1)当前元素是红色当前元素是红色v rirj;i+;j+;v else if(rj=2)j+;当前元素是白色当前元素是白色v else (rj=3 当前元素是兰色当前元素是兰色v rjrk;k-;vQkSort432023-9-443 冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡
28、的下沉)请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学2019二.3(9分)】【北京邮电大学1992六(10分)】算法举例算法举例 10.2 10.2 双向双向冒泡排序442023-9-444vvoid BubbleSort2(int a,int n)v 相邻两趟向相反方向起泡的冒泡排序算法相邻两趟向相反方向起泡的冒泡排序算法vchange=1;low=0;high=n-1;冒泡的上下界冒泡的上下界v while(lowhigh&change)v change=0;设不发生交换设不发生交换v for(i=low;iai+1)v aiai+1;change=1;有交换有交换,修改标志修改标志
29、changev high-;修改上界修改上界v for(i=high;ilow;i-)气泡下沉气泡下沉,小元素上浮小元素上浮(向左向左)v if(aiai-1)v aiai-1;change=1;有交换有交换,修改标志修改标志changev low+;修改下界修改下界v while vBubbleSort2 算法举例算法举例 10.2 10.2 双向双向冒泡排序的算法452023-9-445 对给定关键字序号对给定关键字序号j(1jn)j(1jn)，要求在无序记录，要求在无序记录A1.nA1.n中找到关键字从小到大排在第中找到关键字从小到大排在第j j位上的记录，写位上的记录，写一个算法利用快
30、速排序的划分思想实现上述查找。一个算法利用快速排序的划分思想实现上述查找。(要求要求用最少的时间和最少的空间用最少的时间和最少的空间)例如：给定无序关键字例如：给定无序关键字7,5,1,6,2,8,9,37,5,1,6,2,8,9,3，当，当j=4j=4时，时，找到的关键字应是找到的关键字应是5 5。【中科院研究生院中科院研究生院20192019十二十二(15(15分分)】【武汉理工大学武汉理工大学20192019四四.3(35/3.3(35/3分分)】算法举例算法举例 10.3 10.3 快速排序462023-9-446vint partition(RecType A,int 1,n)v i
31、nt i=1,j=n;x=Ai.key;v i=1;v while(ij)v while(i=x)j-;v if(ij)Ai+=Aj;v while(ij&Ai.key=x)i+;v if(ij)Aj-=Ai;v v return i;v v void Find_j(RecType A,int n,int j)v i=partition(A,1,n);v while(i!=j)v if(ij)i=quicksart(A,i+1,n);在后半部分继续进行划在后半部分继续进行划分分v else i=quicksart(R,1,i-1);在前半部分继续进行划在前半部分继续进行划分分v 算法举例算法举
32、例 10.3 10.3 的算法472023-9-447选择排序 基本思想基本思想：依次从待排序记录序列中选择出关键：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的字值最小（或最大）的记录、关键字值次之的记录、记录、，并分别将它们定位到序列左侧，并分别将它们定位到序列左侧（或右侧）的第（或右侧）的第1个位置、第个位置、第2 2个位置、个位置、，从而使待排序的记录序列成为按关键字值由小从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。到大（或由大到小）排列的有序序列。选择排序种类选择排序种类：直接（简单）选择排序直接（简单）选择排序 树形选择排序树
33、形选择排序 堆排序堆排序 482023-9-448直接选择排序 待排记录序列的状态为：待排记录序列的状态为：有序序列有序序列R1.i-1 无序序列无序序列 Ri.n有序序列中有序序列中所有记录的关键字均小于无序序列中记所有记录的关键字均小于无序序列中记录的关键字录的关键字，第，第i趟直接选择排序是从无序序列趟直接选择排序是从无序序列Ri.nRi.n的的n-i+1n-i+1记录中选出记录中选出关键字最小关键字最小的记录加入的记录加入有序序列有序序列 492023-9-449直接选择排序示例初始关键字序列初始关键字序列：51 33 62 96 87 17 28 51 第一趟排序后：第一趟排序后：1
34、7 33 62 96 87 51 28 51 第二趟排序后：第二趟排序后：17 28 28 62 96 87 51 33 51 第三趟排序后：第三趟排序后：17 28 28 33 33 96 87 51 62 51第四趟排序后：第四趟排序后：17 28 28 33 33 51 87 96 62 51第五趟排序后：第五趟排序后：17 28 28 33 33 51 51 96 62 87第六趟排序后：第六趟排序后：17 28 28 33 33 51 51 62 96 87第七趟排序后：第七趟排序后：17 28 28 33 33 51 51 62 87 96 502023-9-450直接选择排序算法
35、void SelectSort(RecType R，int n)对记录序列对记录序列R1.n作直接选择排序。作直接选择排序。for(i=1;in;i+)选择第选择第i小的记录，并交换到位小的记录，并交换到位 k=i;假定第假定第i个元素的关键字最小个元素的关键字最小 for(j=i+1;j=n;j+)找最小元素的下标找最小元素的下标 If(Rj.keyRk.key)k=j;if(i!=k)RiRk;与第与第i个记录交换个记录交换 forSelectSort 直接选择排序的平均时间复杂度平均时间复杂度为O（n2）记录移动次数记录移动次数最好情况最好情况：0 0 最坏情况最坏情况：3(3(n-1)
36、n-1)比较次数比较次数(与初始状态无关与初始状态无关):):)(21)(211nninni512023-9-451 基本思想：对基本思想：对n个待排序记录的关键字进行两两比个待排序记录的关键字进行两两比较，从中选出较，从中选出 n/2 个较小者再两两比较，直到选出关个较小者再两两比较，直到选出关键字最小的记录为止，此为键字最小的记录为止，此为一趟排序一趟排序。一趟选出的关键字最小的记录称为一趟选出的关键字最小的记录称为“冠军冠军”，而，而“亚军亚军”是从与是从与“冠军冠军”比较失败的记录中找出比较失败的记录中找出。输出输出“冠军冠军”后，将（冠军）叶子结点关键字改后，将（冠军）叶子结点关键字
37、改为最大，继续进行锦标赛排序，直到选出关键字次小为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。的记录为止，如此循环直到输出全部有序序列。树形选择排序(锦标赛排序)522023-9-452 对关键字序列对关键字序列72,73,71,23,94,16,05,68进行树形进行树形选择排序选择排序 树形选择排序(锦标赛排序)052305722316057273712394160568532023-9-453“亚军亚军”是从与是从与“冠军冠军”比较失败的记录中找出比较失败的记录中找出的的树形选择排序(锦标赛排序)1623167123166872737123941
38、668亚军542023-9-454 n个记录的锦标赛排序，每选择一个记录需个记录的锦标赛排序，每选择一个记录需 log2n 次比较，次比较，时间复杂度为时间复杂度为O(nlog2n)。缺点：需要缺点：需要较多的辅助存储空间较多的辅助存储空间；与与“最大值最大值”进行多次多余的比较进行多次多余的比较。对树形排序的改进是堆排序 树形选择排序性能分析 552023-9-455堆的定义：堆是满足下列性质的序列堆的定义：堆是满足下列性质的序列K1,K2,Kn：堆排序 12ii2iiKKKK或12ii2iiKKKK（i=1,2,n/2）若上述序列是堆，则若上述序列是堆，则K K1 1必是序列中的最小值或最
39、大必是序列中的最小值或最大值，分别称作小顶堆或大顶堆值，分别称作小顶堆或大顶堆 （小堆或大堆，小根堆或大根堆）。（小堆或大堆，小根堆或大根堆）。若将此序列看成是一棵完全二叉树，则堆或是空树或是满若将此序列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，任何一足下列特性的完全二叉树：其左、右子树分别是堆，任何一个结点的值不大于个结点的值不大于(或不小于或不小于)左左/右子女结点（若存在）的值右子女结点（若存在）的值 562023-9-456堆排序示例 28 51 33 62 87 96 17 51 51 87 33 28 51 62 96 17 96，51，
40、87，33，28，62，51，17 是大顶堆 例如：17，28，51，33，62，96，87，51 是小顶堆572023-9-457堆排序基本思想基本思想：先建一个堆，即先选得一个：先建一个堆，即先选得一个关键字最大或最小的记录关键字最大或最小的记录，然后与序列中，然后与序列中最后一个记录交换，之后将序列中最后一个记录交换，之后将序列中前前n-1个个记录重新调整为一个堆（调堆的过程称为记录重新调整为一个堆（调堆的过程称为“筛选筛选”），再将堆顶记录和第），再将堆顶记录和第n-1个记录个记录交换，如此反复直至排序结束。交换，如此反复直至排序结束。堆排序需解决的两个问题：堆排序需解决的两个问题：如
41、何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？成为一个新的堆？582023-9-458第二个问题解决方法第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替代之；方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆的堆第一个问题解决方法第一个问题解决方法方法：把整个数
42、组方法：把整个数组R1到到Rn调整为一个大根堆，即把调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为堆。需完全二叉树中以每一个结点为根的子树都调整为堆。需要将以序号为要将以序号为 n/2 ，n/2 1，1的结点作为根的结点作为根的子树调整为堆的子树调整为堆用筛选法调整堆用筛选法调整堆592023-9-459调整堆示例2851336287961751(a)堆2851336287965117(b)17与51交换后的情景602023-9-460调整堆示例5151876228963317(d)28与87交换后调成的新堆3351516287962817(c)调整后的新堆612023-9-
43、461建堆示例初始关键字序列：初始关键字序列：51，33，62，96，87，17，28，51为例，为例，其初始建大顶堆过程其初始建大顶堆过程 3362968728175151(a)4.8是堆，不调整3362968728175151(b)3.8是堆，不调整622023-9-462建堆示例3362968728175151(c)2.8不是堆，进行筛选不是堆，进行筛选9662518728175133(d)1.8不是堆，进行筛选不是堆，进行筛选8762515128179633(e)建成的大顶堆建成的大顶堆632023-9-463堆排序筛选算法void Sift(RecType R，int i，int m
44、)假设假设Ri+1.m中各元素满足堆的定义，本算法调整中各元素满足堆的定义，本算法调整Ri使序列使序列 Ri.m中各元素满足堆的性质中各元素满足堆的性质 R0=Ri;暂存暂存 for(j=2*i;j=m;j*=2)if(jm&Rj.keyRj+l.key)j+;沿大者（右）方向筛沿大者（右）方向筛选选 if(R0.key0;i-)把把R1.n建成大顶堆建成大顶堆 Sift(R,i,n);for(i=n;i1;i-)输出并调堆输出并调堆 R1Ri;Sift(R,1,i-1);将将R1.i-1重新调整为大顶堆重新调整为大顶堆 forHeapSort 堆排序的堆排序的时间复杂度时间复杂度为为O（nl
45、og2n）652023-9-465时间复杂度：最坏情况下时间复杂度：最坏情况下T(n)=O(nlogn)建初始堆时间建初始堆时间：调用调用SIFT 过程过程 n/2 次，每次以次，每次以Ri为根的子为根的子树调整为堆。具有树调整为堆。具有n个结点的完全二叉树深度是个结点的完全二叉树深度是h=logn +1,第第i层结点个数至多为层结点个数至多为 2 i-1。SIFT对深度为对深度为k的完全二叉树进行比较的完全二叉树进行比较的关键字次数至多为的关键字次数至多为2(k-1)，因此比较总次数不超过因此比较总次数不超过C1(n)2 i-1*2(h-1)=2 h-1+2 h-2*2+2 h-3*3+2*
46、(h-1)=2*2(log 2n)+1=4n重新建堆时间：重新建堆时间：排序过程中重新建堆比较总次数不超过排序过程中重新建堆比较总次数不超过C2(n)=2*(log n-1 +log n-2+log 2 )=1;i=i/2)v if(R0.keyRi.key)v Rj=Ri;j=i;v else break;v Rj=R0;v siftv(2)void HeapBuilder(RecType R,int n)v for(i=2;i=n;i+)sift(R,i);702023-9-470归并排序 基本思想基本思想：将具有将具有n个待排序记录的序列看个待排序记录的序列看成是成是n个长度为个长度为1
47、的有序序列，进行两两归并，的有序序列，进行两两归并，得到得到n/2 个长度为个长度为2的有序序列，再进行两两的有序序列，再进行两两归并，得到归并，得到n/4 个长度为个长度为4的有序序列，如此的有序序列，如此重复，直至得到一个长度为重复，直至得到一个长度为n的有序序列为止的有序序列为止 712023-9-471归并排序示例二趟归并排序后二趟归并排序后：33 51 62 96 117 28 87 初始关键字序列初始关键字序列：51 33 62 96 87 17 28 一趟归并排序后一趟归并排序后：33 51 62 96 117 87 28 三趟归并排序后三趟归并排序后：17 28 33 51 6
48、2 87 96 722023-9-472一趟归并排序算法void Merge(RecType R,RecType R1,int i,int l,int h)v 将有序的将有序的Ri.l和和Rl+1.h归并为有序的归并为有序的R1i.hv for(j=l+1,k=i;i=l&j=h;k+)v R中记录由小到大地并入中记录由小到大地并入R1v if(Ri.key=Rj.key)R1k=Ri+;v else R1k=Rj+;v if(i=l)R1k.h=Ri.l;将剩余的将剩余的Ri.l复制到复制到R1v if(j=h)R1k.h=Rj.h;将剩余的将剩余的Rj.h复制到复制到R1vMerge732
49、023-9-473归并排序算法vvoid Msort(RecType R,RecType R1,int s,int t)v 将将Rs.t进行进行2-路归并排序为路归并排序为R1s.tv if(s=t)R1s=Rs;v elsev m=(s+t)/2;将将Rs.t平分为平分为Rs.m和和Rm+1.tv Msort(R,R2,s,m);递归地将递归地将Rs.m归并为有序的归并为有序的R2s.mv Msort(R,R2,m+1,t);递归地递归地Rm+1.t归并为有序的归并为有序的R2m+1.tv Merge(R2,R1,s,m,t);将将R2s.m和和R2m+1.t归并到归并到R1s.tv ifv
50、MSort742023-9-474归并排序算法vvoid MergeSort(RecType R,int n)v 对记录序列对记录序列R1.n作作2-路归并排序。路归并排序。v MSort(R,R,1,n);vMergeSortv归并排序的设计复杂度为归并排序的设计复杂度为O(nlogn)752023-9-475自测题自测题 v 10.若数据元素序列若数据元素序列11,12,13,7,8,9,23,4,5是采是采用下列排序方法之一得到的第二趟排序后的结果，用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是则该排序算法只能是vA.起泡排序起泡排序 vB.插入排序插入排序 vC.选择排
