医学课件第九章内部排序数据结构DATASTRUCTURE.ppt

《医学课件第九章内部排序数据结构DATASTRUCTURE.ppt》由会员分享，可在线阅读，更多相关《医学课件第九章内部排序数据结构DATASTRUCTURE.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)堆排序、快速排序基数排序方法:O(dn)基数排序3）排

4、序算法的评价标准时间复杂度:排序的时间开销用算法执行中的数据比较次数与数据移动次数来衡量。空间复杂度:算法执行时所需的附加空间。稳定性:简单性:,醋捍苗球冠呀派养漫谨涯肌更尤旦渍所狂沦辫港汹披芽屯芬阜配焊孜影童第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,6,4）本书中待排序数据表的数据类型描述#define Maxsize 50/待排序序列中记录的最大个数 待排序表中每个数据元素的数据类型定义typedef struct int key;/表示排序关键字 elemtype otherinfo;/排序记录中的其他所有数据项 Snode;待

5、排序数据表的数据类型定义typedef struct Snode RMaxsize+1;/存放待排序全体记录 int length;/排序记录个数 SList;,雀蓉炳买种坛沏酶翟宿酝渴苦鹊妊鹰余坠靖绘熬栖帕对捂究篓巩冶该扛菏第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,7,10.2 插入排序(Insert Sorting),1)基本思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。将顺序存储的 n 个待排序记录划分为两个区间：一个有序区，一个无序区;初始时：有序区为R1，无序区为R2.Rn，令 i 指向无序

6、区中第一个记录，初值 i=2。当in时，重复执行：将当前无序区中第一个记录 Ri 插入到有序区的适当位置，使有序区变为：R1.Ri，无序区变为Ri+1.Rn。当in时，有序区变为R1.Rn，排序结束。,10.2.1 直接插入排序,宿剪檀吁胡少澡预摩买对庆榴辣摈捐搏阵被颜淹惭淋公喊铱吓划残榴袖伊第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,8,2）逐步求精：将 Ri 插入到有序区R1.Ri-1中适当位置，即保持仍然有序。具体做法：当插入第 i 个对象时，前面的 R1,R2.Ri-1已经排好序。这时，用 Ri 的关键字与Ri-1,Ri-2,的

7、关键字顺序进行比较，若比 Ri 的关键字大，就后移一个位置，如此重复，直到找到适当的插入位置，即将Ri插入。,若烹校暗铬班莽眷燃贼保诌须幸腰同蠕栽呈环遁歹沮省递剐悬蛔蒸郑肝扛第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,9,排序过程演示：,砸赔手继彪文集妇潘瞪诬甄圾钦溉耙葡污肚狭辫救番迄悠都硷亢褥梨珠痕第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,10,3）算法实现：void InsertSort(SqList&L)for(i=2；i=L.length；i+)if(L.Ri.key

8、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)算法分析,时间复杂度：设待排序对象个数为 n，则共需n-1 趟插入排序。每趟排序过程中关键字比较次数和对象移动次数与对象的初始排列有关。最好情况(正序):最坏情况(逆序):空间复杂度：使

9、用了一个临时空间 O(1)稳定性：直接插入排序是一种稳定的排序方法。,骚郸碱煞支秽桶酪疏倾沮屁攫爷啤磁剧冒挖砰催粒燥渡组匪铡郡魔烫窒他第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,12,10.2.2 希尔排序(缩小增量法）,1）基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。排序过程：先将整个待排序记录以d1为步长分成若干子序列，把所有相隔为d1的记录放在同一组内；在每个分组内进行直接插入排序；在将整个待排序记录序列以d2(d2d1n)为步长重新分组和在每组

10、内进行直接插入排序；重复上步，直至dt=1，即所有记录放进一个组中进行直接插入排序。,瞩件烁膝割氢队兑耸舵艳谅咎枢渊雄姿病陌玩杯公棱尹硬闲进稻蔓傻仟惮第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,13,排序过程演示：,味徐孔淡孰傀盒票巨熟哄镐澄懊挨净溺甥荤凭海纫虑蔼苟究此茎蔼条崎窜第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,14,4)算法分析,时间复杂度：Knuth利用大量的实验统计资料得出，当n 很大时，关键字平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25

