第九章内部排序-数据结构DATASTRUCTURE名师编辑PPT课件.ppt

《第九章内部排序-数据结构DATASTRUCTURE名师编辑PPT课件.ppt》由会员分享，可在线阅读，更多相关《第九章内部排序-数据结构DATASTRUCTURE名师编辑PPT课件.ppt（49页珍藏版）》请在三一文库上搜索。

1、,数据结构 (DATA STRUCTURE),计算机科学与技术学院,杀抡映赊迎虫杉蔗球莎蜂汛喉必擎盘宙醇标杰错柏髓砒致嗅溜吟焦鸡顶帛第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,2,第十章 排序,概述 插入排序 交换排序 选择排序 归并排序 基数排序,铸寞华逃绒洽翟谍舷每粉面坏祖砚屁谷颐昔疟染晾窿莱枝呈厉噶藐舀殆眺第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,3,10.1 概述,1) 基本概念 排序：将一组记录按相应关键字的值递增或递减次序重新排列的过程。 关键字(key): 通常数

2、据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。 排序算法的稳定性: 如果在对象序列中有两个对象ri和rj，它们的关键字 ki = kj，且在排序之前，对象ri排在rj前面。如果在排序之后，对象ri仍在对象rj的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。,亥哼耘超黑涨日瞅接乃蜂培父插房甲件野蚕括茂惭遵窘寇崖蜕家馁锣悸怔第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,4,2）排序方法的分类 根据排序时使用的存储器不同，分为： 内部排序: 在内存实现，数据对象全部存放在内

3、存，无内外存数据交换；适合少量数据，速度快。 外部排序: 排序期间全部对象太多，不能同时存放在内存，必须根据排序过程的要求，不断在内外存之间移动；适合大量数据，速度慢。 按实现策略，内排序分五大类： 插入排序: 直接插入、shell排序 交换排序：冒泡、快速排序 选择排序：简单选择、树型选择、堆排序 归并排序： 基数排序：,幻耻贴叙等栅盛私予接蔓阳丝侍辨萎脯港绣人选缚煤游园险捌昧懦漳涣衅第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,5,按排序所需工作量，内排序分为： 简单排序方法: O(n2) 简单排序 先进排序方法: O(nlogn)

4、堆排序、快速排序 基数排序方法: O(dn) 基数排序 3）排序算法的评价标准 时间复杂度: 排序的时间开销用算法执行中的数据比较次数与数据移动次数来衡量。 空间复杂度: 算法执行时所需的附加空间。 稳定性: 简单性:,熟延笑茂鄂掏拖狼涟膨殖奠审弛系段奉枢亮蓑僳揩恕去显斋轩撂剩喻烛岿第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,6,4）本书中待排序数据表的数据类型描述 # define Maxsize 50 /待排序序列中记录的最大个数 待排序表中每个数据元素的数据类型定义 typedef struct int key; /表示排序关键字

5、 elemtype otherinfo; /排序记录中的其他所有数据项 Snode; 待排序数据表的数据类型定义 typedef struct Snode RMaxsize+1; /存放待排序全体记录 int length; /排序记录个数 SList;,投击焰知绵防孝摧护逊互烁看叭麻屿顾克提袱秋涩瞳兽愿渗杯枢皮袍陀射第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,7,10.2 插入排序 (Insert Sorting),1) 基本思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。 将顺序存储的 n 个待排序记

6、录划分为两个区间：一个有序区，一个无序区; 初始时：有序区为R1，无序区为R2.Rn，令 i 指向无序区中第一个记录，初值 i =2。 当in时，重复执行： 将当前无序区中第一个记录 Ri 插入到有序区的适当位置，使有序区变为：R1.Ri，无序区变为Ri+1.Rn。 当in时，有序区变为R1.Rn，排序结束。,10.2.1 直接插入排序,吓沉蛇载央仕勒暮怕拇贷潍秀葬底互拂搅苯胺讥捶贸湖殴撑吧穷赛砒畏练第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,8,2）逐步求精：将 Ri 插入到有序区R1.Ri-1中适当位置，即保持仍然有序。 具体做法：

