数据结构 李云清 杨庆红 揭安全.pptx
《数据结构 李云清 杨庆红 揭安全.pptx》由会员分享,可在线阅读,更多相关《数据结构 李云清 杨庆红 揭安全.pptx(50页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第10章章 内排序内排序 排序是数据处理过程中经常使用的一种重要的运排序是数据处理过程中经常使用的一种重要的运算,排序的方法有很多种,本章主要讨论内排序的各算,排序的方法有很多种,本章主要讨论内排序的各种算法,并对每个排序算法的时间和空间复杂性以及种算法,并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。算法的稳定性等进行了讨论。10.1 排序的基本概念 假设一个文件是由假设一个文件是由n n个记录个记录R R1 1,R R2 2,R Rn n组成,组成,所谓排序就是以记录中某个所谓排序就是以记录中某个(或几个或几个)字段值不减字段值不减(或或不增不增)的次序将这的次序将这n
2、n个记录重新排列,称该字段为排个记录重新排列,称该字段为排序码。能唯一标识一个记录的字段称为关键码,关序码。能唯一标识一个记录的字段称为关键码,关键码可以作为排序码,但排序码不一定要是关键码。键码可以作为排序码,但排序码不一定要是关键码。第1页/共50页 按排序过程中使用到的存储介质来分,可以将排按排序过程中使用到的存储介质来分,可以将排序分成序分成两大类两大类:内排序和外排序内排序和外排序。内排序内排序是指在排序过程中所有数据均放在内存中是指在排序过程中所有数据均放在内存中处理,不需要使用外存的排序方法。而对于数据量很处理,不需要使用外存的排序方法。而对于数据量很大的文件,在内存不足的情况下
3、,则还需要使用外存,大的文件,在内存不足的情况下,则还需要使用外存,这种排序方法称为这种排序方法称为外排序外排序。排序码相同的记录,若经过排序后,这些记录排序码相同的记录,若经过排序后,这些记录仍保持原来的相对次序不变,称这个排序算法是仍保持原来的相对次序不变,称这个排序算法是稳稳定的定的。否则,称为。否则,称为不稳定的排序算法不稳定的排序算法。第2页/共50页评价排序算法优劣的标准评价排序算法优劣的标准 :首先考虑算法执行所需的时间,这主要是用执行首先考虑算法执行所需的时间,这主要是用执行过程中的比较次数和移动次数来度量;过程中的比较次数和移动次数来度量;其次考虑算法执行所需要的附加空间。其
4、次考虑算法执行所需要的附加空间。当然,保证算法的正确性是不言而喻的,可读性等当然,保证算法的正确性是不言而喻的,可读性等也是要考虑的因素。也是要考虑的因素。第3页/共50页排序算法如未作特别的说明,使用的有关定义如下排序算法如未作特别的说明,使用的有关定义如下 :/*/*常见排序算法的头文件,文件名常见排序算法的头文件,文件名table.h*/table.h*/#define MAXSIZE 100 /*#define MAXSIZE 100 /*文件中记录个数的最大值文件中记录个数的最大值*/typedef int keytype;/*typedef int keytype;/*定义排序码类
5、型为整数类型定义排序码类型为整数类型*/typedef struct typedef struct keytype key;keytype key;/*/*此处还可以定义记录中除排序码外的其它域此处还可以定义记录中除排序码外的其它域*/recordtype;/*recordtype;/*记录类型的定义记录类型的定义*/typedef struct typedef struct recordtype rMAXSIZE+1;recordtype rMAXSIZE+1;int length;/*int length;/*待排序文件中记录的个数待排序文件中记录的个数*/table;/*table;/*
6、待排序文件类型待排序文件类型*/为了方便,r0一般不用于存放排序码,在一些排序算法中它可以用来作为中间单元存放临时数据。length域是待排序的记录个数,它必须不大于MAXSIZE,这样,第1length个记录的排序码分别存于r1.keyrlength.key中 第4页/共50页10.2 插入排序插入排序 插入排序的基本方法是插入排序的基本方法是:将待排序文件中的记录,将待排序文件中的记录,逐个地按其排序码值的逐个地按其排序码值的大小插入到目前已经排好序的若干个记录组成的文件中大小插入到目前已经排好序的若干个记录组成的文件中的适当位置,并保持新文件有序。的适当位置,并保持新文件有序。10.2.
7、1 直接插入排序 直接插入排序算法的思路是直接插入排序算法的思路是:初始可认为文件中的初始可认为文件中的第第1 1个记录己排好序,然后将第个记录己排好序,然后将第2 2个到第个到第n n个记录依次插个记录依次插入已排序的记录组成的文件中。在对第入已排序的记录组成的文件中。在对第i i个记录个记录R Ri i进行进行插入时,插入时,R R1 1,R R2 2,R Ri-1i-1已排序,将记录已排序,将记录R Ri i的排序码的排序码keykeyi i与已经排好序的排序码从右向左依次比较,找到与已经排好序的排序码从右向左依次比较,找到R Ri i应插入的位置,将该位置以后直到应插入的位置,将该位置
8、以后直到R Ri-1i-1各记录顺序后移,各记录顺序后移,空出该位置让空出该位置让R Ri i插入。插入。第5页/共50页一组记录的排序码分别为一组记录的排序码分别为:312312,126126,272272,226226,2828,165165,123 123 初初始始时时将将第第1 1个个排排序序码码作作为为已已经经排排好好序序的的,把把排排好好序序的的数数据据记记录录放放入入中中括括号号 中中,表表示示有有序序的的文文件件,剩剩下下的在中括号外,如下所示:的在中括号外,如下所示:312312,126126,272272,226226,2828,165165,123 123 设设前前3 3
9、个个记记录录的的排排序序码码已已重重新新排排列列有有序序,构构成成一一个个含含有有3 3个记录的有序文件个记录的有序文件:126126,272272,312312,226226,2828,165165,123 123 现在要将第现在要将第4 4个排序码个排序码226226插入插入 !第6页/共50页126126,272272,312312,226226,2828,165165,123123现在要将第现在要将第4 4个排序码个排序码226226插入插入 !将待插入的排序码将待插入的排序码226226和已经有序的最后一个排和已经有序的最后一个排序码序码312312比较,因为待插入的排序码比较,因为
10、待插入的排序码226226小于小于312312,所,所以以226226肯定要置于肯定要置于312312的前面,至于是否就是置于的前面,至于是否就是置于312312的前一个位置,此时还不能确定,需要继续向左比较;的前一个位置,此时还不能确定,需要继续向左比较;将所有大于待插入排序码将所有大于待插入排序码226226的那两个排序码的那两个排序码312312和和272272依次后移一个位置,在空出的位置插入待依次后移一个位置,在空出的位置插入待排序的排序码排序的排序码226226,得一含有,得一含有4 4个记录的有序文件:个记录的有序文件:126126,226226,272272,312312,28
11、28,165165,123 123 第7页/共50页需要注意的是,当待插入排序码小于所有已排序的需要注意的是,当待插入排序码小于所有已排序的排序码时,如在插入第排序码时,如在插入第5 5个值个值2828时:时:126126,226226,272272,312312,2828,165165,123123算法设计的时候如处理?算法设计的时候如处理?方法之一:设置“哨兵”第8页/共50页void insertsort(table*tab)void insertsort(table*tab)int i,j;int i,j;for(i=2;ilength;i+)/*for(i=2;ilength;i+)
12、/*依次插入从第依次插入从第2 2个开始的所有元素个开始的所有元素*/j=i-1;j=i-1;tab-r0.key=tab-ri.key;/*tab-r0.key=tab-ri.key;/*设置哨兵,准备找插入位置设置哨兵,准备找插入位置*/while(tab-r0.keyrj.key)/*while(tab-r0.keyrj.key)/*找插入位置并后移找插入位置并后移*/tab-rj+1.key=tab-rj.key;/*tab-rj+1.key=tab-rj.key;/*后移后移*/j=j-1;/*j=j-1;/*继续向前(左)查找继续向前(左)查找*/tab-rj+1.key=tab-
13、r0.key;tab-rj+1.key=tab-r0.key;/*/*插插入入第第i i个个元元素素的的副副本本,即即前前面面设设置置的的哨哨兵兵*/算法算法10.1 10.1 直接插入排序算法直接插入排序算法 第9页/共50页设设待待排排序序的的7 7记记录录的的排排序序码码为为312312,126126,272272,226226,2828,165165,123123,直直接接插插入入排排序序算法的执行过程如图算法的执行过程如图10.210.2所示。所示。哨兵哨兵 排序码排序码 312 312,126126,272272,226226,2828,165165,123123初始初始 ()()
14、312312,126126,272272,226226,2828,165165,123123i=2i=2:(126126)126126,312312,272272,226226,2828,165165,123123i=3i=3:(272272)126126,272272,312312,226226,2828,165165,123123i=4i=4:(226226)126126,226226,272272,312312,2828,165165,123123i=5i=5:(2828)2828,126126,226226,272272,312312,165165,123123i=6i=6:(1651
15、65)2828,126126,165165,226226,272272,312312,123123i=7i=7:(123123)2828,123123,126126,165165,226226,272272,312312图图10.2 10.2 直接插入排序算法执行过程示意图直接插入排序算法执行过程示意图 第10页/共50页直接插入排序算法执行时间的分析:直接插入排序算法执行时间的分析:最好的情况最好的情况 :即初始排序码开始就是有序的情况下,因为当插即初始排序码开始就是有序的情况下,因为当插入第入第i i个排序码时,该算法内循环个排序码时,该算法内循环whilewhile只进行一次条件只进行一
16、次条件判断而不执行循环体,外循环共执行判断而不执行循环体,外循环共执行n-1n-1次,其循环体次,其循环体内不含内循环每次循环要进行内不含内循环每次循环要进行2 2次移动操作,所以在最次移动操作,所以在最好情况下,直接插入排序算法的比较次数为好情况下,直接插入排序算法的比较次数为(n-1)(n-1)次,次,移动次数为移动次数为2*(n-1)2*(n-1)次。次。第11页/共50页最坏情况最坏情况 :即初始排序码开始是逆序的情况下,因为当插入即初始排序码开始是逆序的情况下,因为当插入第第i i个排序码时,该算法内循环个排序码时,该算法内循环whilewhile要执行要执行i i次条件判次条件判断
17、,循环体要执行断,循环体要执行i-li-l次,每次要移动次,每次要移动1 1个记录,外循个记录,外循环共执行环共执行n-1n-1次,其循环体内不含内循环每次循环要次,其循环体内不含内循环每次循环要进行进行2 2次移动操作,所以在最坏情况下,比较次数为次移动操作,所以在最坏情况下,比较次数为(1+2+n)*(n-1)(1+2+n)*(n-1),移动次数为,移动次数为(1+2+2+2+n+2)*(n-1)(1+2+2+2+n+2)*(n-1)。假设待排序文件中的记录。假设待排序文件中的记录以各种排列出现的概率相同,因为当插入第以各种排列出现的概率相同,因为当插入第i i个排序码个排序码时,该算法内
18、循环时,该算法内循环whilewhile平均约要执行平均约要执行i/2i/2次条件判断,次条件判断,循环体要执行(循环体要执行(i-li-l)/2/2次,外循环共执行次,外循环共执行n-1n-1次,所以次,所以平均比较次数约为平均比较次数约为(2+3+n)/2*(n-1)(2+3+n)/2*(n-1),平均移动次,平均移动次数为数为(n-1)*(2+1+3+1+n+1)/2(n-1)*(2+1+3+1+n+1)/2,也即直接插入排序,也即直接插入排序算法的时间复杂度为算法的时间复杂度为O(nO(n2 2)。第12页/共50页10.2.2 二分法插入排序二分法插入排序 二分法插入排序的思想:二分
19、法插入排序的思想:根据插入排序的基本思想,在找第根据插入排序的基本思想,在找第i i个记录的插入个记录的插入位置时,前位置时,前i-li-l个记录已排序,将第个记录已排序,将第i i个记录的排序码个记录的排序码keyikeyi和已排序的前和已排序的前i-1i-1个的中间位置记录的排序码进行个的中间位置记录的排序码进行比较,如果比较,如果keyikeyi小于中间位置记录排序码,则可以在小于中间位置记录排序码,则可以在前半部继续使用二分法查找,否则在后半部继续使用前半部继续使用二分法查找,否则在后半部继续使用二分法查找,直到查找范围为空,即可确定二分法查找,直到查找范围为空,即可确定keyikey
20、i的插的插入位置。入位置。第13页/共50页void binarysort(table*tab)void binarysort(table*tab)int i,j,left,right,mid;int i,j,left,right,mid;for(i=2;ilength;i+)/*for(i=2;ilength;i+)/*依次插入从第依次插入从第2 2个开始的所有元素个开始的所有元素*/tab-r0.key=tab-ri.key;/*tab-r0.key=tab-ri.key;/*保存待插入的元素保存待插入的元素*/left=1;right=i-1;/*left=1;right=i-1;/*设
21、置查找范围的左、右位置值设置查找范围的左、右位置值*/while(left=right)/*while(leftri.keyrmid.key)right=mid-1;if(tab-ri.keyrmid.key)right=mid-1;else left=mid+1;else left=mid+1;/*/*插入位置为插入位置为left*/left*/for(j=i-1;j=left;j-)tab-rj+1.key=tab-rj.key;/*for(j=i-1;j=left;j-)tab-rj+1.key=tab-rj.key;/*后移后移,空出插入位置空出插入位置*/tab-rleft.key=
22、tab-r0.key;/*tab-rleft.key=tab-r0.key;/*插入第插入第i i个元素的副本个元素的副本*/*/*算法算法10.2 10.2 二分法插入排序算法二分法插入排序算法*/第14页/共50页 设待排序的设待排序的7 7记录的排序码为记录的排序码为312312,126126,272272,226226,2828,165165,123123,在前,在前6 6个记录已经排序的情况个记录已经排序的情况下,使用二分法插入排序算法插入第下,使用二分法插入排序算法插入第7 7个记录的排序码个记录的排序码123123的执行过程示意如图的执行过程示意如图10.310.3所示(见书本)
23、。所示(见书本)。二分法插入排序算法,在查找第二分法插入排序算法,在查找第i i个记录的插入位个记录的插入位置时,每执行一次置时,每执行一次whilewhile循环体,查找范围缩小一半,循环体,查找范围缩小一半,和直接插入排序的比较次数对比,二分法插入的比较和直接插入排序的比较次数对比,二分法插入的比较次数少于直接插入排序的最多比较次数,而一般要多次数少于直接插入排序的最多比较次数,而一般要多于直接插入排序的最少比较次数。总体上讲,当于直接插入排序的最少比较次数。总体上讲,当n n较较大时,二分法插入排序的比较次数远少于直接插入排大时,二分法插入排序的比较次数远少于直接插入排序的平均比较次数,
24、但二者所要进行的移动次数相等,序的平均比较次数,但二者所要进行的移动次数相等,故二分法插入排序的时间复杂度也是故二分法插入排序的时间复杂度也是O(nO(n2 2),所需的附,所需的附加存储空间为一个记录空间。加存储空间为一个记录空间。第15页/共50页10.2.3 表插入排序表插入排序 二分法插入排序比较次数通常比直接插入排序的二分法插入排序比较次数通常比直接插入排序的比较次数少,但移动次数相等。表插入排序将在不进比较次数少,但移动次数相等。表插入排序将在不进行记录移动的情况下,利用存储结构有关信息的改变行记录移动的情况下,利用存储结构有关信息的改变来达到排序的目的。来达到排序的目的。给每个记
25、录附设一个所谓的指针域给每个记录附设一个所谓的指针域linklink,它的类型,它的类型为整型,为整型,表插入排序的思路:表插入排序的思路:在插入第在插入第i i个记录个记录R Ri i时,时,R R1 1,R R2 2,R Ri-1i-1已经通过各自的指针域已经通过各自的指针域linklink按排序码按排序码不减的次序连接成一个(静态链)表,将记录不减的次序连接成一个(静态链)表,将记录R Ri i的排的排序码序码keykeyi i与表中已经排好序的排序码从表头向右、或与表中已经排好序的排序码从表头向右、或称向后依次比较,找到称向后依次比较,找到R Ri i应插入的位置,将其插入在应插入的位
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 李云清 杨庆红 揭安全 安全
限制150内