《计算机应用基础课件1.6排序.ppt》由会员分享，可在线阅读，更多相关《计算机应用基础课件1.6排序.ppt（46页珍藏版）》请在第壹文秘上搜索。
1、第第 1 章章 数据结构数据结构 主要内容1.1 基本数据结构与算法基本数据结构与算法 1.2 线性表线性表 1.3 栈和队列栈和队列1.4 树和二叉树树和二叉树 1.5 查找查找1.6 排序排序ABCDEFG10658651.6 排序 排序又称分类，是计算机程序设计中一个重要运算，它的功能是将一组任意序列的数据元素，进行按关键字由大到小的顺序（降序）排列或按由小到大的顺序（升序）排列。排序的对象：这些数据元素可以是数值型，也可以为字符排序的对象：这些数据元素可以是数值型，也可以为字符型。若为数值型，则按数值大小排列；若为字符型，则按型。若为数值型，则按数值大小排列；若为字符型，则按其其ASC
2、IIASCII码的顺序排列。码的顺序排列。排序的依据：在实际应用中，参加排序的数据元素有时不排序的依据：在实际应用中，参加排序的数据元素有时不是单个数据项，而是由多个数据项组成的记录。此时排序应是单个数据项，而是由多个数据项组成的记录。此时排序应按照关键字的大小进行。所谓关键字是指记录中的某个数据按照关键字的大小进行。所谓关键字是指记录中的某个数据项，用它可以标识一个记录。若此关键字可以唯一地标识一项，用它可以标识一个记录。若此关键字可以唯一地标识一个记录，则称此关键字个记录，则称此关键字为主关键字为主关键字；反之，把用以识别若干；反之，把用以识别若干记录的关键字称为记录的关键字称为次关键字。
3、次关键字。学号学号姓名姓名系别系别住址住址电话电话981111李洪李洪机械机械六舍六舍5371111982111王刚王刚电子电子四舍四舍5372111983211王将王将计算机计算机五舍五舍5373211983212张强张强机械机械六舎六舎5372221排序的稳定性：排序的稳定性：在待排序的记录中，若存在多个关键在相同在待排序的记录中，若存在多个关键在相同 的记录，经过排序后，这些具有相同关键在的记录，经过排序后，这些具有相同关键在 的记录之间的相对次序发生变化，则称这种的记录之间的相对次序发生变化，则称这种 排序方法是稳定的；否则，是不稳定的。排序方法是稳定的；否则，是不稳定的。排序的分类：
4、内部排序与外部排序排序的分类：内部排序与外部排序 内部排序内部排序:整个排序过程整个排序过程完全在内存中完全在内存中进行进行.外部排序外部排序:由于待排序记录数据量太大由于待排序记录数据量太大,内存无法容纳内存无法容纳 全部数据全部数据,排序需要排序需要借助外部存储设备借助外部存储设备才能才能 完成完成.排序算法评价：排序算法评价：算法执行时间算法执行时间(最好、最差及平均情况最好、最差及平均情况)、需要附加空间大小、需要附加空间大小1.6 排序插入排序的基本思想：插入排序的基本思想：1.6.2 插入排序插入排序插入排序三种方法插入排序三种方法1.直接排序直接排序:认可第认可第1 1个记录已排
5、好序，然后将第个记录已排好序，然后将第2 2个到第个到第n n个个记录依次插入到前面已排好序的记录组成的文件中。记录依次插入到前面已排好序的记录组成的文件中。2.折半插入排序折半插入排序:折半插入排序在寻找插入位置时，不是逐个折半插入排序在寻找插入位置时，不是逐个比较而是利用比较而是利用折半查找的原理寻找插入位置折半查找的原理寻找插入位置。待排序元素越。待排序元素越多，改进效果越明显。多，改进效果越明显。3.希尔排序希尔排序:将整个无序序列分割成若干个子序列分别进行直将整个无序序列分割成若干个子序列分别进行直接插入排序接插入排序.将将待排序待排序文件中的记录，逐个按其排序码值的大小插文件中的记
6、录，逐个按其排序码值的大小插入到已入到已排好序排好序的若干个记录组成的文件中的适当位置，保的若干个记录组成的文件中的适当位置，保持新文件有序。持新文件有序。1.直接插入排序直接插入排序:思路：思路：认可第认可第1 1个记录已排好序，然后将第个记录已排好序，然后将第2 2个到第个到第n n个记录个记录依次插入到前面已排好序的记录组成的文件中。依次插入到前面已排好序的记录组成的文件中。具体过程具体过程(第第i i个记录个记录R Ri i插入到前面插入到前面i-1i-1个已排好序的记录中个已排好序的记录中)将将R Ri i的排序码与前面已排好序的排序码从的排序码与前面已排好序的排序码从右向左右向左依
7、次比依次比较，找到较，找到R Ri i应插入的位置；将该位置以后直到应插入的位置；将该位置以后直到R Ri-1i-1各记录顺各记录顺序后移序后移,空出位置插入空出位置插入R Ri i。1.6.2 插入排序插入排序 直接插入排序直接插入排序:次数次数i r0 r1 r2 r3 r4 r5 r6 r7 r8 (49)39 66 96 76 11 37 50 (39 49)66 96 76 11 37 50i=239(39 49 66)96 76 11 37 50i=366(39 49 66 96)76 11 37 50i=496(39 49 66 76 96)11 37 50i=576(11 39
8、 49 66 76 96)37 50i=611(11 37 39 49 66 76 96)50i=737(11 37 39 49 50 66 76 96)i=850对于有对于有n个个数据元素的数据元素的待排序列，待排序列，插入操作要插入操作要进行进行n-1次次./*对对N个整数进行升序排序个整数进行升序排序*/for(i=1;i=0;k-)/寻找插入位置寻找插入位置if(aiak)break;/插入到第插入到第k个位置的后面个位置的后面 temp=ai;for(j=i-1;jk;j-)/向后移动向后移动 aj+1=aj;aj+1=temp;./*改进前面的算法改进前面的算法*/for(i=1;
9、i=0&tempaj若降序排序，若降序排序，则：则：1.直接插入排序直接插入排序:时效分析时效分析111321niini 最好情况最好情况:初始排序码已经有序。共比较初始排序码已经有序。共比较n-1次，移动次，移动0次。次。最坏情况最坏情况:待排序序列完全逆序。比较和移动均为待排序序列完全逆序。比较和移动均为n(n-1)/2次。次。平均情况平均情况:比较和移动次数均约为比较和移动次数均约为n2/4，时间复杂度为，时间复杂度为O(n2)。2)1(nn1.6.2 插入排序插入排序该算法适合该算法适合于于n n 较小的较小的情况，时间情况，时间复 杂 度 为复 杂 度 为O(nO(n2 2).).2
10、 2、折半插入排序、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是折半插入排序在寻找插入位置时，不是逐个比较而是利用折利用折半查找的原理寻找插入位置半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。待排序元素越多，改进效果越明显。例：有例：有6 6个记录，前个记录，前5 5 个已排序的基础上，对第个已排序的基础上，对第6 6个记录排序个记录排序。15 27 36 53 69 42 low mid high (4236,后半后半)15 27 36 53 69 42 low high mid (4253,前半前半)15 27 36 53 69 42 high low(high
11、 tj,tk=1。(2)按增量序列个数按增量序列个数k，对序列进行，对序列进行k趟排序。趟排序。(3)每趟排序，根据对应的增量每趟排序，根据对应的增量ti，将序列分割成若干长，将序列分割成若干长度为度为m的子序列，分别对各子表直接插入排序。增的子序列，分别对各子表直接插入排序。增量量ti逐次减小，逐次减小，tk=1时，再对全部元素进行一次直时，再对全部元素进行一次直接插入排序即可完成。接插入排序即可完成。1.6.2 插入排序插入排序举例举例:有一个含有有一个含有14个数的序列个数的序列,使用希而排序进行升序排序使用希而排序进行升序排序 (39,80,76,41,13,29,50,78,30,1
12、1,100,7,41,86)取增量：取增量：5，3，1h=539 80 76 41 13 29 50 78 30 11 100 7 41 86(R1,R6,R11)39 29 100(R2,R7,R12)80 50 7(R3,R8,R13)76 78 41(R4,R9,R14)41 30 86(R5,R10)13 11则子序列：则子序列：39，29，100，80，50，7，76，78，41，41，30，86，13，11R1,R2,R3,R4,R5,R6,R7,R8,R9,R10 R11,R12,R13,R14h=539 80 76 41 13 29 50 78 30 11 100 7 41 8
13、6子序列：子序列：39，29，100，80，50，7，76，78，41，41，30，86，13，11R1,R2,R3,R4,R5,R6,R7,R8,R9,R10 R11,R12,R13,R14 29 39 100 7 50 80 41 76 78 30 41 86 11 13因此第一趟排序结果如下因此第一趟排序结果如下:29 7 41 30 11 39 50 76 41 13 100 80 78 86对每个序列进行直接插入排序对每个序列进行直接插入排序:h=3 29 7 41 30 11 39 50 76 41 13 100 80 78 8629 30 50 13 78 7 11 76 100
14、 86 41 39 41 80分别对以上分别对以上3个子序列个子序列,即即29，30，50，13，78，7，11，76，100，86，41，39，41，80进行直接插入排序进行直接插入排序,13 7 39 29 11 41 30 76 41 50 86 80 78 100(R1,R4,R7,R10,R13)(R2,R5,R8,R11,R14)(R3,R6,R9,R12)R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R1413 29 30 50 78 7 11 76 86 100 39 41 41 80第二趟最终结果：第二趟最终结果：第一趟排序结果第一趟排
15、序结果13 7 39 29 11 41 30 76 41 50 86 80 78 100h=1 序列基本有序，对其进行直接插入排序序列基本有序，对其进行直接插入排序,第三趟最终结果：第三趟最终结果：7 11 13 29 30 39 41 41 50 76 78 80 86 100第二趟最终结果：第二趟最终结果：3.希尔希尔排序排序特点：特点：每一遍以不同间隔距离插入排序。每一遍以不同间隔距离插入排序。h h较大时移动数据元素较大时移动数据元素是跳跃式进行。子序列每一次比较可能移去多个逆序是跳跃式进行。子序列每一次比较可能移去多个逆序(直接插入直接插入排序每次比较只能移去一个排序每次比较只能移去
16、一个)。效率较高。最后一次排序。效率较高。最后一次排序(h=1)(h=1)时，时，已基本有序，不需要多少移动。故其时间复杂度较直接插入排序已基本有序，不需要多少移动。故其时间复杂度较直接插入排序低。低。数学难题：数学难题：如何选取增量序列才能有最好的排序效果，至今未完如何选取增量序列才能有最好的排序效果，至今未完整解决。但注意：增量序列中除整解决。但注意：增量序列中除1 1外没有公因子，且最后一个增外没有公因子，且最后一个增量序列必须为量序列必须为1 1。时效分析时效分析:很难。比较次数与移动次数依赖于增量序列的选取，很难。比较次数与移动次数依赖于增量序列的选取，特定情况下可以估计特定情况下可以估计.1.6.2 插入排序插入排序 对待排序记录两两比较排序码，不满足排序对待排序记录两两比较排序码，不满足排序顺序则顺序则交换交换。直到任何两个记录排序码满足排序。直到任何两个记录排序码满足排序要求。要求。基本思路基本思路交换排序种类交换排序种类:冒泡排序冒泡排序快速排序快速排序 1.6.3 交换排序交换排序1.冒泡排序冒泡排序基本思想：基本思想：通过相邻元素的交换，逐步将线性表变成有序。通过