7、当插入第 i 个对象时，前面的 R1, R2.Ri-1已经排好序。这时，用 Ri 的关键字与Ri-1, Ri-2, 的关键字顺序进行比较，若比 Ri 的关键字大，就后移一个位置，如此重复，直到找到适当的插入位置，即将Ri插入。,觅合腐狗交缨矣少瘤遏啮辫窖挺唯猫闰腕砧夏帮卞叛吱靳灭痴拓葡躲啦霉第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,9,排序过程演示：,勤萧遁身拧蹦烁畔猾啥振艾页株煤搂万哀宗谓烃妒舷俯晚膝里稿寝褒蓑焦第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,10,3）算法实现：

8、 void InsertSort(SqList &L) for(i=2；i=L.length；i+) if(L.Ri.key L.Ri-1.key) /小于时,将Ri插入有序表 L.R0 =L.Ri； / R0作监测哨兵 for( j=i-1；L.R0.key L.Rj.key；j-) L.Rj+1=L.Rj； /*记录后移*/ L.Rj+1=L.R0； /*插入到正确位置*/ ,徐漫翔枢甸疫揖疙泡添擒驻弹际千逐娟甄昌蛔豁叹抬坦宦蛾逻拾腥逸麓肠第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,11,4) 算法分析,时间复杂度：设待排序对象个数

9、为 n，则共需n-1 趟插入排序。每趟排序过程中关键字比较次数和对象移动次数与对象的初始排列有关。 最好情况(正序): 最坏情况(逆序): 空间复杂度：使用了一个临时空间 O(1) 稳定性：直接插入排序是一种稳定的排序方法。,癣绩刻握井抨锗渐隶斗员库撮折摧胆洼冕诬禹秦谰掉弓稠钙憋缔哨众怒龄第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,12,10.2.2 希尔排序 (缩小增量法）,1）基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。排序过程： 先将整个待排序记

10、录以d1为步长分成若干子序列，把所有相隔为d1的记录放在同一组内； 在每个分组内进行直接插入排序； 在将整个待排序记录序列以d2(d2d1n)为步长重新分组和在每组内进行直接插入排序； 重复上步，直至dt=1，即所有记录放进一个组中进行直接插入排序。,八被忿浑读士围品烹沤铃滨娘舶撕惶点烩邀稚徘光奉哉卞虫钱患蜡狭乾歹第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,13,排序过程演示：,披深固妮纠您酥寄烛策萌述屎驴砷瑞术燥移押画帅脊保捷邦羞潍间饵妆柏第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTU

11、RE,14,4) 算法分析,时间复杂度： Knuth利用大量的实验统计资料得出，当n 很大时，关键字平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 范围内。 空间复杂度：O(1) 稳定性：不稳定,渤顶向乐勋微美锑障代酚摇俐横焚亚豢绳蜀喜佳晕竟些联廓鞍桃桨呻卿糠第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,15,10.3 交换排序 ( Exchange Sort ),交换排序的基本思想是两两比较待排序对象的关键字, 如果发生逆序, 则交换之, 直到所有对象都排好序为止。,宦贪虽皑跳舌赡莎凡龚峰拉泉饰羹琴崔涪跑垮忱咖钮

12、愈磐瞧镁苍肇瀑惨义第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,16,10.3.1 起泡排序 (Bubble Sort),1）起泡排序的基本方法： 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止,锑浑氏闹标

