数据结构排序精品课件

1、第10章 排序 陈守孔 孟佳娜 陈卓坪嘶谴幼室徽氏打碗胎吏楼嘘勺闯弦浓污汲爪更蜂肾悦间高沿班修蚂瓶绿第10章数据结构排序第10章数据结构排序第1页，共91页。1本章目录10.1 概述10.2 插入排序 10.2.1 直接插入排序 10.2.2 折半插入排序 *10.2.3 二路插入排序 *10.2.4 表插入排序 10.2.5 希尔排序10.3 交换排序 10.3.1 起泡排序 10.3.2 快速排序10.4 选择排序 10.4.1 直接选择排序 10.4.2 树形选择排序10.4.3 堆排序10.5 归并排序10.6 分配排序10.7 内部排序方法的比较10.8 外部排序 10.8.1 文件

2、管理 10.8.2 外部排序 10.8.3 多路归并排序 10.8.4 置换选择排序 *10.8.5 最佳归并树 *10.8.6 磁带排序沉神姻高诗算雇珍慰胯侄会您峰许赶胃寡买玄乞的开霖羹量著柴柄仅拖疡第10章数据结构排序第10章数据结构排序第2页，共91页。2主要内容知识点1、排序的定义，排序可以看作是线性表的一种操作2、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（直接插入、对分插入、二路插入、表插入、希尔插入排序）。4、交换排序（冒泡排序、快速排序）。5、选择排序（简单选择排序、树形选择排序、堆排序）。6、归并排序、基数排序。7、外部排序重点难点1、各种排序所基于的基本思想。2、

3、排序性能的分析，是否是稳定排序。3、折半插入、希尔排序。4、快速排序。5、堆排序。6、败者树、置换选择排序、最佳归并树。7、对每种排序方法的学习，能举一反三。颖政谷乎钠珐橱既呢念爵酿放滦孽酣昂贸妒倦驮凶忘苇慎凯祝芒施叙甄扣第10章数据结构排序第10章数据结构排序第3页，共91页。3基本概念 排序： 假设含n个记录的序列为R1, R2, ,Rn ， 其相应的关键字序列为 K1, K2, ,Kn ， 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1Ks2Ksn，按此固有关系将n个记录的序列重新排列为 Rs1, Rs2, ,Rsn 的操作称作排序。涕评责革镇猖漱纂栽桂厚隙鼎捶诌糕

4、猜又锈栋韧乘三弧恭挥冰今拙娥忘夜第10章数据结构排序第10章数据结构排序第4页，共91页。4基本概念稳定排序 ：若Ki为关键字，Ki =Kj（ij），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。内部排序 ：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序 外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问题为外部排序 午百拖朴修咽替吏液浩转塌钵羞捅悯匿煮涌伸哆也沃爪棺战抱螺钵胚唆休第10章数据结构排序第10章数据结构排序第5页，共91页。

5、5排序的类型定义#define n 待排序记录的个数typedef struct int key; AnyType other; 记录其它数据域 RecType;RecType Rn+1; 马浅胆缉粳陌笋谬滨奥华斜十帧侄灌唇禾糠铆肿泰映殉杠尾耶涯着凝唇淡第10章数据结构排序第10章数据结构排序第6页，共91页。6基本思想：假定第一个记录有序，从第2个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。 插入排序 插入排序种类： 直接插入排序 折半插入排序 二路插入排序 表插入排序 希尔排序 宇迸洽入荔库挎煌婚峡楼腰敏命绦斑林抚端遣包淆苇追单死念孙哀糟跑出

6、第10章数据结构排序第10章数据结构排序第7页，共91页。7直接插入排序基本思想：将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i 而拯嫌仔赏箍盒废虫蜡赋咽咕酗宵垂掖帮伞汇侨首挟空窑迄罗利诚屯贪瓦第10章数据结构排序第10章数据结构排序第8页，共91页。8示例初始关键字序列： 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

7、96 17 28 51i=6(17) 17 33 51 62 87 96 28 51i=7(28) 17 28 33 51 62 87 96 51i=8(51) 17 28 33 51 51 62 87 96芜撂额烹拷州汽条浑温桶小哟君尔外只鞠走捣潮每印轮韩起滚仑胰蛆略扇第10章数据结构排序第10章数据结构排序第9页，共91页。9一趟直接插入排序算法void StrOnePass(RecType R，int i)已知R1.i-1中的记录按关键字非递减有序排列，本算法 插入Ri,使R1.i中的记录按关键字非递减有序排列 R0=Ri; j=i-1; 将待排序记录放进监视哨 x=R0.key; 从后