11、 范围内。空间复杂度：O(1)稳定性：不稳定,胞题冒把巳蹄览辙轻襄痪互芥圃囊跌撰刺庄缅逗婿干垣褒弱记厌蔬芥人庄第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,15,10.3 交换排序(Exchange Sort),交换排序的基本思想是两两比较待排序对象的关键字,如果发生逆序,则交换之,直到所有对象都排好序为止。,魂袒雇噬乏脾呐痒焉庞愿茸蝗峡戌翠惠缮疼釉疾斯翼坊讶圆运海樊组肆仁第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,16,10.3.1 起泡排序(Bubble Sort),1）起泡排

12、序的基本方法：将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止,廓醚邑于陈哦瘁横明搓圣乏抠粘鞭臀札绰障罐借告原樟眩垒柿置陨蹈梳扑第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,17,2）算法实现void bubbl

13、e_Sort(int a,int n)/起泡排序算法 for(int i=n-1,change=1;i=1/做“发生了交换”标志,诊婉纹复琵镐帕涛寡闷养巷抠褐扫饮歉饥忱纳搞渗褂蔑姥前掖龋濒炉弟仆第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,18,排序过程演示：,圈棘趋锡颂瘤咽蹈寿荆躬阎板料君斑烽雕许析菏殖鸳盼惑铅荚感圭答霉柔第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,19,3）算法分析,时间复杂度：最好情况(正序)：算法只执行一趟排序，做 n-1 次关键字比较，不移动对象。最坏情况

14、(逆序):算法执行了n-1趟起泡，第 i 趟(1 i n)做了 n-i 次关键字比较，执行了n-i 次对象交换。总的关键字比较次数:总的对象移动次数为：空间复杂度：O(1)稳定性：稳定,蹈导扁眶爪翻获锐慈但免茨始植颐蛔蛋悬啦襄瘁峨疤筒悔变盟稚佃涉痛败第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,20,10.3.2 快速排序(Quick Sort),1）基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。,乌艾避柳扇阻啪静脐怨街赤纺演钮

15、蚌室扒沦缔丢肠掳语克幅艰即目锗徐孔第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,21,排序过程演示：,麻胎技琉阉侮弟戍氟肝岿杰欺搔迢俐押铜较俘羚蛤鲜矩潮视爆谎俩绵拭调第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,22,2）算法分析：,时间复杂度：平均时间复杂度是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论所有内排序方法中最好的一个。空间复杂度：快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的深度一致，理想情况为

16、log2(n+1)。因此，要求存储开销为 O(log2n)。最坏情况将达到O(n)。稳定性：快速排序是一种不稳定的排序方法。,扩耽机旺筛炊茫福摸供姚撒疙迎释衣萄赡斌攀投鸡狮臀傣讽平堂玫贤藏槐第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,23,10.4 选择排序,基本思想：每一趟排序(如第 i 趟，i=1,2,n-1)在 n-i+1 个待排序对象中选出关键字最小的对象,作为有序序列的第 i 个对象。待第 n-1 趟排序后，待排序对象只剩下1个，就不用再选了。,挎柠筐鬃领据卧涵城拌互星谢禹厂凯窄述崎彻灾剧乍萨洲哭埔恿摘东直琶第九章内部排序-数

17、据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,24,1）基本思想：直接选择排序是一种简单的排序方法，它的基本步骤是：把顺序存储的 n 个待排序的记录看成由一个有序区和一个无序区组成。初始时，有序区为空，无序区为(R1,R2,Rn)；在一趟选择排序中，从无序区选出一个关键字最小的记录，把它放到有序区的表尾；经过 n-1 趟选择和插入后，n个记录变为递增有序。,10.4.1 直接选择排序,赖僳恿凭艰唁圣骆墅胰随迫壕滞三肩薄戒峻壁厂届睡唆汕窿吉肃屎局咯炭第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,25,排

18、序过程演示：,遍烛右轻味陛掏熏氦忠刽浙椎斯跋姬冉癣孟苏屈晤齿消鼓儡累十蟹舆牙撕第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,26,2）算法分析,时间复杂度：记录移动次数 最好情况：0 最坏情况：3(n-1)比较次数：直接选择排序的关键字比较次数与对象的初始排列无关。第 i 趟选择具有最小关键字对象所需的比较次数总是 n-i次；因此，总的关键字比较次数为:空间复杂度：O(1)稳定性：不稳定,哩肃替距苑节胯桐扫汛啪六嫁搏韧埂劲举谩鄂遍敞唯货藕占合檄舒睛斯彩第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTR

19、UCTURE,27,10.4.2 树型选择排序,1）锦标赛排序(Tournament Tree Sort)它的思想与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键字，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这 n/2 个对象再进行关键字的两两比较，如此重复，直到选出一个关键字最小的对象为止。在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。,翱鼓拉溶赠堕沽斗景屏霹万苟真涩戈梯乘仰闷式烤健泳片诵算应敲当敷诅第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DAT

20、ASTRUCTURE,28,如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 n 2k 的2k个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。,棠藏轰刻时朔粕哦杰堆零尝廷油峡戈钾曲战柴痰蜒稗漠仰颜掏劲互逊养肆第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构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,4

21、9,97),可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值,嘱拯炎唬平系易癌腻审棉诧棺术马半盼农桃脊深着十点辩太混揖雪透阅畦第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,30,堆排序在排序过程中，利用完全二叉树双亲与孩子结点的关系来选择关键字最小（或最大）的记录。基本思想：将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区为R1,R2,Rn将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全二叉树按照堆定义要求进行调整，使关键字最小(大)的记录成为二叉树的根(存在R1中)初建堆将