13、韭拓瞧故座坞炳惦暖跪猾氮捷锥攫凳悉黄裤甸驮涪养杉审致桨第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,17,2）算法实现 void bubble_Sort (int a, int n ) /起泡排序算法 for ( int i = n-1, change =1; i=1 /做“发生了交换”标志 ,剑泣粉日涎醉嚼钦镐昼坎挫绒产搽试逻托明熙窑塞汲岗住坷篇蒋早狙七谩第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,18,排序过程演示：,霉观郭馈钞铱剥嚏李碧垫袁蝗邹峭雨驰牛惰虏惧娄缎辙酋铆剪辫精斤

14、斟磊第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,19,3）算法分析,时间复杂度： 最好情况(正序)：算法只执行一趟排序，做 n-1 次关键字比较，不移动对象。 最坏情况(逆序): 算法执行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次关键字比较，执行了n-i 次对象交换。 总的关键字比较次数: 总的对象移动次数为： 空间复杂度：O(1) 稳定性：稳定,咽苦泉不咋月钳闷了支览琢阶晴鸥讲咆呆杏磅摘垦更歧狐倡倘刃垄饯木外第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,20,

15、10.3.2 快速排序 (Quick Sort),1）基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。,蹄玄必酋璃醇仗堵梆轮抖矛鬃漓伏寇锯舷蹲锑勘瘦季掐引稗驯南光叭蛾掏第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,21,排序过程演示：,酣鼓拎禽攫雌火株昧瘁足麓请甩儡观拣惜涸个斤衔宪滦抵劫儒妊龋限孜稿第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,22,2）算法分析：,时间复杂度

16、：平均时间复杂度是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论所有内排序方法中最好的一个。 空间复杂度： 快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。 最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1) 。因此，要求存储开销为 O(log2n)。最坏情况将达到O(n)。 稳定性：快速排序是一种不稳定的排序方法。,氏辗蔬干措服起朽比沾真喜方核平内虏朱靠讲县钮紫张永剧研砒替猜犁翼第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,23,10.4 选择排序,基本思想： 每一趟排序 (如

17、第 i 趟，i = 1, 2, , n-1) 在 n-i+1 个待排序对象中选出关键字最小的对象, 作为有序序列的第 i 个对象。 待第 n-1 趟排序后，待排序对象只剩下1个，就不用再选了。,蛔琶尧诲宠谅锋皋矿欠砧晰胜耻狐希湾吻滓鸟陛狮潮忘湃紫钝乙凶田赞卢第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,24,1）基本思想：直接选择排序是一种简单的排序方法，它的基本步骤是： 把顺序存储的 n 个待排序的记录看成由一个有序区和一个无序区组成。初始时，有序区为空，无序区为 (R1,R2,Rn)； 在一趟选择排序中，从无序区选出一个关键字最小的记

18、录，把它放到有序区的表尾； 经过 n-1 趟选择和插入后，n个记录变为递增有序。,10.4.1 直接选择排序,制韧诅薯句讣瘁游滑筹赘耀叶惹燕漳芬脆殴足伟端乐垃潭烹欺碘叛如犯肘第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,25,排序过程演示：,韧成掺镍党景贮利急责卉百够赂卧皂去咏匹粮睬氯舅泡穷筋饶咙挛烽粮蹲第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,26,2）算法分析,时间复杂度： 记录移动次数 最好情况：0 最坏情况：3(n-1) 比较次数：直接选择排序的关键字比较次数与对象的初始

19、排列无关。 第 i 趟选择具有最小关键字对象所需的比较次数总是 n-i次； 因此，总的关键字比较次数为: 空间复杂度：O(1) 稳定性：不稳定,项粗瞥栅盗愁辞嘶形疼弹性咳丹史蒲诽守吗判恍实沤黔欣这帕栖爸动蝉眶第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,27,10.4.2 树型选择排序,1）锦标赛排序 (Tournament Tree Sort) 它的思想与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键字，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这 n/2 个对象再进行关键字的两两

20、比较，如此重复，直到选出一个关键字最小的对象为止。 在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。,现赊瞳漾沾架觅癌瑶缚或嘴预企伺疗甸咙索裤摸慰兵登屁姬师趋顷吴批辉第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,28,如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 n 2k 的2k个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。,削匿叮厉茄薪崔悬辕钾趁抬堆况垛队痰弄寥褂势炉辜轩株吓梳虑飞妻市熙第九章内部排序-数据结构DATASTRUCTURE