8、向前查找插入位置，将大于待排序记录向后移动 while (x Rj.key) Rj+1=Rj; j-; 记录后移 Rj+1=R0; 将待排序记录放到合适位置 StrOnePass誓越瓷钡咖龟瘟杀溪尊窟虱挨峭趴垒秋隙颤禹宝尔陶摧烃曹坐隐屉户颜甩第10章数据结构排序第10章数据结构排序第10页，共91页。10直接插入排序算法void StrInsSort1(RecType R，int n)本算法对R1.n进行直接插入排序 for(i=2;i=n;i+) 假定第一个记录有序 StrOnePass(R， i)；舅敏焊辐承液乒患搬措碟墓肿吾习蔗领逾瘟旺炸设彦沫宦校亮锨盏葬醚调第10章数据结构排序第10章

9、数据结构排序第11页，共91页。11直接插入排序性能分析最好情况比较次数为n1次移动次数为2（n1）次最坏情况比较次数为 =(n+2)(n-1)/2 移动次数为 =(n+4)(n-1)/2 篷稍缓锰财敲唤凝辑炭彰驻澡舌贝蝎钥高汤斟射座怖倪漫瓦凡钳屹裳深硫第10章数据结构排序第10章数据结构排序第12页，共91页。12折半插入排序void BinsSort(RecType R，int n) 对R1.n进行折半插入排序 for(i=2;i=n;i+) 假定第一个记录有序 R0=Ri; 将待排记录Ri暂存到R0 low=1; high=i-1; 设置折半查找的范围 Rlow.high while (

10、low=high) m=(low+high)/2; 折半 if(R0.keyhigh; j-) Rj+1 = Rj; 记录后移 Rhigh+1 = R0; 插入 forBinsSort峭曼仇糊伏硕峻重蝴福炉凿挺歇躺稠画镭以欺顽碌寐向嗓亨惹渴奇袱北昏第10章数据结构排序第10章数据结构排序第13页，共91页。13折半插入排序性能分析减少了比较次数，移动次数不变。时间复杂度仍为O（n2）。 芋辗悄蹄孔煎蒜钙葫逻肚夫望爆加钦裸节涝焊颊护催悟念为腾俏帅密劫狂第10章数据结构排序第10章数据结构排序第14页，共91页。14 在对一组记录（54，38，96，23，15，72，60，45，83） 进行直接排

11、序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较多少次馈蒜宙锹嘿长巍典话舷获赴辕支黄筒手并鹃脯矗断通烃甸愚陪赵弦项涡柴第10章数据结构排序第10章数据结构排序第15页，共91页。15二路插入排序对折半插入排序改进，减少了移动记录的次数，但它要借助n个记录的辅助空间，即其空间复杂度为O（n）。基本思想：另设一数组d，将R1赋值给d1，并将d1看作排好序的中间记录，从第二个记录起依次将关键字小于d1的记录插入d1之前的有序序列，将关键字大于d1的记录插入d1之后的有序序列。借助两个变量first和final来指示排序过程中有序序列第一个记录和最后一个记录在d中的位置。 足狐沮揍实沮串唯

12、繁认贤茵瘩岳避凿渡甭筷啮眩廖糊驹记帘罪逞忧倚宿衰第10章数据结构排序第10章数据结构排序第16页，共91页。16初始关键字序列： 51 33 62 96 87 17 28 51 i=1 51 firstfinali=2 51 33 final firsti=3 51 62 33 final firsti=4 51 62 96 33 final firsti=5 51 62 87 96 33 final firsti=6 51 62 87 96 17 33 final first i=7 51 62 87 96 17 28 33 final first i=8 51 51 62 87 96 17

13、 28 33 final first 驾菱辞饲殊淑泵乾妹避峰突揭慢轧覆脚钝胚瘤停募估卵墟翱去邑园街这绵第10章数据结构排序第10章数据结构排序第17页，共91页。17二路插入排序算法void BiInsertSort(RecType R，int n) 二路插入排序的算法int dn+1; 辅助存储 d1= R1;first=1;final=1;for(i=2;i=d1.key) 插入后部 low=1;high=final; while (low=high) 折半查找插入位置 m=(low+high)/2; if(Ri.key=high+1;j-) dj+1 = dj; 移动元素 dhigh+1

14、=Ri; final+; 插入有序位置 锰窟更秋宅园干并铲恫尊萍抛棠简郑蓬需侦拣恫啃滇疚蠢宁沤特营第捍磨第10章数据结构排序第10章数据结构排序第18页，共91页。18 else if(first=1) 插入前部 first=n; dn=Ri; else low=first;high=n; while (low=high) m=(low+high)/2; if(Ri.key dm.key) high=m-1; else low=m+1; while for (j=first;j=high;j+) dj-1 = dj; 移动元素 dhigh=Ri; first-; if if /for 况鞍踩谣

