版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
lirui@1第9章排序9.1插入排序9.2交换排序9.3选择排序9.4归并排序9.5基数排序9.6各种内部排序方法的比较讨论29.1插入排序一、直接插入排序二、折半插入排序三、希尔排序3一、直接插入排序
直接插入排序的基本操作是将一个记录插入到已排好的有序表中,从而得到一个新的、记录数增加1的有序表。例如:已知待排序的一组记录的初始排列如下所示:R(49),R(38),R(65),R(97),R(76),R(13),R(27),R(19)。4假设在排序过程中,前四个记录已按关键字递增的次序,重新排列,构成一个含4个记录的有序序列:现要将第5个(关键字为76)的记录插入上述序列,可以得到一个新的含5个记录的有序序列,则首先要找到插入的位置,然后进行插入。假设从R(97)起向左进行顺序查找,由于657697,则R(76)应插入在R(65)和R(97)之间,从而得到下列新的有序序列:{R(38),R(49),R(65),R(76),R(97)}(2)称从式(1)到式(2)的过程为一趟直接插入排序。{38,49,65,97}(1)5一般情况下,第i趟直接插入排序的操作为:在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i]后,变成含有i个记录的有序子序列r[1…i];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r[0]处设置监视哨。整个排序过程为进行n-1趟插入,即:先将序列中的第一个记录看成是一个有序序列的子序,然后从第2个记录起逐个进行插入直至整个序列变成按关键字非递减有序序列为止。在自i-1起往前搜索的过程中,可以同时后移记录。6例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1
()i=7(133849657697)2727jjjjjj977665493827
排序结果:(13273849657697)7记录按关键字非递增有序排列时比较的次数达最大值记录移动次数达到最大值关键字间的比较次数和移动记录的次数,约为n2/4。由此,直接插入排序的时间复杂度为O(n2
)。记录按关键字非递减有序排列时比较的次数达最小值:
记录不需要移动。8二、折半插入排序插入排序的基本操作是在一个有序表中进行查找和插入,则从上章的讨论可知,这个“查找”操作可利用“折半查找”来实现,由此进行的插入排序称之为折半插入排序。9i=1(30)1370853942620i=213(1330)70853942620…...i=820(613203039427085)折半插入排序i=820(6133039427085)20lowhighmidi=820(6133039427085)20lowhighmidi=820(6133039427085)20lowhighmidi=820(6133039427085)20lowhigh10三、希尔排序基本思想:先将整个待排记录序列分割成若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。排序过程:先取一个正整数d1<n,把全部记录分成若干个组,所有距离为d1倍数的记录放一组,在各组内进行插入排序;然后取d2<d1,重复上述分组和排序工作;直至di=1,即所有记录放进一个组中排序为止11例:4938659776132748554一趟排序:132748
55
4
493865
97
76取d1=5一趟分组:493865
97
76
132748
55
44938659776132748554ji49133827jiji6548ji9755ji76412二趟排序:134
48
3827
49
556597
76取d2=3二趟分组:132748
554
49
386597
761327485544938659776jiji274jiji5538jijiji13取d3=1三趟分组:1344838274955659776三趟排序:4132738484955657697希尔排序所需的比较和移动次数约为n1.3,当n时,可减少到n(log2n)2。149.2交换排序一、起泡排序二、快速排序15一、起泡排序首先将最后一个记录的关键字与倒数第二个记录的关键字进行比较,若为逆序r[n].key<r[n-1].key,则将两个记录交换;然后依次类推,直至第2个记录和第1个记录的关键字比较为止。上述过程称作第一趟冒泡排序,其结果使得关键字最小的记录“漂浮”到第一个记录的位置上。16然后进行第二趟冒泡排序,对后n-1个记录进行同样操作,其结果是使关键字次小的记录“漂浮”到第2个记录的位置上。……,重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止。17例4938659776132730初始关键字3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟38497697139727971376767627301365276530651313494930492738273830383018算法描述与分析起泡排序的效率,若初始序列为“正序”,则只需进行一趟排序,在排序过程中进行n-1次关键字间的比较;反之,若初序列“逆序”,则需进行n-1趟排序,需进行
次比较。并作等数量级的记录移动,因此,总的时间复杂度为O(n2)。19二、快速排序
其基本思想是:通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序。20由此,可以该“枢轴”记录最后所落的位置最作分界线,将序列{L.r[s],L.r[s+1],…,L.r[t]}分割成两个子序列{L.r[s],L.r[s+1],…,L.r[i-1]}和{L.r[i+1],L.r[i+2],…,L.r[t]},这个过程称作一趟快速排序。一趟快速排序的具体做法是:对r[s……t]中记录进行一趟快速排序,附设两个指针low和high,它们的初值分别为low和high,设枢轴记录的关键字为Pivotkey,然后从low所指位置起向后搜索找到第一个关键字大于Pivotkey的记录和枢轴记录相互交换做,重复这两步直至low=high。首先从high所指位置起向前搜索找到第一个关键字小于Pivotkey的记录和枢轴记录相互交换,21X初始关键字:49
38659776132750lowhigh4927lowhighlowhighlowhigh6549lowhigh4913lowhigh9749lowhighlowhigh
完成一趟排序:
(273813)49(76976550)22分别进行快速排序(13)27(38)49(5065)76(97)快速排序结束:13
27
3849
5065
7623通常,快速排序平均时间复杂度为O(nlogn),但待排序记录的键值几乎已排序时,情况反而恶化,每一趟快速排序的基准记录位置就是第一个记录位置或最后一个记录位置。最坏情况下的时间复杂度为T(n)=O(n²)。快速排序的平均时间为Tavg(n)=knlnn,其中n为待排序序列记录的个数,k为某个常数,经验证明,在所有同数量级的此类(先进的)排序方法中,快速排序的常数因子k最小。因此,就平均时间而言,快速排序是目前被认为是最好的一种内部排序方法。快速排序递归算法需要栈空间来实现递归,一般情况下需要的空间为S(n)=O(log2n),最坏情况下,需要的栈空间为S(n)=O(n)。快速排序方法是不稳定的。249.3选择排序一、简单选择排序二、树形选择排序三、堆排序25一、简单选择排序一趟简单选择排序的操作为:通过n-1次关键字的比较,从n个记录中选择出关键字最小的记录,并和第1个记录交换。再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第2个记录交换重复上述操作,共进行n-1趟排序后,排序结束.26初始:[49386597761327]jkkkkkkjji=11349一趟:13[386597764927]i=2jjkkkkk2738二趟:1327[6597764938]三趟:132738[97764965]27五趟:1327384965[9776]六趟:132738496576[97]排序结束:13273849657697四趟:13273849
[769765]28简单选择排序过程中,所需进行记录移动的操作次数较少,其最小值为0,最大值为3(n-1)。然而,无论记录的初始排列如何,所需进行的关键字间的比较次数相同,均为(n(n-1))/2。因此,总的时间复杂度也是O(n2)。算法描述与算法评价29二、树形选择排序树形选择排序,又称锦标赛排序,是一种按照锦标赛的思想进行选择排序的方法首先对n个记录的关键字进行两两比较,然后在其中n/2个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。30386549977613274938651327381313树形选择排序示例31树形选择排序示例3865499776
274938657627382727输出13之后32树形选择排序示例3865499776
4938657649384938输出13、27之后33或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1三、堆排序2、堆和完全二叉树
堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)1、堆的定义n个元素的序列(k1,k2,……kn),当且仅当满足下列关系时,称之为堆34例(13,38,27,50,76,65,49,97)1327384965765097353、堆排序:若在输出堆顶的最小值之后,使得剩余n-1个元素的序列重又建成一个堆,则可得到n个元素的次小值;如此反复执行,便能得到一个有序序列,这个过程称之为堆排序。实现堆排序需解决的两个问题如何由一个无序序列建成一个堆?如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆?二个问题解决方法——筛选364、筛选
13273849657650979727384965765013输出:13372749389765765013输出:139749382765765013输出:1327383849502765769713输出:13276549502738769713输出:132738394965502738769713输出:1327387665502738499713输出:13273849405065762738499713输出:132738499765762738495013输出:1327384950416597762738495013输出:13273849509765762738495013输出:132738495065427665972738495013输出:132738495065769765762738495013输出:1327384950657697435、建堆
建堆:从无序序列的第n/2个元素(即此无序序列对应的完全二叉树的最后一个非终端结点)起,至第一个元素止,进行反复筛选4449653827137697504965382713765097例如含8个元素的无序序列(49,38,65,97,76,13,27,50)45491338276576509749133827657650971349492746时间复杂度:最坏情况下T(n)=O(nlogn)空间复杂度:S(n)=O(1)总共进行的比较的次数为:<2(log2(n-1)+log2(n-2)+……+log22))<2n(log2n)由此,堆排序在最坏的情况下,其时间复杂度为O(nlogn)。47初始关键字:[49][38][65][97][76][13][27]一趟归并后:
[3849][6597][1376][27]二趟归并后:[38496597][132776]三趟归并后:
[13273849657697]9.4归并排序48时间复杂度:T(n)=O(nlog2n)空间复杂度:S(n)=O(n)与快速排序和堆排序相比,归并排序的最大特点,它是一种稳定的排序方法。但在一般情况下,很少利用2路归并排序方法进行内部排序。499.5基数排序一、多关键字排序二、链式基数排序502<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A一、多关键字排序已知扑克牌中52张牌面的次序为:两个关键字:花色(<<<)
面值(2<3<……<A)并且“花色”地位高于“面值”51方法1:先对花色排序,将其分为4个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4个组连接起来即可——最高优先法52方法2:先按13个面值给出13个编号组(2号,3号,...,A号),将牌按面值依次放入对应的编号组,分成13堆。再按花色给出4个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3号组中牌取出分别放入对应花色组,……,这样,4个花色组中均按面值有序,然后,将4个花色组依次连接起来即可——最低位优先法53一般情况下,假设有n个记录的序列{R1,R2,…,Rn},且每个记录Ri中含有d个关键字(Ki0,Ki1,…,Kid-1),则称序列对关键字(K0,K1,…,Kd-1)有序是指:对于序列中任意两个记录Ri和Rj(1i<jn)都满足下列有序关系(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)
其中K0称为最主位关键字,Kd-1称为最次位关键字。54为实现多关键字排序,通常有两种方法:(1)先对最高位关键字进行排序(MSD)最高优先法(2)先对最高低关键字进行排序(LSD)最低位优先法55第一种方法是先对最高位关键字K0(如花色)进行排序,将序列分成若干子序列,每个子序列中的记录都具有相同的K0值;然后分别就每个子序列对次关键字K1(如面值)进行排序,按K1值不同再分成若干更小的子序列;依次重复,直至对Kd-2进行排序之后得到的每一子序列中的记录都具有相同的关键字(K0,K1,…,Kd-2),而后分别每个子序列对Kd-1进行排序,最后将所有子序列依次联接在一起成为一个有序序列,这种方法称之为最高优先法(MostSignificantDigitfirst)(MSD)。56第二种方法是从最低位关键字Kd-1起进行排序。然后再对高一位的关键字Kd-2排序,……依次重复,直至对最高位关键字K0排序后,便成为一个有序序列。这种方法称之为最低位优先法(LSD)。MSD与LSD不同特点按MSD排序,必须将序列逐层分割成若干子序列,然后对各子序列分别排序。按LSD排序,不必分成子序列,对每个关键字都是整个序列参加排序;并且可不通过关键字比较,而通过若干次“分配”与“收集”实现排序。57二、链式基数排序基数排序:借助“分配”和“收集”对单逻辑关键字进行排序的一种方法
链式基数排序:用链表作存储结构的基数排序逻辑关键字可以看成由若干个关键字复合而成的。58由于如此分解而得的每个关键字Kj都在相同的范围内(对数字,0Kj9,对字母“A”Kj‘Z”),按LSD进行排序更为方便,只要从最小数位关键字起,按关键字的不同值将序列中记录“分配”到RADIX个队伍中后再“收集”之,如此重复d次。按这种方法实现排序称之为基数排序,其中“基”指的是RADIX的取值范围,在上述两种关键字的情况下,它们分别是“10”和“26”。首先以静态链表存储n个待排记录,并令表头指针指向第一个记录,如图(a)所示。59第一趟分配对最低数位关键字(个位数)进行,改变记录的指针值将链表中的记录分配至10个链对列中去,每个队列中的记录关键字的个位数相等,如图(b)所示。其中f[i]和e[i]分别为第i个队列的头指针和尾指针;第一趟收集是改变所有非空队列的对尾记录的指针值域,令其指向下一个非空队列的对头的记录,重新将10个队列中的记录链成一个链表,如图(c)所示;第二趟分配,第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的,其过程和个位数相同,如图(d)~(g)所示,至此排序完毕。60初始状态:278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集:链式基数排序举例61505008109930063269278083184589二趟收集:083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集:62008063083109184269278505589930三趟收集:109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集:63算法评价时间复杂度:分配:T(n)=O(n)收集:T(n)=O(rd)T(n)=O(d(n+rd))空间复杂度:S(n)=2rd个队列指针。+n个指针域空间对于n个记录(假设每个记录含有d个关键字,每个关键字的取值范围为rd个值,进行链式基数排序的时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd),整个排序需进行d趟分配和收集。其中:n——记录数d——关键字数rd——关键字取值范围649.6各种内部排序方法的比较讨论排序方法平均时间最坏情况辅助存储简单排序O(n2)O(n2)O(1)快速排序O(nlogn)O(n2)O(logn)堆排序O(nlogn)O(nlogn)O(1)归并排序O(nlogn)O(nlogn)O(n)基数排序O(n(d+rd))O(n(d+rd))O(rd)65从上表可以得出如下结论:(1)从平均时间性能而言,快速排序最佳,其所需时间最省,但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是,在n较大时,归并排序所需时间较堆排序省,但它所需的辅助存储量最多。(2)上表中的“简单排序”包括除希尔排序之外的所有插入排序,起泡排序和简单选择排序,其中以直接插入排序为最简单,当序列中的记录“基本有序”或n值较小时,它是最佳的排序方法,因此常将它和其它的排序方法,诸如快速排序、归并排序等结合起来使用。66(3)基数排序的时间复杂度也可写成O(nd)。因此,它最适合用于n值很大而关键字较小的序列。若关键字也很大,而序列中大多数记录的“最高位关键字”均不同,则也可先按“最高位关键字”不同将序列分成若干“小”的子序列,而后进行直接插入排序。(4)从方法的稳定性来比较,基数排序是稳定的内排方法,所有时间复杂度为O(n2)的简单排序也是稳定的,然而,快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。671、对于给定的键值序列{12,2,16,30,8,28,4,10}分别写出直接插入排序、折半插入排
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学五年级语文《驴子和它的影子》教学设计
- 高中一年级思想政治新学期新征程新成长主题班会教学设计
- 高中信息技术必修2《第二单元 信息系统的硬件与软件 项目三 分析电子点餐信息系统-认识计算机与移动终端》教学设计
- 小学一年级德育教案:美丽的祖国主题班会深度教学设计
- 高中政治选择性必修三《逻辑与思维》第6.3节 复合判断的演绎推理方法 教学设计
- 高中地理必修第二册“人类面临的环境问题与可持续发展”单元教学设计
- 统编版小学六年级语文上册《开国大典》教学设计
- 高中化学必修第一册《物质的量与摩尔质量》教学设计
- 初中语文七年级《赫耳墨斯和雕像者》寓言教学创新设计
- 小学五年级英语Unit1 Different friends分层语境教学设计
- 应急维修动力照明火灾自动报警施工方案
- 2025宁波银行总行金融科技部校园招聘笔试历年典型考题及考点剖析附带答案详解
- TCCAATB 0080-2025民用机场旅客随身携带行李的卡控服务
- 反恐防范宣传课件
- 脑卒中神经内科诊疗与防治要点
- 肿瘤药物给药顺序及解毒剂
- 上海奉贤区区属国有企业招聘笔试题库2025
- 建筑挡烟垂壁设计图集
- 设计素描分割重构方法
- 教育部人文社会科学重大项目标书3
- 风光储储能项目PCS舱、电池舱吊装方案
评论
0/150
提交评论