《数据库第9章1ppt课件》由会员分享，可在线阅读，更多相关《数据库第9章1ppt课件（11页珍藏版）》请在金锄头文库上搜索。
1、9.1 9.1 概述概述9.2 9.2 插入排序插入排序9.3 9.3 交换排序交换排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 基数排序基数排序第第9 9章章 内部排序内部排序9.1 9.1 概述概述1. 什么是排序？什么是排序？ 将一将一组杂乱无章的数据按一定的乱无章的数据按一定的规律依次律依次陈列起来。列起来。 2. 排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按关键字排序按关键字排序3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？时间效效率率排排序序速速度度即即排排序序所所破破费的的全全部部比比较次次数数空空间效率效率占
2、内存占内存辅助空助空间的大小的大小稳定定性性假假设两两个个记录A A和和B B的的关关键字字值相相等等，但但排排序序后后A A、B B的的先先后后次次序序坚持持不不变，那那么么称称这种种排排序序算算法是法是稳定的。定的。 便于便于查找！找！4. 什么叫内部排序？什么叫外部排序？什么叫内部排序？什么叫外部排序？ 假假设待排序待排序记录都在内存中，称都在内存中，称为内部排序；内部排序；假假设待排序待排序记录一部分在内存，一部分在外存，一部分在内存，一部分在外存，那么称那么称为外部排序。外部排序。注：外部排序注：外部排序时，要将数据分批，要将数据分批调入内存来排序，中入内存来排序，中间结果果还要及要
3、及时放入外存，放入外存，显然外部排序要复然外部排序要复杂得多。得多。 5.5.待排序待排序记录在内存中怎在内存中怎样存存储和和处置？置？ 顺序排序序排序排序排序时直接挪直接挪动记录； 链表排序表排序排序排序时只挪只挪动指指针； 地址排序地址排序排序排序时先挪先挪动地址，最后再挪地址，最后再挪动记录。注：地址排序中可以增注：地址排序中可以增设一一维数数组来来专门存放存放记录的地址。的地址。6. 内部排序的算法有哪些？内部排序的算法有哪些？按排序的按排序的规那么不同，可分那么不同，可分为5类：插入排序插入排序交交换排序重点是快速排序排序重点是快速排序选择排序排序归并排序并排序基数排序基数排序d关键
4、字的位数关键字的位数(长度长度)按排序算法的按排序算法的时间复复杂度不同，可分度不同，可分为3类：简单的排序算法：的排序算法：时间效率低，效率低，O(n2)先先进的排序算法的排序算法: 时间效率高，效率高，O( nlog2n )基基 数数 排排 序序 算法：算法：时间效率高，效率高，O( dn)9.2 9.2 插入排序插入排序插入排序的根本思想是：插入排序的根本思想是：插入排序的根本思想是：插入排序的根本思想是：插入排序有多种插入排序有多种详细实现算法：算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 32-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希希尔排
5、序排序 每步将一个待排序的每步将一个待排序的每步将一个待排序的每步将一个待排序的对对象，象，象，象，按其关按其关按其关按其关键码键码大小，插入到前面曾大小，插入到前面曾大小，插入到前面曾大小，插入到前面曾经经排好序的一排好序的一排好序的一排好序的一组对组对象象象象的适当位置上，直到的适当位置上，直到的适当位置上，直到的适当位置上，直到对对象全部插入象全部插入象全部插入象全部插入为为止。止。止。止。简简言之，言之，言之，言之，边边插入插入插入插入边边排序，保排序，保排序，保排序，保证证子序列中随子序列中随子序列中随子序列中随时时都是排好序的。都是排好序的。都是排好序的。都是排好序的。小改良小改良
6、大改良大改良1) 1) 直接插入排序直接插入排序直接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例1 1：关：关键字序列字序列T=T=1313，6 6，3 3，3131，9 9，2727，5 5，1111， 请写出直接插入排序的中写出直接插入排序的中间过程序列。程序列。【13】, 6, 3, 31, 9, 27, 5, 11【6, 13】, 3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3, 6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】
7、, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6, 9, 11，13，27, 31】 在已构成的有序表中在已构成的有序表中线性性查找，并在找，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移。移。最简单的排序法！最简单的排序法！最简单的排序法！最简单的排序法！例例1 1：关：关键字序列字序列T= T= 2121，2525，4949，25*25*，1616，0808，请写出直接插入排序的写出直接插入排序的详细实现过程。程。* *表示后一个表示后一个2525i=1i=121212525494925*25*161608080 1 2
8、 3 4 5 6哨哨兵兵2121i=2i=2i=3i=3i=5i=5i=4i=4i=6i=62525494925*25*25*494916161625*25*0808084949解：假解：假设该序列已存入一序列已存入一维数数组r7r7中，将中，将r0r0作作为哨兵哨兵TempTemp。那么程序。那么程序执行行过程程为：21212525494925*25*2121初初态：1616494925*25*2525212116160808完成!时间效率：效率： 由于在最坏情况下，一切元素的比由于在最坏情况下，一切元素的比较次数次数总和和为01n-1)O(n2)。其他情况下也要思索。其他情况下也要思索挪挪
9、动元素的次数。元素的次数。 故故时间复复杂度度为O(n2) 空空间效率：效率：仅占用占用1个个缓冲冲单元元O1算法的算法的稳定性：由于定性：由于25*排序后依然在排序后依然在25的后面的后面稳定定5 5希希希希尔尔shellshell排序排序排序排序根本思想：先将整个待排根本思想：先将整个待排根本思想：先将整个待排根本思想：先将整个待排记录记录序列分割成假序列分割成假序列分割成假序列分割成假设设干子序列干子序列干子序列干子序列, , , ,分分分分别进别进展直接插入排序，待整个序列中的展直接插入排序，待整个序列中的展直接插入排序，待整个序列中的展直接插入排序，待整个序列中的记录记录“根本有序根
10、本有序根本有序根本有序时时，再，再，再，再对对全体全体全体全体记录进记录进展一次直接插入排序。展一次直接插入排序。展一次直接插入排序。展一次直接插入排序。技巧：子序列的构成不是技巧：子序列的构成不是技巧：子序列的构成不是技巧：子序列的构成不是简单简单地地地地“逐段分割，而是将相逐段分割，而是将相逐段分割，而是将相逐段分割，而是将相隔某个增量隔某个增量隔某个增量隔某个增量dkdkdkdk的的的的记录组记录组成一个子序列成一个子序列成一个子序列成一个子序列, , , ,让让增量增量增量增量dkdkdkdk逐趟逐趟逐趟逐趟缩缩短短短短例如依次取例如依次取例如依次取例如依次取5,3,15,3,15,3
11、,15,3,1，直到，直到，直到，直到dkdkdkdk1 1 1 1为为止。止。止。止。优优点：点：点：点：让让关关关关键键字字字字值值小的元素能很快前移，且序列假小的元素能很快前移，且序列假小的元素能很快前移，且序列假小的元素能很快前移，且序列假设设根根根根本有序本有序本有序本有序时时，再用直接插入排序，再用直接插入排序，再用直接插入排序，再用直接插入排序处处置，置，置，置，时间时间效率会高很多。效率会高很多。效率会高很多。效率会高很多。又称减少增量排序又称减少增量排序又称减少增量排序又称减少增量排序38例：关键字序列例：关键字序列 T=(49，38，65，97, 76, 13, 27, 4
12、9*，55, 04，请写出希尔排序的详细实现过程。，请写出希尔排序的详细实现过程。0123456789104938659776132749*5504初初态：第第1趟趟 (dk=5)第第2趟趟 (dk=3)第第3趟趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 算法分析：开算法分析：开场时dk dk 的的值较大，子序列中的大，子序列中的对象象较少，排序速度少，排序速度较快；随
13、着排序快；随着排序进展，展，dk dk 值逐逐渐变小，子序列中小，子序列中对象个数象个数逐逐渐变多，由于前面任多，由于前面任务的根底，大多数的根底，大多数对象已根本有序，象已根本有序，所以排序速度依然很快。所以排序速度依然很快。riri时间效率：时间效率：空空间效率：效率：O O1 1由于由于仅占用占用1 1个个缓冲冲单元元算法的算法的稳定性：不定性：不稳定定由于由于49*49*排序后却到了排序后却到了4949的前面的前面O(n1.25O(n1.25O(n1.25O(n1.25O O O O1.6n1.251.6n1.251.6n1.251.6n1.25由由由由阅历阅历公式得公式得公式得公式得
14、到到到到1. 欲将序列欲将序列Q, H, C, Y, P, A, M, S, R, D, F, X中的关中的关键码按按字母升序重排，那么初始步字母升序重排，那么初始步长为4的希的希尔排序一趟的排序一趟的结果是？果是？答：原始序列：答：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：一趟后：课堂堂练习：P,Q,R,A,D,H,C,F,M,S,X ,Y原始序列：原始序列： 256，301，751，129，937，863，742，694，076，438( (取取取取dk=5, 3, 1)dk=5, 3, 1)256256，301301，751751
15、，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，74
16、2742，751751，129129，937937第第1趟趟dk=5第第2趟趟dk=3第第3趟趟dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863
17、，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，9379372. 以以关关键字字序序列列256，301，751，129，937，863，742，694，076，438为例例，写写出出执行行希希尔排排序序取取dk=5,3,1算法的各趟排序算法的各趟排序终了了时，关，关键字序列的形状。字序列的形状。