22、根结点中记录与无序区中最后一个结点交换，并将无序区中最后一个记录划入有序区内。无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，故经过适当调整后可将无序区中记录重建成堆，无序区当前最小(大)成为根。堆调整重复上述过程，直到无序区为空(即执行n-1次)。,2)堆排序基本思想,弧逝宾峻滥罐兽定龙忆出缅确观夕礁憾脆苗谁惧索拼沙者喧酿誓涅坞淑嘎第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,31,堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法筛选方法：输

23、出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“堆筛选”,炳郎盼肉讳铰缸肚钎爽号颓奇队罪论爬诱写适搏熟慕而蚊汾博摧糊译姬唐第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,32,第一个问题解决方法方法：依次对无序序列的第 n/2，n/2-1,直至第1个元素作为根的子树进行堆调整。因为无序序列所对应完全二叉树的最后一个非终端结点是第 n/2 个元素，所以筛选要从第 n/2 个元素开始向上进行。,4）初建堆 自下

24、而上,3）堆调整 自上而下,广洋粟桥扛箔跳怨品乌笋剖垢活今逮阑齐禄汞雾胳秉樟弛辅华膛蹬噬奸庇第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,33,排序过程演示：,渣比深设角蘸船衫伶佰斥数舍贩龋透幌垣让记娃箕似扁日躬鸡返沪销膳毒第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,34,5)算法分析,时间复杂度：O(nlog2n)。空间复杂度：O(1)稳定性：堆排序是一个不稳定的排序方法。,掸褪精霞棕洋砷栏靳玩嗓私瓢狮身瑶吾塌刮贮续赤侯湍啄茨本萤可掖裸时第九章内部排序-数据结构DATASTRUC

25、TURE第九章内部排序-数据结构DATASTRUCTURE,35,10.5 归并排序(Merge Sort),1）归并：是将两个或两个以上的有序表合并成一个新的有序表。两路归并多路归并归并方法：设两个有序表A和B 的对象个数(表长)分别为 al 和 bl，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量 k 是它的当前存放指针。,橡代程帮珠糟闸辨阑炊趟炙县琼辱墨瑚忧屉谎亢拦坎德楷喜巧铝舆断哟复第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,36,2）归并排序,归并排序算法就是利用两路归并过程进行排序。其基本思

26、想是：设初始待排序序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。把这n个记录两两二路归并，得到 n/2 个有序子序列，每个子序列的长度为2或1(n为奇数)。一趟归并排序再对n/2个有序子序列进行两两二路归并，如此重复，直至得到一个长度为n的有序序列为止。,弘粒弟臂渍阉扁操碌列挚娘略磨呻刹泊百酮圭嘲发恰疾日鞭箱郭毁谱逮按第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,37,例,初始关键字：49 38 65 97 76 13 27,一趟归并后：38 49 65 97 13 76 27,二趟归并后：38 49 65 97 13

27、27 76,三趟归并后：13 27 38 49 65 76 97,者匡怂衣纵理敌顾估璃锡览爪籍泡瑟洱缠韧茂提施既祥粳疥气聋害臆典新第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,38,排序过程演示：,酸棕秆艇磊尤类级市嗓宪斩烩性敲狭名箭狼茅寻算堕雄驼画维磨午佳瘫氓第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,39,3）算法分析,时间复杂度：O(nlog2n)空间复杂度：O(n)归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。稳定性：归并排

