数据结构-排序课件.ppt
- 文档编号:12957424
- 上传时间:2023-06-09
- 格式:PPT
- 页数:58
- 大小:256KB
数据结构-排序课件.ppt
《数据结构-排序课件.ppt》由会员分享,可在线阅读,更多相关《数据结构-排序课件.ppt(58页珍藏版)》请在冰点文库上搜索。
2023年6月9日,1,9.1基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序的比较9.8外部排序9.9小结,第九章排序,2023年6月9日,2,本章主要内容,本章主要内容,本章详细介绍了排序的基本概念和常见的排序方法,包括常用的内部排序方法,外部排序方法等内容。
通过本章的学习,应掌握如下内容:
l插入排序l交换排序l选择排序l归并排序l基数排序l外部排序l各种排序的比较,2023年6月9日,3,关键字:
在排序过程中,所依据的数据项称为“关键字”,也称为排序记录的关键码。
排序:
对任意排列的数据元素序列,通过某种算法使其满足按关键字递增(或递减)关系的过程。
排序的稳定性和不稳定性:
对需要排序的数据元素序列,将其按关键字进行排序,若相同关键字元素之间的位置关系,排序前与排序后的相对位置不发生变化,称此排序方法满足稳定性;否则称这种排序方法满足不稳定性。
9.1基本概念,2023年6月9日,4,排序算法中结点的数据类型描述方法:
typedefintKeyType;typedefstructKeyTypekey;ElemType;typedefstructElemTypedataMAXSIZE+1;/*结点数组*/intlength;/*表长度*/SL;,内部排序和外部排序:
内排序是指待排序列完全存放在内存中所进行的排序过程,适合记录较少的序列。
如果待排序列记录数量非常多,排序过程不能一次在内存中完成,必需对外存储器进行访问,这样的排序称为外部排序。
2023年6月9日,5,9.2.1直接插入排序直接插入排序:
是指将一个记录按关键字大小的顺序插入到有序序列中的过程。
排序过程如下:
设有一组关键字key1,key2,keyn;认为key1就是一个有序序列;令关键字为key2的数据元素插入到上述表长为1的有序序列中,使之成为一个表长为2的有序序列;最后让关键字为keyn的数据元素插入到上述表长为n-1的有序序列中,使之成为一个表长为n的有序序列。
2023年6月9日,6,【例9-1】有一个待排序列6,13,9,26,11,将其按照直接插入方法实现排序。
如图所示:
初始关键字:
a1a2a3a4a5i=1:
61392611i=2:
61392611i=3:
69132611i=4:
69132611i=5:
69111326,2023年6月9日,7,【算法9.1】直接插入排序voidInsertSort(SL*p)for(i=2;ilength;i+)if(p-datai.keydatai-1.key)p-data0=p-datai;/*设置监视哨*/for(j=i-1;p-data0.keydataj.key;j-)p-dataj+1=p-dataj;/*记录后移*/p-dataj+1=p-data0;/*插入到正确位置*/*if*/,a0a1a2a3a4a5i=1:
61392611i=2:
61392611,2023年6月9日,8,算法分析:
空间复杂度:
该算法只使用了一个辅助存储单元p-data0,所以是O
(1);时间复杂度:
向有序表中逐个插入记录的操作,进行了n-1趟,每一趟比较和移动记录的次数取决于待排序列按关键码的初始排列状态。
最好情况下,即初始序列已经有序的情况下,比较n-1次,移动2(n-1)次。
最坏情况下,即初始序列在呈逆序的情况下,比较n(n-1)/2次,移动n(n-1)/2+2n次。
因此,时间复杂度为O(n2),排序方法稳定,适合于记录个数比较少的情况,若原始数据序列在基本有序的情况下,算法效率比较高。
2023年6月9日,9,直接插入排序算法中,数据的移动是一步步进行的,当数据量很大时,比较和移动的次数都非常大。
希尔排序是对该算法的改进。
希尔排序基本思想是先将整个待排序列分割成若干个子序列,然后对各子序列分别进行直接插入排序,当达到有序状态时,再进行一次直接插入排序。
排序过程如下:
每趟排序,根据对应的步长,将待排序列分割成若干长度为m的子序列,分别对各子序列进行直接插入排序;缩小步长再继续划分子序列排序,直到步长为1为止。
9.2.2希尔排序,2023年6月9日,10,【例9-2】待排序列为34,81,72,42,10,28,52,77,33,13,109,4,42,89。
步长因子di分别取5、3、1,则排序过程如下:
d0=53481724210285277331310944289,子序列分别为34,28,109,81,52,4,72,77,42,42,33,89,10,13。
2023年6月9日,11,第一趟排序结果:
2844233103452724213109817789,第二趟排序结果:
1343428134233724252898177109此时,序列基本“有序”,对其进行直接插入排序,得到最终结果:
4101328333442425272778189109,2023年6月9日,12,【算法9.2】希尔排序voidShellInsert(SL*p,intdk)/*一趟增量为dk的插入排序,dk为步长因子*/for(i=dk+1;ilength;i+)if(p-datai.keydatai-dk.key)p-data0=p-datai;for(j=i-dk;j0&p-data0.keydataj.key;j=j-dk)p-dataj+dk=p-dataj;p-dataj+dk=p-data0;,2023年6月9日,13,算法分析:
算法中的循环是针对一个特定增量di进行分组插入排序,同一组记录的关键字进行比较,需要调整位置时,关键字较小的记录是按照di的宽度进行移动的,当di=1时,此算法就是直接插入方法。
有人曾在大量实验基础上推算出,它的时间复杂度为O(n3/2)。
空间复杂度为O
(1)。
排序方法不稳定。
步长因子序列的选取:
步长因子比较常用的选择d0为n/2,d1为n/4,di=1(n为表的长度),一般不选择2的整数次幂,但是排序最后最后步长必须是1。
2023年6月9日,14,基本思想:
对待排序列中相邻元素进行比较,如果为逆序,则将这两个元素的位置交换。
重复此操作直到整个序列全部有序为止。
9.3.1冒泡排序基本思路为:
首先将第一个记录的关键字和第二个记录的关键字比较,若为逆序,则两个记录交换;然后比较第二个记录和第三个记录的关键字,直至第n-1个记录和第n个记录的关键字比较、交换结束为止。
经过第一趟排序后,关键字最大(或最小)的记录被调整到最后一个记录的位置。
下一趟排序时,这个关键字最大(或最小)的记录就不必考虑了。
直到某一趟排序过程中没有进行交换操作为止。
9.3交换排序,2023年6月9日,15,【算法9.3】冒泡排序voidbubble(SL*p)n=p-length;for(i=1;ii;j+)if(p-dataj.keydataj-1.key)p-data0=p-dataj;p-dataj=p-dataj-1;p-dataj-1=p-data0;flag=1;if(flag=0)printf(“排序结束”);break;/*bubble*/,2023年6月9日,16,算法分析:
算法中flag为标志变量,当某一趟排序中进行过记录交换时flag的值为1,否则为0。
所以外循环结束条件是:
flag=0,已有序,或i=n。
空间复杂度:
仅用一个辅助单元,复杂度为O
(1)。
时间复杂度:
冒泡排序中元素之间比较的次数为n(n-1)/2。
若所给的序列是满足排序要求,则元素移动的次数为0(最好情况);若所给的序列是正好成逆序状态,元素移动的次数为3n(n-1)/2(最坏情况)。
其平均时间复杂度为O(n2)。
2023年6月9日,17,当冒泡排序在数据元素的关键字呈逆序时进行排序,需要进行多次比较和移动操作,数据元素移动是一步一步进行的,且有很多是重复的。
快速排序是对冒泡排序算法的改进。
基本思想:
快速排序又称为分区交换法,是通过对某关键字(支点)的比较,将各待排序列分成前后两部分,后半部分所有记录的关键字值大于等于支点的关键字值,前半部分所有记录的关键字小于等于支点的关键字值。
将待排序列按关键字以支点分成两部分的过程,称为一次划分。
对各部分不断的划分,直到整个序列按关键字有序为止。
9.3.2快速排序,2023年6月9日,18,【例9-3】一趟快速排序过程示例r0r1r2r3r4r5r6r7r8r9r104328397698694515828r0r1r2r3r4r5r6r7r8r9r10434328397698694515828lowhigh从high向前搜索小于r0.key的记录,将其赋值给low指向的位置,r0r1r2r3r4r5r6r7r8r9r10432828397698694515828lowhigh从low向后搜索大于r0.key的记录,将其赋值给high指向的位置,2023年6月9日,19,432828397698694515876lowhigh从high向前搜索小于r0.key的记录,将其赋值给low指向的位置,43282839498694515876lowhigh从low向后搜索大于r0.key的记录,将其赋值给high指向的位置,2023年6月9日,20,432828394986998515876lowhigh,432828394986998515876lowhighlow=high,划分结束,将r0.key的值赋值给low(high)指向的位置,2828394436998515876,2023年6月9日,21,voidQuickSort(SL*P,intlow,inthigh)inti=low,j=high;P-data0=P-datalow;while(idataj.key=P-data0.key)j-;if(idatai+=P-dataj;while(idatai.keydata0.key)i+;if(idataj-=P-datai;P-datai=P-data0;if(lowi-1)QuickSort(P,i+1,high);/*QuickSort递归调用*/,2023年6月9日,22,快速排序的递归过程可用生成一棵二叉树的过程形象地表示,每棵子树的根结点是各次划分时的支点,,r0r1r2r3r4r5r6r7r8r9r104328397698694515828,2828394,6998515876,初始序列,43,6998515876,一次划分后,2023年6月9日,23,算法分析:
时间复杂度:
在n个记录的待排序列中,一次划分需要约n次关键码比较。
若每次划分的前后两部分数据元素个数基本相等,则需要经过log2n次划分,所以算法时间复杂度为nlog2n,最坏情况下,时间复杂度为O(n2)。
空间复杂度:
快速排序是递归的,每层递归调用的指针和参数均要用栈来存放,递归调用次数与二叉树的深度一致。
存储开销在理想情况下为O(log2n),即树的高度;在最坏情况下,二叉树是一个单支,这时算法的空间复杂度为为O(n)。
2023年6月9日,24,是以降低数据元素的移动次数为排序思路。
9.4.1直接选择排序排序过程:
第一次,选取整个序列中关键字最小的记录与第一个元素交换;第二次,从剩余的n-1个记录中选出关键字最小的记录与第二个记录交换;第i次,则从剩余的n-i+1个记录选出关键字最小的记录与第i个记录交换;直到整个序列按关键码有序。
9.4选择排序,2023年6月9日,25,【例9-4】待排序列352845551968初始状态352845551968i=1192845553568元素19和35交换i=2192845553568元素35和45交换i=3192835554568元素45和55交换i=4182435455568i=5182435455568i=6182435455568,2023年6月9日,26,【算法9.5】直接选择排序voidSelectSort(SL*p)for(i=1;ilength;i+)k=i;for(j=i+1,k=i;jlength;j+)if(p-datak.keyp-dataj.key)k=j;/*t中存放关键码最小记录的下标*/if(i!
=k)/*关键码最小的记录与第i个记录交换*/p-data0=p-datai;p-datai=p-datak;p-datak=p-data0;,2023年6月9日,27,算法分析:
空间复杂度:
一个附加单元的存储空间,所以是O
(1)。
时间复杂度:
该算法使用了循环的嵌套形式,复杂度为n(n+1)/2,所以为O(n2)。
算法是稳定的。
直接选择排序中比较的次数比较多。
9.4.2堆排序(HeapSort)堆排序就是直接选择排序算法的改进算法。
堆的定义:
设有n个元素的序列R1,R2,Rn,其关键字为k1,k2,kn,当且仅当满足下述关系之一时,称之为堆.,2023年6月9日,28,下面讨论小根堆,2023年6月9日,29,堆排序大体分两步处理:
第一步建立堆结构。
先取i=n/2(i是第n个结点的双亲的编号),将以i结点为根的子树调整为堆;然后令i=i-1;再将以i结点为根的子树调整成为堆。
直到i=1为止,初建堆完成。
第二步堆排序。
首先输出堆顶元素,让堆中最后一个元素上移到堆顶位置,然后恢复堆,重复执行输出堆顶元素、堆尾元素移到堆顶和恢复堆的操作,直到全部元素输出完为止。
因此,实现堆排序需解决两个问题:
1.如何将n个元素的序列按关键码建成堆;2.输出堆顶元素后,调整剩余元素成为一个新堆。
2023年6月9日,30,【例9-6】设有8个记录的关键字是53,36,30,91,47,12,24,85,试用堆排序的方法,将这组记录由小到大排序。
第一步:
建立堆结构,其过程如图所示。
2023年6月9日,31,2023年6月9日,32,第二步:
堆排序。
这是反复输出堆顶元素,将堆尾元素上移至堆顶,再调整恢复堆的过程,恢复堆的过程与初建堆中i=1时所进行的调整操作相同。
2023年6月9日,33,2023年6月9日,34,2023年6月9日,35,【算法9.6】堆排序,voidHeapsift(SL*p,ints,intm)/*对p-datas进行调整使其成为小顶堆*/rc=p-datas;j=2*s;while(jdataj.keyp-dataj+1.key)j+;/*i为关键码较小的元素下标*/if(rc.keyp-j.key)p-datas=p-dataj;s=j;j=j*2elsej=m+1;p-datas=rc;/*插入*/*Heapsift*/,2023年6月9日,36,voidHeapSort(SL*h)/*对顺序表*h进行堆排序*/for(i=h-length/2;i=1;i-)/*将h1.length建成堆*/Heapsift(h,i,h-length);for(j=h-length;j=2;j-)rc=h-data1;h-data1=h-dataj;h-dataj=rc;/*堆顶与堆底元素交换*/Heapsift(h,1,j-1);/*对data1.i-1重新调整为堆*/*HeapSort*/,堆排序最坏情况下,时间复杂度为O(nlog2n)。
2023年6月9日,37,归并的含义是将两个或两个以上的有序序列归并成一个新的有序表。
归并排序可分为多路归并排序和两路归并排序。
它既可以用于内部排序,也可以用于外部排序。
一趟两路归并算法的思想(以升序为例):
先用两个指针分别指向两个序列的第一个数据元素,进行比较,取出较小者,然后将其所在序列的指针后移,重复以上过程,直到指针达到序列的末尾,这时将另一个序列的剩余元素依次顺序放到有序序列的后面即可。
9.5归并排序,2023年6月9日,38,将两个有序序列L-datat.m和L-datam+1.n归并为有序序列L1-t.n的过程:
i=t;j=m;k=t;若im或jn,执行;比较L-datai和L-dataj关键字,将较小的存入L1中:
如果L-datai.keydataj.key;L1-datak=L-datai;i+;k+;执行;否则,L1-datak=L-dataj;j+;k+;执行;将尚未处理完的子表中元素存入L1;如果idataim存入L1-datakn;如果jjn存入L1-datakn;合并结束。
2023年6月9日,39,【算法9.7】一趟两路归并排序voidMerge(SL*L,SL*L1,intt,intm,intn)for(i=t,j=m,k=t;idatai.keydataj.key)L1-datak=L-datai;i+;elseL1-datak=L-dataj;j+;/*for*/if(idatakn=L1-dataim-1;if(jdatakn=L1-datajn;/*Merge*/,2023年6月9日,40,【例9-7】有一个序列12,9,44,10,99,61,65,43,76,其两路归并算法的过程:
初始关键字12944109961654376,一趟归并后91210446199436576,二趟归并后91012444361659976,三趟归并后91012434461659976,四趟归并后91012434461657699,2023年6月9日,41,两路归并排序思想:
把序列所含的n个记录看作n个有序的子序列,然后两两归并,得n/2个长度为2或1的有序子序列;再两两归并,以此类推直到得到的子序列长度为n,排序完毕。
算法分析:
空间复杂度为O(n)。
时间复杂度:
对包含n个数据元素的表,将这n个数据元素看作叶子结点,若将两两归并生成的子表看作它们的父结点,则归并过程对应由叶子结点向根结点生成一棵二叉树的过程。
所以归并趟数约等于二叉树的高度-1,即log2n,每趟归并需移动记录n次,故为O(nlog2n)。
2023年6月9日,42,是一种借助于多关键码排序的思想,将单关键码按基数分成“多关键码”进行排序的方法。
多关键字排序的基本过程是首先根据多个关键字分别排序,最后再将其合并到一起。
【例9-8】扑克牌中52张牌,可按花色和面值分成两个字段,其大小关系为:
花色:
方块梅花红心黑心面值:
2345678910JQKA若对扑克牌按花色、面值进行升序排序,得到如下序列:
方块2,3,.,A,梅花2,3,.,A,红心2,3,.,A,黑心2,3,.,A,9.6基数排序,2023年6月9日,43,本节假设记录的关键字为整型。
最低位优先法:
即是首先根据关键字最低位(个位)有效数字进行排序,然后根据次低位(十位)有效数字进行排序,以此类推,直到根据最高位有效数字进行排序,产生一个有序序列。
假设有n个记录,其关键字在0999之间,每位上有效数字在09之间共有10种可能性,则基数为10,在进行“分配”操作时涉及10个队列,即队列的个数与基数相同。
此处关键字最多位数是3,那么需要进行3趟“分配”和“收集”操作。
2023年6月9日,44,【例9-9】对序列248,159,43,970,549,134,585,279,18,53进行基数排序。
2023年6月9日,45,2023年6月9日,46,(f)第三趟按百位数分配,修改结点指针域,将链表中的记录分配到相应链队列中,2023年6月9日,47,算法思路如下:
第一趟“分配”,根据关键字个位有效数字,把所有记录分配到相应的10个队列中去。
f0,e0表示0号队列的头、尾指针;f9,e9表示9号队列的头、尾指针;例如:
关键字549的记录被分配到9号队列。
第一趟收集,把所有非空队列按队列号由小到大的顺序将关键字出队。
此序列关键字的个位已经有序;高位仍处于无序状态。
以后各他趟,分别根据关键字的十位、百位有效数字重复类似第、步的“分配”与“收集”操作,最终将得到一个按照关键字由小到大的序列。
2023年6月9日,48,第一趟“分配”,根据关键字个位有效数字,把所有记录分配到相应的10个队列中去。
f0,e0表示0号队列的头、尾指针;f9,e9表示9号队列的头、尾指针;例如:
关键字549的记录被分配到9号队列。
第一趟收集,把所有非空队列按队列号由小到大的顺序将关键字出队。
此序列关键字的个位已经有序;高位仍处于无序状态。
以后各他趟,分别根据关键字的十位、百位有效数字重复类似第、步的“分配”与“收集”操作,最终将得到一个按照关键字由小到大的序列。
2023年6月9日,49,算法分析:
时间复杂度:
设待排序列含n个记录,d个关键码,关键码的基数为radix,则进行链式基数排序的时间复杂度为O(d(n+radix),其中,一趟分配时间复杂度为O(n),一趟收集时间复杂度为O(radix),共进行d趟分配和收集。
综合比较上述讨论的各种内部排序方法,其性能指标如表9-1所示。
通常从下面二方面衡量排序方法的性能,一方面数据排序期间的运算量,一般考虑关键字的比较次数和记录的平均移动次数;另一方面,数据排序期间所需要的辅助存储空间。
2023年6月9日,50,9.7内部排序的比较,2023年6月9日,51,在应用中,应根据不同情况、不同要求选择较合适的方法,甚至可将多种方法结合使用。
下面几点建议,仅供读者参考。
(1)当待排序的记录数n不大时(约n50),可选用表中前三种排序方法。
它们的时间复杂度虽为O(n2),但方法简单,容易实现。
(2)当n值很大,不强求排序稳定性,并且内存容量不宽余时,应选用快速排序或堆排序。
一般来讲,他们排序速度非常快。
(3)当n值很大,对排序稳定性有要求,并内存容量宽余时,用归并排序最为合适。
2023年6月9日,52,9.8.1外部排序在对大型文件排序时,由于文件很大,不可能将整个文件的所有记录都同时调入内存中进行排序,就要利用外部排序技术来完成排序。
外部排序方法最常用的是多路归并法。
这种方法基本要经过两个步骤:
第一步,按可按内存大小,将外存上含n个记录的文件分成若干个长度为k的子文件或段(segment),依次读入内存并利用有效的内部排序方法对它们进行排序,并将排序结果重新写入外存。
通常称这些有序子文件为归并段或顺串;,9.8外部排序,2023年6月9日,53,假设有一个含10000个记录的文件,首先通过10次内部排序得到10个初始归并段A1A10,其中每一段都含1000个记录。
然后对它们作如图9-12所示的两两归并,直至得到一个有序文件为止。
将两个有序段归并成一个有序段的过程,若在内存中进行,前面讨论的两路归并排序中的Merge函数便可实现此归并。
第二步,对这些归并段进行逐趟归并,使归并段(有序子文件)逐渐由小到大,最后在外存上形成一个排序文件。
2023年6月9日,54,一般情况下,外部排序所需总时间=内部排序所需时间mtis+外存信息读写的时间dtio+内部归并排序所需时间sutmg,其中:
tis是为得到一个初始归并段进行的内部排序所需时间的均值;tio是进行一次外存读/写时间的均值;utmg是对u个记录进行内部归并所需时间;m为经过内部排序之后得到的初始归并段的个数;s为归并的趟数;d为总的读/写次数。
由此,上例10000个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 排序 课件
![提示](https://static.bingdoc.com/images/bang_tan.gif)