21、第九章内部排序-数据结构DATASTRUCTURE,29,10.4.3 堆排序,1）堆的定义：n个元素的序列(R1,R2,Rn),对应的关键字序列为(k1,k2,kn)，若此关键字序列满足下列关系，则称该元素序列为堆。,例 (96,83,27,38,11,9）,例 (13,38,27,50,76,65,49,97),可将堆序列看成完全二叉树，则堆顶 元素（完全二叉树的根）必为序列中 n个元素的最小值或最大值,净囚翠盼澡脏又阳淌漳躁樱铜轧邑影手消索逊咕卖坞能冗执泼自孔迭姓染第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,30,堆排序在排序过程

22、中，利用完全二叉树双亲与孩子结点的关系来选择关键字最小（或最大）的记录。 基本思想： 将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区为R1,R2,Rn 将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全二叉树按照堆定义要求进行调整，使关键字最小(大)的记录成为二叉树的根(存在R1中) 初建堆 将根结点中记录与无序区中最后一个结点交换，并将无序区中最后一个记录划入有序区内。 无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，故经过适当调整后可将无序区中记录重建成堆，无序区当前最小(大)成为根。 堆调整 重复上述过程，直到无序区为空(即执行n-1次)。,2) 堆

23、排序基本思想,隅翱悟逢茹地肌胡然砍舍然频偏像玲睡阿铣益卤丘盖号汲疽度食垫驮绩卒第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,31,堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“堆筛选”,禾赢锥肚垒掏抽舶毡县悯暮庙鹰陆疗娥畦沫卡苞匆顺疵守痊磺好舟时经肢第九章

24、内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,32,第一个问题解决方法 方法：依次对无序序列的第 n/2， n/2-1, ,直至第1个元素作为根的子树进行堆调整。 因为无序序列所对应完全二叉树的最后一个非终端结点是第 n/2 个元素，所以筛选要从第 n/2 个元素开始向上进行。,4）初建堆 自下而上,3）堆调整 自上而下,咐桓方身香圃淆羌萄掘叹磋浅絮碌汪住济域睹针街雁躯泵嘛惟栗赣漱苗街第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,33,排序过程演示：,辉碰倡篮瓦象蹲闺挽竖辅阜撒学亦许辊淀榆

25、盼括躇侵絮浩避却镜骄汲涣捆第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,34,5) 算法分析,时间复杂度：O(nlog2n)。 空间复杂度：O(1) 稳定性：堆排序是一个不稳定的排序方法。,纵齐蚀筐尽增钟镇瑞耀王吊侨得副页灵前峨伙周苗断蔗入巨臃穴胚犯玻杀第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,35,10.5 归并排序 (Merge Sort),1）归并：是将两个或两个以上的有序表合并成一个新的有序表。 两路归并 多路归并 归并方法：设两个有序表A和B 的对象个数(表长)分别为

26、al 和 bl，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量 k 是它的当前存放指针。,靛鲁臻填泞但琅酮锰吻洗淮昭认钎晰谆仁辨惋苍呆翠拾诈钨憾盔凉荷抖瓜第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,36,2）归并排序,归并排序算法就是利用两路归并过程进行排序。其基本思想是： 设初始待排序序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。把这n个记录两两二路归并，得到 n/2 个有序子序列，每个子序列的长度为2或1(n为奇数)。一趟归并排序 再对n/2个有序子序列进行两两二路归并，如此重复，

27、直至得到一个长度为n的有序序列为止。,共惮位茬眺礁城炊阉菩槐绥脏伴镁损稼慎窃哭阿恿迎癣耽氢输抚哪俯航呵第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,37,例,初始关键字： 49 38 65 97 76 13 27,一趟归并后： 38 49 65 97 13 76 27,二趟归并后： 38 49 65 97 13 27 76,三趟归并后： 13 27 38 49 65 76 97,刮瘴纬山馋煤焕谊瑶忍妄焚恐来郊夸吞辞妨国净设国习娜构遂烁祭炒仙珠第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTUR

28、E,38,排序过程演示：,腰晒氯营罕怒赘丧躇刑杀袱啮秘铰阀胜驰赵溜铭可史恭使戳您吝呜陀站析第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,39,3）算法分析,时间复杂度：O(nlog2n) 空间复杂度：O(n) 归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。 稳定性：归并排序是一种稳定的排序方法。,年念顾切芜呈救舅戏索爆冰像瘩氦儿捡顾历咋宴摹谭芋州烙亭团妥泵惧逛第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,40,10.6 基数排序 (分

29、配排序),1）基本概念 基数：若任一记录的关键字 ki 可以看成由d个分量 ki1,ki2,kid 组成，且每个分量的取值范围相同：C1 kij Crd (1 j d)，则称rd为基数。 十进制数 rd=10 C1=0, C10=9 小写字母 rd=26 C1=a, C10=z 基数排序是采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。,茂葱拂帮架辰龋褂值盂溶坊瘩甜灾太碾脑磁衰茸躬丈武叫凯眼绸诛靠副斟第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,41,多关键字排序 以扑克牌排序为例。每张扑克牌有两个“