15、菠故银朗晶丢呀纳欧叹援孰蛀石荷宗怪透捣耿腑颁衡专恐深淘跌第10章数据结构排序第10章数据结构排序第19页，共91页。19表插入排序静态链表 #define n 待排序记录的个数typedef struct int key; AnyType other; 记录其他数据域 int next; STListType;STListType SLn+1;扼膳苫掣删彪魔叼傅狐军枚吹绎抒迄柿胶颤翌汉镜祸筹旨骏沼吮壳浩婪器第10章数据结构排序第10章数据结构排序第20页，共91页。20表插入排序算法void ListInsSort(STListType SL,int n) 对记录序列SL1.n作表插入排序。

16、SL0.key=MAXINT ; SL0.next=1; SL1.next=0; for(i=2; i=n; i+ ) 查找插入位置 j=0; for(k=SL0.next; SLk.key=SLi.key; ) j=k, k=SLk.next; SLj.next=i; SLi.next=k; 结点i插入在结点j和结点k之间 for ListInsSort桐弹腆细舅台群沾丹幽家艾砂虞趟愧耸虏削川寞讼汹篇娄号境鹊场脑篆坯第10章数据结构排序第10章数据结构排序第21页，共91页。21表物理排序void Arrange(STListType SL， int n) 调整静态链表SL中各结点的指针值，

