《计算机应用基础课件》1.6排序.ppt

,第 1 章 数据结构,主要内容1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 排序,姓名 学号 成绩 班级 李红 9761059 95 机97.6,10,65,865,1.6 排序,排序又称分类，是计算机程序设计中一个重要运算，它的功能是将一组任意序列的数据元素，进行按关键字由大到小的顺序（降序）排列或按由小到大的顺序（升序）排列。,排序的对象：这些数据元素可以是数值型，也可以为字符型。若为数值型，则按数值大小排列；若为字符型，则按其ASCII码的顺序排列。,排序的依据：在实际应用中，参加排序的数据元素有时不是单个数据项，而是由多个数据项组成的记录。此时排序应按照关键字的大小进行。所谓关键字是指记录中的某个数据项，用它可以标识一个记录。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字；反之，把用以识别若干记录的关键字称为次关键字。,排序的稳定性：在待排序的记录中，若存在多个关键在相同 的记录，经过排序后，这些具有相同关键在 的记录之间的相对次序发生变化，则称这种 排序方法是稳定的；否则，是不稳定的。排序的分类：内部排序与外部排序 内部排序:整个排序过程完全在内存中进行.外部排序:由于待排序记录数据量太大,内存无法容纳 全部数据,排序需要借助外部存储设备才能 完成.排序算法评价：算法执行时间(最好、最差及平均情况)、需要附加空间大小,1.6 排序,插入排序的基本思想：,1.6.2 插入排序,插入排序三种方法1.直接排序:认可第1个记录已排好序，然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。2.折半插入排序:折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。3.希尔排序:将整个无序序列分割成若干个子序列分别进行直接插入排序.,将待排序文件中的记录，逐个按其排序码值的大小插入到已排好序的若干个记录组成的文件中的适当位置，保持新文件有序。,1.直接插入排序:思路：认可第1个记录已排好序，然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。具体过程(第i个记录Ri插入到前面i-1个已排好序的记录中)将Ri的排序码与前面已排好序的排序码从右向左依次比较，找到Ri应插入的位置；将该位置以后直到Ri-1各记录顺序后移,空出位置插入Ri。,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 50,i=2,39,(39 49 66)96 76 11 37 50,i=3,66,(39 49 66 96)76 11 37 50,i=4,96,(39 49 66 76 96)11 37 50,i=5,76,(11 39 49 66 76 96)37 50,i=6,11,(11 37 39 49 66 76 96)50,i=7,37,(11 37 39 49 50 66 76 96),i=8,50,对于有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;i=0,tempaj,若降序排序，则：,1.直接插入排序:时效分析,最好情况:初始排序码已经有序。共比较n-1次，移动0次。,最坏情况:待排序序列完全逆序。比较和移动均为n(n-1)/2次。,平均情况:比较和移动次数均约为n2/4，时间复杂度为O(n2)。,1.6.2 插入排序,该算法适合于n 较小的情况，时间复杂度为O(n2).,2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。,折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同为O(n2)。,1.6.2 插入排序,3.希尔排序,基本思想：将整个无序序列分割成若干个子序列分别进 行直接插入排序,待整个序列中的记录”基本 有序”时,再对全体记录进行一次直接插入排序。子序列分割：选定两个元素之间距离h，将所有间隔为h的元素 分成一组(将相隔某个增量h的元素构成一个子系列),具体实现:,(1)选择一个增量序列t1，t2，tk,其中ti 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,11,100,7,41,86)取增量：5，3，1,h=5,39 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，11,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10 R11,R12,R13,R14,h=5,39 80 76 41 13 29 50 78 30 11 100 7 41 86,子序列：39，29，100，80，50，7，76，78，41，41，30，86，13，11,R1,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 86,29 30 50 13 78,7 11 76 100 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 R14,13 29 30 50 78,7 11 76 86 100,39 41 41 80,第二趟最终结果：,第一趟排序结果,13 7 39 29 11 41 30 76 41 50 86 80 78 100,h=1 序列基本有序，对其进行直接插入排序,第三趟最终结果：,7 11 13 29 30 39 41 41 50 76 78 80 86 100,第二趟最终结果：,3.希尔排序,特点：每一遍以不同间隔距离插入排序。h较大时移动数据元素是跳跃式进行。子序列每一次比较可能移去多个逆序(直接插入排序每次比较只能移去一个)。效率较高。最后一次排序(h=1)时，已基本有序，不需要多少移动。故其时间复杂度较直接插入排序低。数学难题：如何选取增量序列才能有最好的排序效果，至今未完整解决。但注意：增量序列中除1外没有公因子，且最后一个增量序列必须为1。时效分析:很难。比较次数与移动次数依赖于增量序列的选取，特定情况下可以估计.,1.6.2 插入排序,对待排序记录两两比较排序码，不满足排序顺序则交换。直到任何两个记录排序码满足排序要求。,基本思路,交换排序种类:,冒泡排序快速排序,1.6.3 交换排序,1.冒泡排序基本思想：通过相邻元素的交换，逐步将线性表变成有序。基本过程：第一趟冒泡排序：首先第一个元素与第二个元素比较，逆序则 交换；然后第二个元素与第三个元素比较；直到第n-1个元素与第n个元素比较为止。结果（关键字）最大的元素放在最后位置。第二趟冒泡排序：对前面n-1个元素进行相同操作，结果 次大元素放在n-1位置上。第i趟冒泡排序：对前面n-i+1个元素进行相同操作，结 果(n-i+1)中最大元素放在(n-i+1)位置上。,趟数：最多n-1,结束条件：在某一趟排序中没有进行交换元素操作。,1.6.3 交换排序,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,思想：小的浮起，大的沉底。,举例:将数列(8,6,5,7,1)升序排序,初始86571,第一趟65718,第二趟56178,第三趟51678,第四趟15678,初始已排好序(正序最好)，则只需进行一趟排序,比较次数n-1，移动次数为0。逆序(最坏)，则需进行n-1趟排序,比较次数为(1+2+3+n-1)=n(n-1)/2。是稳定的排序,时间复杂度为O(n2),空间复杂度是O(1).,时效分析:,程序代码:,#define N 5int gradeN,temp;for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,读入5个值保存在数组中,16,71,46,90,85,temp=46,temp=71,temp=16,16,71,46,90,85,i=0 第1趟,j=0 从头开始比较,j4,条件不成立,j=1,j4,条件成立,90,46,j=2,j4,条件成立,90,71,j=3,j4,90,16,j=4,内层循环终止,90,即：i=0 第1趟 时 grade0 和grade1比较 grade1 和grade2比较 grade2 和grade3比较 grade3 和grade4比较 最大值放到grade4中,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,即，i=0 第1趟 时内存循环for(j=0;jN-1-i;j+)变量j是从0到3的,16,71,46,90,85,i=1 第2趟,j=0 从头开始比较,90,46,90,71,90,16,90,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,内存循环for(j=0;jN-1-i;j+)中 j的取值从0到2 grade0 和grade1比较 grade1 和grade2比较 grade2 和grade3比较找出次大值放到grade3中,16,71,46,90,85,i=1 第2趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,16,71,46,85,i=2 第3趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,71,71,16,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,16,71,46,85,i=3 第4趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,71,71,16,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,46,16,46,2.快速排序,基本思想：通过一趟排序将待排记录分割成独立两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再对前、后两部分待排记录重复上述过程，直到所有子表表长不超过1为止。,优点：通过两个不相邻元素交换，可以一次交换消除多个逆序，加快排序速度。,49 39 66 96 76 11 27 50,27 39 11 49 76 96 66 50,27 39 49 50 66 76 96,1.6.3 交换排序,2.快速排序,过程:,首先任选一个记录K(通常选第一个记录)作为枢轴(支点)附设两个指针i和j分别指向第一个记录和最后一个记录。(1)指针j向前搜索逐个记录与K比较,直到发现小于K的记录为止，将其与枢轴记录互相交换。(2)指针i向后搜索逐个记录与K比较,直到发现大于K的记录为止，将其与枢轴记录互相交换。(3)重复(1)(2)直至i=j为止。完成一趟排序，完成一次分割(以K为分界线)，对前后两个子表按上述原则再分割，直到所有子表的表长不超过1(为空)为止。,1.6.3 交换排序,49 39 66 96 76 11 27 50,第1次交换(向前,小的与枢轴交换)即27与49交换.,第2次交换:(向后,大的与枢轴交换)即66与49换,第3次交换:11与49换,完成一趟排序:,初始关键字,第4次换:96与49换,27 39 11 49 76 96 66 50,举例:将（49，39，66，96，76,11，27，50）进行一趟快速排序 分析:(取第一个数49为枢轴,即K=49,空处是枢轴为49),49 39 66 96 76 11 27 50,27 39 11 49 76 96 66 50,一次划分之后,快速排序的全过程,初始关键字,分别进行快速排序,11 27 39,50 66 结束,结束 结束 50 66 76 96,结束,11 27 39 49 50 66 76 96,有序序列,时效分析:平均时间复杂度最佳为O(nlog2n)。最坏情况时间效率为O(n2)。,基本思想：每次从待排序的记录中选出关键字最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序种类:直接选择排序和堆排序,1.直接选择排序(以升序为例)首先从所有n个待排序记录中选择关键字最小的记录，与第1个记录交换(第1遍进行n-1次比较)。再从剩下的 n-1个记录中选出关键字最小的记录，与第2个记录交换(第2遍进行n-2次比较)。重复操作进行n-1遍，直到待排序序列全部有序为止。,1.6.4 选择排序,1.直接选择排序,正序：移动次数为0逆序：移动次数为3(n-1),执行n(n-1)/2次比较,举例:将（89，21，56，48，85，16，19，47）直接选择排序,原序列 89 21 56 48 85 16 19 47,最后结果 进行n-1=7次选择,1.6.4 选择排序,时效分析:,选择法排序 for(i=0;i ak)k=j;if(k!=i)temp=ai;ai=ak;ak=temp;,例,初始：49 38 65 97 76 13 27,i=1,13,49,一趟：13 38 65 97 76 49 27,i=2,27,38,六趟：13 27 38 49 65 76 97,从小到大排序,2.堆排序堆定义：n个元素的序列K1，K2，Kn，当且仅当满足下列关 系时，称为堆。,kik2i kik2i+1,kik2i kik2i+1,小根堆 或,大根堆,堆结构(完全二叉树表示)：将序列对应的一维数组看成一个完全二叉树。,在堆中,堆顶元素必为序列中n个元素的最小值(或最大值)。,小根堆,大根堆,其中:（i=1，2，n/2）,1.6.4 选择排序,首先包括n个元素的序列建堆,输出堆顶最小值。得到n个元素中最小元素。然后再对剩下n-1个元素重建堆,输出堆顶元素。得到n个元素中次小元素。反复执行(直到剩下子序列为空)，便得到一个有序列。,2.堆排序,排序过程:,两个问题:实现堆排序需解决,(1)如何将n个元素的无序序列建成一个堆。,(2)输出堆顶元素后，调整剩余元素成为一个新堆。,输出堆顶元素后，以堆中最后一个元素代替之。此时根结点左、右子树均为堆，仅需自上而下调整即可。,1.6.4 选择排序,方法：将根结点与左、右子树根结点比较，若不满足堆条件，则较小值与根结点交换。顺序：从完全二叉树最后一个非终端结点(第n/2个元素)开始，直到根结点(第一个元素)为止，对每一个结点，调整建堆。,举例:一个无序序列(49,39,66,96,76,11,27,50)建小根堆的过程 1.从第一个非叶子结点(序号=n/2=8/2=4,即图中值为96的结点开始筛选,筛选 原则是保证父结点的值要小于或等于叶子接点,第4个结点96被筛选后状态,第3个结点66被筛选后状态,目前的堆中,堆顶元素11为最小值,输出后,重新对n-1个元素重新建一个新堆,新堆中的堆顶是剩余的n-1个元素中的最小值,n个元素中的次最小值.,49 被筛选后建成的堆,该处理第1个结点,举例:输出堆顶元素并建新堆过程,堆,11,11与96交换后情形,输出堆顶元素之后,以堆中最后一个元素替代之,此时根结点的左、右子树均为堆,仅需自上至下进行调整即可。,11,27与96交换后情形,11,调整后新堆,27为新堆中的最小值,27,输出27,用96替代,11,96与39换,11,27,96与50换,调整后新堆,27为新堆中的最小值,11,调整后新堆,39为新堆中的最小值,继续此过程,调整后新堆,39为新堆中的最小值,11,27,39,11,27,输出堆顶元素（堆顶元素和树中最后一个结点对调）重建堆（因为除了堆顶的根结点，左右子树已经是堆，自上而下进行调整即可）反复执行直到剩下子序列为空（便得到一个有序列）,堆排序的时效分析:最坏情况下，时间复杂度为O(nlog2n)。仅需一个记录大小供交换用的辅助存储空间，适合规模较大的线性表。,排序小结,查找与排序补充习题讲解,1.链表适用于_查找.A.顺序 B.二分法 C.顺序,也能二分法 D.随机2.对长度为n的线性表进行顺序查找,在最坏情况下所需要 的比较次数为_.A.log2n B.n/2 C.n D.n+1（05年4月）3.已知一个有序表为(13、18、24、35、47、50、62、83、90、115、134），当使用二分法查找90的元素时，查找 成功的比较次数为_.A.1 B.2 C.3 D.94.在排序算法中，两两比较待排序的记录，当发现不满足 顺序要求时，变更他们的相对位置，这就是_排序。A.希尔排序 B.交换排序 C.插入排序 D.选择排序,ACBB,5.设待排序关键码序列为（33、18、9、25、67、82、53、95、12、70），要按关键码值递增的顺序排序，采取以 第一个关键码为分界元素的快速排序法，第一趟排序完 成后关键码33被放到了第_个位置。A.3 B.5 C.7 D.96.希尔排序法属于哪一种类型的排序法_。A.交换类排序法 B.插入类排序法 C.选择类排序法 D.建堆排序法以下各组序列中，属于堆的是_.A.19、34、26、97、56、75 B.97、26、34、75、19、56 C.19、56、26、97、34、75 D.19、75、34、26、97、568.对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_.(05.4月）A.冒泡排序为n/2 B.冒泡排序为n C.快速排序为n D.快速排序为n(n-1)/2,BBAD:8:在最坏情况下,冒泡排序和快速排序的比较次数都是 n(n-1)/2,查找与排序补充习题讲解,填空题：1.在排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素做比较，将其放入已排序的正确位置上的方法，称为_.2.对于给定的一组关键字（12、2、16、30、8、28、4、10、20、6、18），按照希尔排序（增量为5）算法进行递增排序，第一趟排序后得到的结果是_.,（12、2、16、30、8、28、4、10、20、6、18）,12 28 18,16 10,2 4,30 20,8 6,对每个系列排序,则最终结果12,2,10,20,6,18,4,16,30,8,28,3.在长度为n的线性表中顺序查找x的元素时,查找成功的平均查找长度为_.4.在具有88个结点的二叉数,其深度至少为_.,3解析:平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度.假设在每个位置查找概率相等,即p1=p2=1/n,若是从表尾向表头方向查找,则每个位置上查找比较次数为:Cn=1,Cn-1=2,C1=n.于是,查找成功的平均查找长度为 ASL=(1/n)(1+2+3+n)=(n+1)/24 分析:性质4:深度=log2n+1=log288+1=6+1=7,