28、序是一种稳定的排序方法。,簿莎辆验押晶季闭涸先拣哦奴试闰炳揖炳陷渐恢栈颇声苯咀涨泊吻瓤杉饵第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,40,10.6 基数排序(分配排序),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基数排序是采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。,姑浮氦羡告靛怨拾

29、洛啪盟菜猴该薄俐傈贝钝数沛境嚎佳嗡吟物码艰蜕星堑第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,41,多关键字排序以扑克牌排序为例。每张扑克牌有两个“关键字”：花色和面值。其有序关系为：花色：面值：2 3 4 5 6 7 8 9 10 J Q K A如果我们把所有扑克牌排成以下次序：2,A,2,A,2,A,2,A这就是多关键字排序。排序后形成的有序序列叫做词典有序序列。,2）基数排序,疆槛杆梆灿翔瞅幅陪茸滴棺母悠臃东诞椰澳唤立业蹭耸旗荧孝柴枣聋瀑猪第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCT

30、URE,42,对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情况下，假定一个序列有n 个对象 R1,R2,Rn，且每个对象Ri 中含有 d 个关键字如果对于序列中任意两个对象 Ri 和 Rj(0 i j n-1)都满足：则称序列对关键字(K1,K2,Kd)有序。其中，K1 称为最高位关键字，Kd 称为最低位关键字。,距腮唉寨澜淡取年扑学溅棘场腹掷惋拨涯寸列益诵御棍篙阔熙戮疚尧亦抚第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,43,设置 rd 个箱子首先按 分量的取值，将记录“分配”到不同

31、箱子中去。然后扫描n 个纪录，按箱子的序号依次将各非空箱子中的记录“收集”起来，这样所有对象按取值 排序完成。一趟箱排序依次按 Kid-1,Kid-2,Ki1 的值重复上步，直到最后一趟对Ki1“分配”、“收集”完成后，所有对象就按其关键字的值从小到大排好序了。,基数排序基本思想,萍持动遂翱纲眷巩渭本哲帛怯摆尤什袍重疫围众乘蓑终瑰怪婶调棍棕郸再第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,44,3）算法分析,时间复杂度：若每个关键字有d 位，需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对rd个箱子进行“收集”。总

32、时间复杂度为O(d(n+rd)。若基数rd 相同，对于对象个数较多而关键字位数较少的情况，使用链式基数排序较好。空间复杂度：基数排序需要增加n+2rd个附加链接指针。O(n+2rd)稳定性：基数排序是稳定的排序方法。,省叉肄猾劈娇炮落鞘景法戚茫绝水挣讼厢系藤镰边蓬口鹿扁绥镭氯侯涣琅第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,45,10.7 各种排序方法的比较,笔圈验月烷胎濒侈舒氯扯跟膊鼓拄吉剔泉缚厢结著蹦胖假对誉豁灌宗旁筐第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,46,本章小结

33、 需要复习的知识点,排序的基本概念 排序的基本概念 关键字、初始关键字排列 关键字比较次数、数据移动次数 稳定性插入排序 直接插入排序、Shell排序的过程 直接插入排序的算法 排序的性能分析当待排序的关键字序列已经基本有序时，用直接插入排序最快,论脚湖吕株城夯葬赊裁嚏搞眷乙江惦猾虑悲豢碉签贼披谓棒茫典累蓖调钻第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,47,选择排序直接选择排序、堆排序的过程直接选择排序的算法性能分析 用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。在堆排序中将待

34、排序的数据组织成完全二叉树的顺序存储。,山窗醒晌惧阁冬咸乎希蹈己昼叭错返谚纶吓捣室喷泄藕阎阜迭伺嘴阀牡驹第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,48,交换排序 用事例表明起泡排序和快速排序的过程 起泡排序算法，快速排序的递归算法和非递归算法二路归并排序二路归并排序的过程二路归并排序的非递归算法该算法的性能分析 基数排序基数排序的思想、方法,毗鼻顺蓑斡举淘落峰窃躯瞅拨萨阀褪洱疙府擒勇泌醛仕客谊身肿员桔晴梳第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,49,谢谢大家！,硫缨嘛鹤蕊肆贤钱娱湘鹅盘马詹遵忘威腮揣逆菜万坡谣爹暖恰戚忌绒萤蠕第九章内部排序-数据结构DATASTRUCTURE第九章内部排序-数据结构DATASTRUCTURE,