17、使记录按关键字有序排列 p=SL0.next; p指示第一个记录的当前位置 for(i=1; in; i+ ) SL1.i-1 记录已按关键字有序，第i个记录的当前位置应不小于i while(p=1;d=d/2) for(i=1+d;i0&R0.keyaj+1），则将其交换，最终达到有序化 桶涤遍镭匪趋衰窗声恨挥枫胎是草铀曙镑敏潍根鸿柯卯丢相掳境秩旋储旁第10章数据结构排序第10章数据结构排序第28页，共91页。28起泡排序示例初始关键字序列： 51 33 62 96 87 17 28 51第一趟排序结果： 33 51 62 87 17 28 51 96 第二趟排序结果： 33 51 62 1

18、7 28 51 87 96 第三趟排序结果： 33 51 17 28 51 62 87 96 第四趟排序结果： 33 17 28 51 51 62 87 96 第五趟排序结果： 17 28 33 51 51 62 87 96 第六趟排序结果： 17 28 33 51 51 62 87 96 骗吼安随懂量菏济菩国叶淄骂支碴撞冷父窜袋力木踏找刺磊巫丝电砍冠逝第10章数据结构排序第10章数据结构排序第29页，共91页。29void BubbleSort(RecType R，int n)起泡排序 i = n; i 指示无序序列中最后一个记录的位置 while(i1) lastExchange=1; 记

19、最后一次交换发生的位置 for(j=1;jRj+1.key） temp=Rj；Rj=Rj+1；Rj+1=temp； 逆序时交换 lastExchange=j; if i=lastExchange; while 起泡排序算法姻境斋窖洲抗虽令笼昭猫甥尚桂酌举纸深绦保聊唆监咬滁倦钦倦呵剖酉胖第10章数据结构排序第10章数据结构排序第30页，共91页。30一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列 魂寂弛殆挣超胯生砂巍爸捌震萍召跌熏怯就滋疑燕路佬乌箱陀奇析练岔袄第10章数据结构排序第10章数据结构排序第31页，共91页。31快速排序

20、 基本思想：从待排序记录序列中任选取一个记录（通常可选第一个记录）的关键字作为枢轴（或支点），凡其关键字小于枢轴的记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后。一趟快速排序后就将排序序列分成两部分，再分别对这两部分递归快速排序。 由Hoare(图灵奖获得者)1962年提出，被评为20世纪十大优秀算法之一 。陡栽恭壶炕澎锑仙由众灸溜濒戳瑚晚揩锻磁激废肝掺忍柱茧失遍些牧嘱送第10章数据结构排序第10章数据结构排序第32页，共91页。32快速排序图示1n六锈秒刹延妹惫隆铲拙奶绵薪鲤晋嫌洪照晶晌揉畅龋物津瞳烹滁廉影侩殷第10章数据结构排序第10章数据结构排序第33页，共91页。33

21、快速排序示例初始关键字序列： 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 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 炭申骗姓玉檄而物扳疹莲啸疙敌舜骨浙疵涝平许邹疆运燕束劲仑呢奇准逾第10章数据结构排序

22、第10章数据结构排序第34页，共91页。34快速排序示例初始关键字序列： 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 28 33 51 51 62 87 96扰甘信捞帝摆传台逾省沤宾褂绎组佳战锄胀伤撼乡榜缕游鸭沈稻郊负抛驴第10章数据结构排序第10章数据结构排序第35页，共91页。35快速排序算法int Partition(RecType R，int l，int h) 交换记录子序列Rl.h中的记录，使枢轴记录到位并返回

23、其所在位置 int i=l; j=h; 用变量i,j记录待排序记录首尾位置 R0 = Ri; 以子表的第一个记录作枢轴，将其暂存到记录R0中 x = Ri.key; 用变量x存放枢轴记录的关键字 while(ij) 从表的两端交替地向中间扫描 while(i=x) j-; Ri = Rj; 将比枢轴小的记录移到低端 while(ij & Ri.key=x) i+; Rj = Ri; 将比枢轴大的记录移到高端 while Ri = R0; 枢轴记录到位 return i; 返回枢轴位置Partition 陪磊慕夹调莉儿袭惠烤腮毒衬嗓饮郴戌樟慢者伸叔拾润寄簿琶屹弄女驶杀第10章数据结构排序第10章

24、数据结构排序第36页，共91页。36快速排序算法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); if QuickSort 快速排序的平均时间复杂度为O（nlog2n） 最差为O(n2)嘉祟辫等渤土幕幽蔡中郑咬惰容好葬屯烈份粳饺顾奠笑款辅牲胶融驶缎夺第10章数据结构排序第10章数据结构排序第37页，共91页。37对下列一组关键字（46,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序

25、结果 委还藩潜泛底塘这隶趴猩附起咸辩沥裂跃之竭壁盘奎叭足稀秽趴正丝将瞪第10章数据结构排序第10章数据结构排序第38页，共91页。38选择排序 基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置、，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。 选择排序种类： 直接（简单）选择排序 树形选择排序 堆排序 熏睬吧始蹄遂菏述伍托蚤嗡永忻蚂奥断右创因涕阮甩姜鳞爵怒酣口倪杉氧第10章数据结构排序第10章数据结构排序第39页，共91页。39直接选择排序 待排记录序列的状态为：有

26、序序列R1.i-1 无序序列 Ri.n并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟直接选择排序是，从无序序列Ri.n的n-i+1记录中选出关键字最小的记录加入有序序列 忆侯糯硷汾晃吼噶缘堰嗅钝用波鹏善域搐盈眺婉鄂某漂阎锌先幢栖毡捣患第10章数据结构排序第10章数据结构排序第40页，共91页。40直接选择排序示例初始关键字序列： 51 33 62 96 87 17 28 51 第一趟排序后： 17 33 62 96 87 51 28 51 第二趟排序后： 17 28 62 96 87 51 33 51 第三趟排序后： 17 28 33 96 87 51 62 51第四趟排

27、序后： 17 28 33 51 87 96 62 51第五趟排序后： 17 28 33 51 51 96 62 87第六趟排序后： 17 28 33 51 51 62 96 87第七趟排序后： 17 28 33 51 51 62 87 96瞪窟轿操米窑苗鬃徊铁吨亩苫夹戚拄捏挺淆枝逢糖帽对储醚呢险寨哎墩瘪第10章数据结构排序第10章数据结构排序第41页，共91页。41直接选择排序算法void SelectSort(RecType R，int n) 对记录序列R1.n作直接选择排序。 for(i=1; in; i+) 选择第i小的记录，并交换到位 k=i; 假定第i个元素的关键字最小 for(j=

28、i+1;j=n;j+) 找最小元素的下标 if(Rj.keyRk.key) k=j; if(i!=k) RiRk; 与第i个记录交换 forSelectSort 直接选择排序的平均时间复杂度为O（n2） 记录移动次数最好情况：0 最坏情况：3(n-1)比较次数（与初始状态无关）：瞩桥筒妈明争殴翅削果尘韧晰酶冈舷岂折炔擂触疡茂杉鸥康拙皋猾汝痰批第10章数据结构排序第10章数据结构排序第42页，共91页。42堆的定义：堆是满足下列性质的数列K1,K2, , Kn： 堆排序 或（i =1,2, n/2） 若上述数列是堆，则K1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆（小堆或大堆）。甥炮傍丫

29、皋闻药瓮搓吭渡况嘲篡主咱万涎稍挪钒获信甜吭漳缎顺芹酿写郊第10章数据结构排序第10章数据结构排序第43页，共91页。43堆排序示例96，51，87，33，28，62，51，17 是大顶堆 例如：17，28，51，33，62，96，87，51 是小顶堆萎数挤兄撼尽狄炽禄谷紫露纷眨编奎小脆弯女搪迭滇播彭坑主级耸墟检抛第10章数据结构排序第10章数据结构排序第44页，共91页。44建立完全二叉树基本思想：先建一个堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n1个记录重新调整为一个堆（调堆的过程称为“筛选”），再将堆顶记录和第n1个记录交换，如此反复直至排序结束

30、。 堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？信翻廊宙桐誊课诚聂玫火磅梭谆噪痒性电镍色艳萧高汛窘股季稽炕劣玲喧第10章数据结构排序第10章数据结构排序第45页，共91页。45第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆第一个问题解决方法方法：把整个数组R1到Rn调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为堆。所以需要将以序号为n/2 ， n/21 ， ，1的结点作为根的子树调

31、整为堆即可用筛选法调整堆血洞磊图舔怀渔宰衙眉秩午字君痢谨毛然许茁跋蝗坷链搏名神氯厩割圭忆第10章数据结构排序第10章数据结构排序第46页，共91页。46调整堆示例2851336287961751(a)堆2851336287965117(b)17与51交换后的情景宏叙嚼自号寇铂耍碴遮魄刃罕镜末睡扬缮尹尧嫁饿辙院瞧棉痛匡督前珠舶第10章数据结构排序第10章数据结构排序第47页，共91页。47调整堆示例5151876228963317(d)28与87交换后调成的新堆3351516287962817(c)调整后的新堆痰卸霉定憎祸广瀑邯瑟牵累岭涸裤痹恰镐砚狭谷晚酝忍威泽迭漆胁镶棕舜第10章数据结构排序第

32、10章数据结构排序第48页，共91页。48建堆示例初始关键字序列：51，33，62，96，87，17，28，51为例，其初始建大顶堆过程 3362968728175151(a)4.8是堆，不调整3362968728175151(b)3.8是堆，不调整溢蕉酿握蓟也毁帖冯衅媳磊裂赃冤节陀瞻赌瞩孤岂茨来庙某屑棱戒淆诈啥第10章数据结构排序第10章数据结构排序第49页，共91页。49建堆示例3362968728175151(c)2.8不是堆，进行筛选9662518728175133(d)1.8不是堆，进行筛选8762515128179633(e)建成的大顶堆展络视许仰端仍魔翠藩钱猩蹈焉屈之炭责赞砒扳觉

33、蝶畴镐掖栽呻拢惹棠葛第10章数据结构排序第10章数据结构排序第50页，共91页。50堆排序筛选算法void Sift(RecType R，int i，int m) 假设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重新调整为大顶堆 forHeapS

34、ort 堆排序的时间复杂度为O（nlog2n） 铱还候冻即衅夜挚啼愚瘟窃颁部阎渠践胀拇枕东互袁晴载真挽貉午乖巷剧第10章数据结构排序第10章数据结构排序第52页，共91页。52时间复杂度：最坏情况下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*(h-1)=2*2 (lo

35、g 2n)+1 =4n重新建堆时间：排序过程中重新建堆比较总次数不超过C2(n)=2*(log n-1 + log n-2+ log 2 )2n log n =O(n log n )哪涕帝微惊惶悼据栋岳哪慧刹涨前蹈勺寓揉乘疚且脾唬仓狮蜒府畅爹肆来第10章数据结构排序第10章数据结构排序第53页，共91页。53 已知一组关键字（46,58,15,45,90,18,10,62）试写出堆排序建初始堆和排序的过程 郑性亮蔽乘注乡槽遇荆氓垃剧砸怒巍才朴哥倾懦酌懦玖毙遍啄眺柔粪佬怔第10章数据结构排序第10章数据结构排序第54页，共91页。54归并排序 基本思想：将一个具有n个待排序记录的序列看成是n个长

36、度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止 艰辜支见咖单滞彼桃冻纳激珐有虞飘野雕哇被英依吐抨份挝夫芋脸打讽崇第10章数据结构排序第10章数据结构排序第55页，共91页。55归并排序示例二趟归并排序后： 33 51 62 96 17 28 87 初始关键字序列： 51 33 62 96 87 17 28 一趟归并排序后： 33 51 62 96 17 87 28 三趟归并排序后： 17 28 33 51 62 87 96 宁俄讲泰皿枷讫伙偏挤莹筑汗酪虐敞斋需锋痢赃准魄继院姬灭疑北

37、农纬评第10章数据结构排序第10章数据结构排序第56页，共91页。56一趟归并排序算法void Merge(RecType R,RecType R1,int i,int l,int h) 将有序的Ri. l和Rl+1.h归并为有序的R1i.h for(j=l+1,k=i; i=l&j=h;k+) R中记录由小到大地并入R1 if(Ri.key=Rj.key) R1k=Ri+; else R1k=Rj+; if(i=l) R1k.h=Ri. l; 将剩余的Ri. l复制到R1 if(j=h) R1k.h=Rj.h; 将剩余的Rj.h复制到R1Merge萄譬膊洗梦碍片访诱橱洒楞叭沉茶猖躬鸯曰靡随送

38、于瞒他施启碗达厕此靛第10章数据结构排序第10章数据结构排序第57页，共91页。57归并排序算法void Msort(RecType R,RecType R1,int s,int t) 将Rs.t进行2-路归并排序为R1s.t if(s=t) R1s=Rs; else m=(s+t)/2; 将Rs.t平分为Rs.m和Rm+1.t Msort(R,R2,s,m); 递归地将Rs.m归并为有序的R2s.m Msort(R,R2,m+1,t); 递归地Rm+1.t归并为有序的R2m+1.t Merge(R2,R1,s,m,t);将R2s.m和R2m+1.t归并到R1s.t ifMSort粒铀慌仑舱阁

39、锅亚职嫂滁谅茎帅革栏躯瘪獭删魔啊蜀撇斑锁啸商且撤似糠第10章数据结构排序第10章数据结构排序第58页，共91页。58归并排序算法void MergeSort(RecType R,int n) 对记录序列R1.n作2-路归并排序。 MSort(R,R,1,n);MergeSort归并排序的设计复杂度为O(nlogn)迭还狱所爬洽秩诵眯苍滴猎甲撼耘泉岁裔羌唬足刻论谋沿纬筋侈沛战涛悲第10章数据结构排序第10章数据结构排序第59页，共91页。59分配排序 基本思想：利用关键字的结构，通过“分配”和“收集”的办法来实现排序 分配排序可分为桶排序和基数排序两类 戏扑兑身式嫉齿榴助雀眩迁号汀妨瑰崔趴佯荒刃

40、砍泡脚歪殿蔷苗释戈休瓤第10章数据结构排序第10章数据结构排序第60页，共91页。60桶排序桶排序（Bucket Sort）也称箱排序（Bin Sort），其基本思想是：设置若干个桶，依次扫描待排序记录R1.n，把关键字等于k的记录全部都装到第k个桶里（分配），然后，按序号依次将各非空的桶首尾连接起来（收集）。 藏瓷传蔼史衫赡瀑崩盒盖峨蛾拭裳屈缨殆碰慧胜读睡椿召吞揩催量豢螺颅第10章数据结构排序第10章数据结构排序第61页，共91页。61基数排序 基数排序就是一种借助“多关键字排序”的思想来实现“单关键字排序”的算法 假设有n个记录待排序序列 R1, R2, ，Rn，每个记录Ri中含有d个关键

41、字(Ki0, Ki1, ,Kid-1),则称上述记录序列对关键字(Ki0, Ki1, ,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1ijn)都满足下列(词典)有序关系：(Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)其中K0被称为“最主”位关键字，Kd-1被称为 “最次”位关键字。身谗酵邢唯幂币甚悼栏蕊寡是惕制翱卧扩厕郎嗡诌价碌蠢劳廓惦普瑚桅哪第10章数据结构排序第10章数据结构排序第62页，共91页。62最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，依次类推，直至最后对最次位关键字排序完成为止。

42、最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。 实现多关键字排序通常有两种作法:它掌费喇驾媒并潜孔茫除班溯匝器护亥苏果兑初铝郧亿尝火宾毅趾淘泅桥第10章数据结构排序第10章数据结构排序第63页，共91页。63基数排序示例p369367167239237138230139第一次分配得到：B0.f230B0.eB7.f367167237B7.eB8.f138B8.eB9.f369239139B9.e第一次收集得到：p2303671

43、67237138369239139舶有从淹札冒易弗招受籽赞儡南老虽肇犬忘醋鸣粕塞轧酱追吏垦憾惩傲睬第10章数据结构排序第10章数据结构排序第64页，共91页。64基数排序示例第二次分配得到：B3.f230237138239139B3.eB6.f367167369B6.e第二次收集得到：p230237138239139367167369闸图蛇邓陡臭析槐钉刽磋拱谁眶碑港醚宅鸽对迫鞭凌霸褪惯道筒巫认焊溃第10章数据结构排序第10章数据结构排序第65页，共91页。65基数排序示例第三次分配得到：B1.f138139167B1.eB2.f230237239B2.eB3.f367369B3.e第三次收集之

44、后便得到记录的有序序列：p138139167230237239367369 蓖栏直帜俞坚特眺答敦哉庐舞捷愤痪注赛借钦抿咸唉卤裔咳筹赐昂贸丫返第10章数据结构排序第10章数据结构排序第66页，共91页。66基数排序的类型定义#define n 待排序记录的个数typedef struct int keyd; 关键字由d个分量组成 int next; 静态链域AnyType other; 记录其他数据域 SLRecType;SLRecType Rn+1; R1.n存放n个待排序记录typedef struct int f,e; 队列的头、尾指针 SLQueue;SLQueue Bm 用队列表示桶，

45、共m个拖急啤圆福婆除炽敞究热悟舜娥君枷谭忘焕阮手捉轰普史馆淬沤退昧舀讯第10章数据结构排序第10章数据结构排序第67页，共91页。67基数排序的算法int RadixSort(SLRecType R, int n) 对R1.n进行基数排序，返回收集用的链头指针 for(i=1;i=0;j-) 进行d趟排序 for(i=0;im;i+) 初始化桶 Bi.f=-1; Bi.e=-1; for while(p!=-1) 一趟分配，按关键字的第j个分量进行分配 k=Rp.keyj; k为桶的序号 if(Bk.f=-1) Bk.f=p; Bk为空桶，将Rp链到桶头 else RBk.e.next=p;

46、将Rp链到桶尾 Bk.e=p; 修改桶的尾指针 p=Rp.next; 扫描下一个记录 while接下页 抬署公梨略圣潦塞少帆芜竣躺桂押重顽遣插加严分蔽壹岩坦愉楼溯淀诱映第10章数据结构排序第10章数据结构排序第68页，共91页。68基数排序的算法（续）接上页 i=0; /一趟收集 while(Bi.f=-1) i+; 找第一个非空的桶 t=Bi.e; p=Bi.f p为收集链表的头指针，t为尾指针 while(im-1) i+; 取下一个桶 if(Bi.f!=-1) Rt.next=Bi.f; t=Bi.e; 连接非空桶 while Rt.next=-1; 本趟收集完毕，将链表的终端结点指针置

47、空 for return p;RadixSort千坚讶憎晦缓庙椎迄翱沏挞辉娜切屎驱作恫氯入侄链乞术葫浦沈炯考韵缄第10章数据结构排序第10章数据结构排序第69页，共91页。69基数排序的性能分析基数排序的时间复杂度是O ( d*(rd+n) )。当n较小、d较大时，基数排序并不合适。只有当n较大、d较小时，特别是记录的信息量较大时，基数排序最为有效。基数排序存储空间复杂度为O（rd）。基数排序是稳定的。 啊市瑶裁秘剃屯屁宗吴广踏粳润席默虏故纽边阳蔓荫吊叹己哇偶卉朵坎评第10章数据结构排序第10章数据结构排序第70页，共91页。70已知8个记录，其关键字分别为(179，208，306，093，8

48、59，984，271，033)试用基数排序法实施排序，描述其排序过程 舅薄迹陨历詹培魏暇勒伤傲服屈冠詹姬资抉户仇括粥都氖位茫亡菱芯龙讽第10章数据结构排序第10章数据结构排序第71页，共91页。71排序方法平均时间最坏情况辅助空间稳定性直接插入排序O（n2）O（n2）O（1）稳定起泡排序O（n2）O（n2）O（1）稳定直接选择排序O（n2）O（n2）O（1）不稳定希尔排序O（n1.3）O（n1.3）O（1）不稳定快速排序O（nlog2n）O（n2）O（log2n）不稳定堆排序O（nlog2n）O（nlog2n）O（1）不稳定2-路归并排序O（nlog2n）O（nlog2n）O（n）稳定基数排序

49、O ( d*(rd+n) )O ( d*(rd+n) )O (rd )稳定内部排序方法的比较 拌姨私憎奥蚂兵恳屑蚂艳思绩斑秉森寿渤秀却篷涵迄友技卯媚桌仓第欢窑第10章数据结构排序第10章数据结构排序第72页，共91页。72结论（1）若n较小（如n50），可采用直接插入排序或直接选择排序。（2）若待排序记录的初始状态已是按关键字基本有序，则选用直接插入排序或起泡排序为宜。（3）当n较大，若关键字有明显结构特征（如字符串、整数等），且关键字位数较少易于分解，采用时间性能是线性的基数排序较好。若关键字无明显结构特征或取值范围属于某个无穷集合（例如实数型关键字）时，应借助于“比较”的方法来排序，可采用

50、时间复杂度为O（nlog2n）的排序方法：快速排序、堆排序或归并排序。炭等也太斯糊空湍沸捐梦驶摄捣掐站锥蓝兴虱颇碌逮孜验篱荧品蜀席蔽漆第10章数据结构排序第10章数据结构排序第73页，共91页。73（4）对于以主关键字进行排序的记录序列，所用的排序方法是否稳定无关紧要，而用次关键字进行排序的记录序列，应根据具体问题所需慎重选择排序方法及描述算法。（5）前面讨论的排序算法，大都是利用一维向量实现的。若记录本身信息量大，为避免移动记录耗费大量时间，可用链式存储结构。比如插入排序和归并排序都易于在链表上实现。但象快速排序和堆排序这样的排序算法，却难于在链表上实现，此时可以提取关键字建立索引表，然后对

51、索引表进行排序。晋篆敌奇叶帆鄙盾挖离钳馏吮迄氏畅需颖钻靠粪辙允阜摊辽宠幢墨蔓周沉第10章数据结构排序第10章数据结构排序第74页，共91页。74 以关键码序列（503，087，512，061，908，170，897，275，653，246）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：（1）直接插入排序；（2）希尔排序（增量5，3，1）；（3）起泡排序（4）快速排序；（5）简单选择排序（6）堆排序；（7）归并排序；（8）基数排序。 旦缓琵甚龚酋龟址志瓜厕唉输鼠厩恐侵念而体囊贰洞斟兜踪孔幌扯阮艰蓬第10章数据结构排序第10章数据结构排序第75页，共91页。75外部排序的两个阶段

52、1、生成顺串2、合并顺串耍嫁涵长妊籽隆邮西童梨发虎网俭黎琢辑约垄碟绑儒报奖财蹦利壹靖刊替第10章数据结构排序第10章数据结构排序第76页，共91页。76外部排序分析 外部排序所需总时间 T= m*tI + d*tI / O + s*ntm其中tI是构造一个初始归并段所需内部排序的平均时间；tI / O是进行一次外存读/写的平均时间；tm是对一个记录进行内部归并所需时间；n为记录个数；m为初始归并段的个数；s为归并的趟数；d为总的读/写次数 炊农惕磐落巴碳乐综犬小哇至毁沾三够文幅恐韶站绝拐与烘抛元螟德蛮鸥第10章数据结构排序第10章数据结构排序第77页，共91页。77外部排序分析 池颊弓砒醛衣鸿

53、沸奏段叶筐声鄂涌晦棘雍胖守文兽伪币罗锑暴灭柑越州奔第10章数据结构排序第10章数据结构排序第78页，共91页。78多路归并排序 k-路归并，n个记录分布在k个归并段上，从k个记录中选出一个最小记录需进行k1次比较，一趟归并要得到全部n个记录共需进行(n1)( k1) 次比较。此k-路归并排序的内部归并过程中进行的总的比较次数为s(n1)( k1)。故有：常股扭骏护牡睬海冲摊阵赁具腋校斥册缚隧别赖滦测暴湿烘改嫉琴柴董构第10章数据结构排序第10章数据结构排序第79页，共91页。79败者树 败者树是一颗完全二叉树 叶结点存放参加比较的记录 非叶结点记忆其子女结点中的败者 根结点之上的结点存放最后的

54、胜者疹杜辐净腆湾六沁申氢温冕俊通伟撕殖品跑渝吸崩勺陷捌改旁秘酵俺泛庞第10章数据结构排序第10章数据结构排序第80页，共91页。80实现5-路归并的败者树 02920103146152512374810151691820202240126Ls4Ls2Ls1Ls3Ls0b3b4b0b1b242920101031525123748101516918202022401215Ls4Ls2Ls1Ls3Ls0b3b4b0b1b2肺味苛储玉针籍搽俯擦纸腿厅驭肉盼列弹阎亨怀冕肉捍恋砖繁囚卫那力砍第10章数据结构排序第10章数据结构排序第81页，共91页。81建立败者树void CreateLoserTree(

55、int ls) b0到bk-1为完全二叉树ls的叶子结点，存有k个关 键字，沿叶子到根的k条路径将ls调整为败者树 bk=MINKEY; for(i=0;i=0;i-) Adjust(ls,i); 依次从bk-1,bk-2,b0出发调整败者CreateLoserTree谐碑姻秩仓涛其程攒粮琴啥嗓波事全侥阎掉试私商峻幌克苛鸽说祈蔑殷吴第10章数据结构排序第10章数据结构排序第82页，共91页。82调整败者树void Adjust(int ls,int s) 从叶子结点bs到根结点ls0的路径调整败者树 t=(s+k)/2; lst是bs的双亲结点 while(t0) if(bsblst) slst; s指示新的胜者 t=t/2; while ls0=s;Adjust众党有舰尊偶职逸握顺趾栽塑翱款隧坯蔫舀润的揪蛊骨振布分袜特母摹券第10章数据结构排序第10章数据结构排