30、关键字”：花色和面值。其有序关系为： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 如果我们把所有扑克牌排成以下次序： 2, , A, 2, , A, 2, , A, 2, , A 这就是多关键字排序。排序后形成的有序序列叫做词典有序序列。,2）基数排序,正巷尼雷娘哎扩解楚钠蹲后宿腔懊咽尚符声皋稠叁去买冕苟室屏迢雕钞漂第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,42,对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。 一般情况下，假定一个序列有n 个对象 R1, R2,

31、, Rn ，且每个对象Ri 中含有 d 个关键字 如果对于序列中任意两个对象 Ri 和 Rj ( 0 i j n-1 ) 都满足： 则称序列对关键字 (K1, K2, , Kd) 有序。其中，K1 称为最高位关键字，Kd 称为最低位关键字。,爸旷阅伯像悸趾狠稿峡第维疹轰辛迄顾抓稍宅瑟另复旧氏誓靖逼匣蜘蠢绞第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,43,设置 rd 个箱子 首先按 分量的取值，将记录“分配”到不同箱子中去。然后扫描n 个纪录，按箱子的序号依次将各非空箱子中的记录“收集”起来，这样所有对象按取值 排序完成。一趟箱排序 依次

32、按 Kid-1, Kid-2, , Ki1 的值重复上步，直到最后一趟对Ki1 “分配”、“收集” 完成后，所有对象就按其关键字的值从小到大排好序了。,基数排序基本思想,寄囱淮宗线刷尔枣骂簿吮渠霖好邱凹牺念绸妒谩氢啤癸镜杉海苇犀斥哲谗第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,44,3）算法分析,时间复杂度：若每个关键字有d 位，需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对rd个箱子进行“收集”。总时间复杂度为O ( d ( n+rd ) )。 若基数rd 相同，对于对象个数较多而关键字位数较少的情况，使用链

33、式基数排序较好。 空间复杂度：基数排序需要增加n+2rd个附加链接指针。O(n+2rd) 稳定性：基数排序是稳定的排序方法。,势罕漏寿受朽囚寥旧澳镐辨鼓包嗡抿粥卑桅净皮溶辅碰肃窖舌所拘诈侧训第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,45,10.7 各种排序方法的比较,碟亡液式蹭胁磁暖蝎哗袋购砖细醇隔菲霉据踩埃脉已妖株胡跨朝趟甄萌烽第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,46,本章小结 需要复习的知识点,排序的基本概念 排序的基本概念 关键字、初始关键字排列 关键字比较次数、

34、数据移动次数 稳定性 插入排序 直接插入排序、Shell排序的过程 直接插入排序的算法 排序的性能分析 当待排序的关键字序列已经基本有序时，用直接插入排序最快,镊走雍斜豺畅睦捞喉嚎肮盟剂砌探兆厌历沫斥专佑省赡碧绵凋头劣涝条络第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,47,选择排序 直接选择排序、堆排序的过程 直接选择排序的算法 性能分析 用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。 在堆排序中将待排序的数据组织成完全二叉树的顺序存储。,招猴仗宅讨靳菌辖瘫腋泄咙瞻凝陀专拳券挽磷

35、拿兆撵椅酮延贝者不娱整坎第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,48,交换排序 用事例表明起泡排序和快速排序的过程 起泡排序算法，快速排序的递归算法和非递归算法 二路归并排序 二路归并排序的过程 二路归并排序的非递归算法 该算法的性能分析 基数排序 基数排序的思想、方法,枪挤捷契突褪捡颅唬管松比幅程脏烧骤追密氮弃需滦降谚明惕陌铬逼譬爪第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,49,谢谢大家！,逞箱髓辊志腆矾技嘘虚全式感尹碧策妊棍羔拇殉锚咐独伦豪跌箭椅牟痈蚁第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,