数据结构第八章排序-修改.ppt

n n排序的基本概念排序的基本概念n n插入排序插入排序n n交换排序交换排序n n选择排序选择排序n n归并排序归并排序n n基数排序基数排序n n各种方法的比较各种方法的比较1什么是排序什么是排序(Sorting)？简单地说，排序就是将一组杂乱无章简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增的数据按一定的规律排列起来（递增或递减）。或递减）。排序是计算机中经常遇到的操作。排序是计算机中经常遇到的操作。8.1 8.1 排序的概念排序的概念2数据表数据表(Data List)(Data List)待排序的记录的有限集合。待排序的记录的有限集合。待排序的记录的有限集合。待排序的记录的有限集合。关键字关键字(Key)作为排序依据的各记录中的属性域。作为排序依据的各记录中的属性域。作为排序依据的各记录中的属性域。作为排序依据的各记录中的属性域。数据表：数据表：R1 ，R2，R3，Rn 关键字序列：关键字序列：k1 ，k2，k3，kn 排序排序(Sorting)使一组任意排列的数据表变成一使一组任意排列的数据表变成一使一组任意排列的数据表变成一使一组任意排列的数据表变成一组组组组按关键字线性有序按关键字线性有序按关键字线性有序按关键字线性有序（递增或递减）的数据表。（递增或递减）的数据表。（递增或递减）的数据表。（递增或递减）的数据表。数据表：数据表：R1 ，R2，R3，Rn 关键字序列：关键字序列：k1 ，k2，k3，kn 其中：递增次序其中：递增次序：k1 k2 k3 kn 或或 递减次序递减次序：k1 k2 k3 kn 排序前：排序前：排序后：排序后：排序的概念排序的概念3例：例：5 5，2 2，8 8，5*5*排序后为：排序后为：2 2，5 5，5*5*，8 8 是稳定排序是稳定排序 排序后为：排序后为：2 2，5*5*，5 5，8 8 是不稳定排序是不稳定排序排序的分类排序的分类排序算法的稳定性排序算法的稳定性 关键字相同的记录在排关键字相同的记录在排关键字相同的记录在排关键字相同的记录在排序过程中保持前后次序不变的排序称稳定排序，序过程中保持前后次序不变的排序称稳定排序，序过程中保持前后次序不变的排序称稳定排序，序过程中保持前后次序不变的排序称稳定排序，否则称不稳定排序。否则称不稳定排序。否则称不稳定排序。否则称不稳定排序。内排序与外排序内排序与外排序 *内排序内排序内排序内排序是指在排序过程中记录全部存放在内存的是指在排序过程中记录全部存放在内存的是指在排序过程中记录全部存放在内存的是指在排序过程中记录全部存放在内存的排序；排序；排序；排序；*外排序外排序外排序外排序是指在排序过程中数据量太大，不能同时是指在排序过程中数据量太大，不能同时是指在排序过程中数据量太大，不能同时是指在排序过程中数据量太大，不能同时存放在内存，在排序过程中不断进行内、外存之存放在内存，在排序过程中不断进行内、外存之存放在内存，在排序过程中不断进行内、外存之存放在内存，在排序过程中不断进行内、外存之间数据交换的排序。间数据交换的排序。间数据交换的排序。间数据交换的排序。4数据表的存储方式数据表的存储方式 *顺序存储方式顺序存储方式顺序存储方式顺序存储方式通过移动记录的相对存储位置实通过移动记录的相对存储位置实通过移动记录的相对存储位置实通过移动记录的相对存储位置实现排序。现排序。现排序。现排序。排序的分类排序的分类*链式存储方式链式存储方式链式存储方式链式存储方式通过各结点修改指针实现排序通过各结点修改指针实现排序通过各结点修改指针实现排序通过各结点修改指针实现排序30 11 44 77 22 8811 22 30 44 77 88排序前排序后h30 11 44 77 22h 30 11 44 77 22 排序前排序后5n n排序的时间效率排序的时间效率排序的时间效率排序的时间效率:通常用算法执行中的通常用算法执行中的通常用算法执行中的通常用算法执行中的数据比较次数数据比较次数数据比较次数数据比较次数与与与与数据移动次数数据移动次数数据移动次数数据移动次数来衡量来衡量来衡量来衡量。n n排序的空间效率排序的空间效率排序的空间效率排序的空间效率：在算法执行时所需的附加存储空间多在算法执行时所需的附加存储空间多在算法执行时所需的附加存储空间多在算法执行时所需的附加存储空间多少来衡量。少来衡量。少来衡量。少来衡量。排序算法分析排序算法分析 为简单起见，数据的存储结构采用顺序方式存储，为简单起见，数据的存储结构采用顺序方式存储，同时假定关键字是整数。记录存储数据类型如下：同时假定关键字是整数。记录存储数据类型如下：typedeftypedeftypedeftypedef structstructstructstruct intintintint key;key;key;key;/*/*/*/*存放关键字存放关键字存放关键字存放关键字*/datatypedatatypedatatypedatatype other;other;other;other;/*/*/*/*存放其他数据项存放其他数据项存放其他数据项存放其他数据项*/rectyperectyperectyperectype;/*/*/*/*记录数据类型记录数据类型记录数据类型记录数据类型*/rectyperectyperectyperectype Rn+1;Rn+1;Rn+1;Rn+1;/*R1Rn/*R1Rn/*R1Rn/*R1Rn存放存放存放存放n n n n个记录个记录个记录个记录*/按关键字按关键字递增递增次序排序次序排序68.2 8.2 插入排序插入排序(Insert Sorting)(Insert Sorting)基本原理基本原理:将一个待排序的记录将一个待排序的记录,按其关键按其关键字大小字大小,插入到前面已经排好序的一组记录插入到前面已经排好序的一组记录的适当位置上的适当位置上,直到记录全部插入为止。直到记录全部插入为止。排序方法排序方法直接插入排序直接插入排序 (Insert Sort)(Insert Sort)希尔排序希尔排序 (Shell Sort)(Shell Sort)7n n基本思想基本思想:将第将第将第将第i i个记录插入在个记录插入在个记录插入在个记录插入在前前前前i-1i-1个有序个有序个有序个有序的记的记的记的记录中，使前录中，使前录中，使前录中，使前i i个记录有序。个记录有序。个记录有序。个记录有序。直接插入排序直接插入排序 (Insert Sort)k1 ，k2，ki-1，ki有序k1 ，k2，ki ki-1 有序例：例：10，20，30，40，50，2510，20，25，30，40，508主主要要操操作作30303333444422221111 1 2 3 4 50 1 2 3 4 5 3333222211114444303044441111 1 2 3 4 5 temp4444222211113333303030304433333333303044443333333330303030222222221111主要操作主要操作 步骤：步骤：*temp 暂存暂存 Ri,*将比其大的所有记录依次后移将比其大的所有记录依次后移 *temp(Ri)插入。插入。监视哨监视哨作用：作用：*暂存暂存Ri *检测越界检测越界R0R01111303044449 49 38 65 97 76 13 27 490 1 2 3 4 5 6 7 8 初始初始 49 38 65 97 76 13 27 49第一趟第一趟第二趟第二趟 38 49 65 97 76 13 27 4949 38384938656565第三趟第三趟 38 49 65 97 76 13 27 49第四趟第四趟 38 49 65 97 76 13 27 49第五趟第五趟 38 49 65 76 97 13 27 49第六趟第六趟 13 38 49 65 76 97 27 49第七趟第七趟 13 27 38 49 65 76 97 499797977676977613139776654938134927279776654938274997766549主要步骤：主要步骤：*R0 暂存暂存Ri*将比其大的所将比其大的所有记录依次后移有记录依次后移*R0 写入写入第第i-1趟：趟：（1）R0=Ri （2）j初值？初值？（3）若）若Rj.keyR0.key Rj后移后移 （4）j下一个下一个（前移）（前移）（5）重复（）重复（3）（）（4）直到？直到？（6）R?=R0 i的初值？的初值？终值？终值？i-1j+12n10第第i趟：趟：（1）R0=Ri （2）j初值？初值？（3）若）若Rj.keyR0.key Rj后移后移 （4）j下一个下一个（前移）（前移）（5）重复（）重复（3）（）（4）直到？直到？（6）R?=R0i的初值？的初值？终值？终值？insertsort(rectype R,n)for(i=2;iR0.key)/*将将所有大的记录后移所有大的记录后移*/Rj+1=Rj;j-;Rj+1=R0;/*插入插入*/直接插入排序的算法直接插入排序的算法i-1j+12n11直接插入排序算法分析直接插入排序算法分析时间性能：时间性能：直接插入排序算法由两重循环组直接插入排序算法由两重循环组直接插入排序算法由两重循环组直接插入排序算法由两重循环组成，外循环为成，外循环为成，外循环为成，外循环为n-1n-1趟趟趟趟排序；内循环表明完成一排序；内循环表明完成一排序；内循环表明完成一排序；内循环表明完成一趟排序所需进行的记录关键字间的趟排序所需进行的记录关键字间的趟排序所需进行的记录关键字间的趟排序所需进行的记录关键字间的比较比较比较比较和记录和记录和记录和记录的的的的后移后移后移后移。*最好情况：最好情况：初始时按关键字递增有序（正序）初始时按关键字递增有序（正序）初始时按关键字递增有序（正序）初始时按关键字递增有序（正序）比较次数比较次数比较次数比较次数:C=n-1 C=n-1 (每趟仅需一次比较）每趟仅需一次比较）每趟仅需一次比较）每趟仅需一次比较）移动次数移动次数移动次数移动次数:M=2(n-1)M=2(n-1)(每趟仅需每趟仅需每趟仅需每趟仅需RiRi 暂存及回写）暂存及回写）暂存及回写）暂存及回写）*最坏情况：最坏情况：最坏情况：最坏情况：初始时关键字递减有序（逆序）初始时关键字递减有序（逆序）初始时关键字递减有序（逆序）初始时关键字递减有序（逆序）O(n)O(n2)*平均情况：平均情况：平均情况：平均情况：T(n)=T(n)=O(nO(n2 2)12稳定性稳定性:稳定稳定稳定稳定的排序的排序的排序的排序。（关键字相同的记录不会交换次序）（关键字相同的记录不会交换次序）（关键字相同的记录不会交换次序）（关键字相同的记录不会交换次序）直接插入排序算法分析直接插入排序算法分析时间性能时间性能:T(n)=O(n2)但在数据表基本有序的情况下效率比较高但在数据表基本有序的情况下效率比较高但在数据表基本有序的情况下效率比较高但在数据表基本有序的情况下效率比较高空间性能空间性能:在排序过程中，只需附加一在排序过程中，只需附加一在排序过程中，只需附加一在排序过程中，只需附加一个存储单元作为个存储单元作为个存储单元作为个存储单元作为“监视哨监视哨监视哨监视哨”-R0-R0。S(n)=O(1)13希希 尔尔 排排 序序1959年由年由D.L.Shell提出，又称缩小增量提出，又称缩小增量排序排序(Diminishing-increment sort)。基本思想：基本思想：在排序中，每趟不断调整子序在排序中，每趟不断调整子序列的大小列的大小,从而减少比较次数从而减少比较次数,提高时间提高时间效率。效率。设计一个增量式序列设计一个增量式序列 di(i=1,2,),其中其中nd1 d2 d2.(通常通常通常通常d d1 1=n/2 d=n/2 di+1i+1=d=di i/2),/2),每趟将数据表分成每趟将数据表分成di组组,分别对各组进行直接插入排序分别对各组进行直接插入排序,直直到最后全部记录在一组为止。到最后全部记录在一组为止。14n=10d=5d=3d=2d=1注注:希尔排序开始时增量大希尔排序开始时增量大,分组多分组多,各组含记录较少各组含记录较少,故各组插入快故各组插入快.后来虽然增量逐渐减小后来虽然增量逐渐减小,各组含记录增各组含记录增多多,但各组已基本有序但各组已基本有序,所以插入速度仍较快所以插入速度仍较快.*每趟从每趟从Ri开始处理开始处理,i=?*Ri要插入前面有序的子序列中要插入前面有序的子序列中,子序列中每个记录间隔子序列中每个记录间隔d.*每趟每趟d=d/2 直到直到?d+1d=115*每趟从每趟从Ri开始处理开始处理,i=?*Ri要插入前面有序的要插入前面有序的子序列中子序列中,子序列中子序列中每个记录间隔每个记录间隔d.*每趟每趟d=d/2 直到直到?shellsort(rectype R,int n)d=?;do d=d/2;for(i=?;i0&Rj.keytemp.key)Rj+d=Rj;j=j-d;Rj+d=temp;while(?);希尔排序的算法希尔排序的算法nd0d+1i-d16稳定性稳定性:不稳定不稳定不稳定不稳定的排序的排序的排序的排序。（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）希尔排序算法分析希尔排序算法分析时间性能时间性能:T(n)=O(nlog2n)空间性能空间性能:在排序过程中，只需附加一在排序过程中，只需附加一在排序过程中，只需附加一在排序过程中，只需附加一个存储单元暂存当前处理记录个存储单元暂存当前处理记录个存储单元暂存当前处理记录个存储单元暂存当前处理记录。S(n)=O(1)178.3 8.3 交换排序交换排序 (Exchange Sort)(Exchange Sort)基本原理：基本原理：两两比较待排序记录的关键字两两比较待排序记录的关键字,若发生逆序若发生逆序(即排列顺序与排序后的次序正好即排列顺序与排序后的次序正好相反相反)，则交换之。直到所有记录都排好序为，则交换之。直到所有记录都排好序为止。止。交换排序方法交换排序方法起泡排序起泡排序(Bubble Sort)快速排序快速排序(Quick Sort)18n n基本思想：基本思想：在待排序子序列在待排序子序列在待排序子序列在待排序子序列 中，两两比较中，两两比较相邻相邻记记录的关键字，若逆序，则交换。录的关键字，若逆序，则交换。起泡排序起泡排序 (Bubble Sort)n n关键字子序列关键字子序列关键字子序列关键字子序列:ki,ki+1,knnkn-1 与与kn ,kn-2与与kn-1 ki 与与ki+1 进行比较进行比较n若若逆序逆序，则交换。，则交换。1955221133442211335544113333445522113344334455221133441155115511221122逆序逆序逆序逆序逆序逆序正序正序主主要要操操作作 由于关键字小由于关键字小的记录不断上的记录不断上浮，象小气泡浮，象小气泡一样，故称为一样，故称为起泡排序起泡排序。注：注：在一趟排在一趟排序中，将关键序中，将关键字最小的记录字最小的记录顶到第一位。顶到第一位。20333344445555222211111 2 3 4 533334444555522221111333344445555222211113333222233332222222233333333555533334444555522221111555511115555111155551111444455554444555544445555逆序逆序逆序逆序逆序逆序正序正序从从前前向向操操作作注：注：将子序列中将子序列中最大记录沉到最最大记录沉到最后一个后一个211 2 3 4 5 6 7 8 初始初始 49 38 65 97 76 13 27 49第一趟第一趟 49 38 65 97 76 13 27 4949 3838 496549389749657665 76 97 1376 9713 9713 97 2727 9727 97499749第二趟第二趟 38 49 65 76 13 27 49 97第三趟第三趟 38 49 65 13 27 49 76 97第四趟第四趟 38 49 13 27 49 65 76 97第五趟第五趟 38 13 27 49 49 65 76 97第六趟第六趟 13 27 38 49 49 65 76 9738 493865 7649 65137613 76132727 7627 76 4949 7649384938133827136538133838131349 13 6513 4913 3813 65 2727 6513 49 2727 4913 38 2727 65 4949 6527 49 4927 3827 38 49主要步骤：主要步骤：两两相邻记录两两相邻记录比较，若逆序，比较，若逆序，则交换。则交换。多多少少趟趟？注：注：当某趟没有交换时，没有必要进行下一趟。当某趟没有交换时，没有必要进行下一趟。974949 7649 6527 49 4927 38 493827如何解决？如何解决？设置一个标志设置一个标志flag每趟：每趟：*初始时初始时flag=0 *若有交换若有交换flag=1当本趟结束时，若当本趟结束时，若flag为为1，则需要进行下一趟。，则需要进行下一趟。若若flag为为0，则排序，则排序结束结束。每趟：每趟：（1）j初值为初值为1，终值，终值j=?（2）flag=0 （3）若）若Rj.keyRj+1.key Rj与与Rj+1交换交换 flag=1 （4）重复（重复（3）（5）若若flag=？,则结束排序。则结束排序。每趟进行比较的次数依次递减，每趟进行比较的次数依次递减，第第一趟一趟 i的初值？的初值？终值？终值？n-i01n-122每趟：每趟：（1）j初值为初值为1，终值，终值i=?（2）flag=0 （3）若）若Rj.keyRj+1.key Rj与与Rj+1交换交换 flag=1 （4）重复（重复（3）（5）若若flag=？,则结束排序。则结束排序。每趟进行比较的次数依次递减，每趟进行比较的次数依次递减，第第一趟一趟 i的初值？的初值？终值？终值？bubblesort(rectype R,int n)flag=1;i=n-1;while(flag=1)flag=0;for(j=1;jRj+1.key)temp=Rj;Rj=Rj+1;Rj+1=temp;flag=1;i-;起泡排序的算法起泡排序的算法23起泡排序的算法分析起泡排序的算法分析时间性能：时间性能：起泡排序算法由两重循环组成，外循起泡排序算法由两重循环组成，外循起泡排序算法由两重循环组成，外循起泡排序算法由两重循环组成，外循环的次数主要是由各趟环的次数主要是由各趟环的次数主要是由各趟环的次数主要是由各趟有无交换有无交换有无交换有无交换而决定；内循环表而决定；内循环表而决定；内循环表而决定；内循环表明完成一趟排序所需进行的记录关键字间的明完成一趟排序所需进行的记录关键字间的明完成一趟排序所需进行的记录关键字间的明完成一趟排序所需进行的记录关键字间的比较比较比较比较和和和和记录的记录的记录的记录的交换交换交换交换。*最好情况：最好情况：初始时按关键字递增有序（正序）初始时按关键字递增有序（正序）初始时按关键字递增有序（正序）初始时按关键字递增有序（正序）比较次数比较次数比较次数比较次数:C=n-1 C=n-1 (仅需一趟排序）仅需一趟排序）仅需一趟排序）仅需一趟排序）移动次数移动次数移动次数移动次数:M=0M=0 (这一趟没有逆序）这一趟没有逆序）这一趟没有逆序）这一趟没有逆序）O(n)*最坏情况：最坏情况：最坏情况：最坏情况：初始时关键字递减有序（逆序）初始时关键字递减有序（逆序）初始时关键字递减有序（逆序）初始时关键字递减有序（逆序）O(n2)*平均情况：平均情况：平均情况：平均情况：T(n)=T(n)=O(nO(n2 2)24稳定性稳定性:稳定稳定稳定稳定的排序的排序的排序的排序。（关键字相同的记录不会交换次序）（关键字相同的记录不会交换次序）（关键字相同的记录不会交换次序）（关键字相同的记录不会交换次序）起泡排序的算法分析起泡排序的算法分析时间性能时间性能:T(n)=O(n2)但在数据表基本有序的情况下效率比较高但在数据表基本有序的情况下效率比较高但在数据表基本有序的情况下效率比较高但在数据表基本有序的情况下效率比较高空间性能空间性能:排序在排序过程中，只需附排序在排序过程中，只需附排序在排序过程中，只需附排序在排序过程中，只需附加一个存储单元用于交换加一个存储单元用于交换加一个存储单元用于交换加一个存储单元用于交换。S(n)=O(1)25快速排序快速排序(Quick Sort)n n基本思想基本思想是任取待排序子序列中的一个记录是任取待排序子序列中的一个记录是任取待排序子序列中的一个记录是任取待排序子序列中的一个记录(例如例如例如例如取第一个取第一个取第一个取第一个)作为作为作为作为基准基准基准基准,按照该记录关键字的大小按照该记录关键字的大小按照该记录关键字的大小按照该记录关键字的大小,将整个子序列将整个子序列将整个子序列将整个子序列划分划分划分划分为左右两个子序列为左右两个子序列为左右两个子序列为左右两个子序列：uu左侧左侧左侧左侧所有记录的关键字都所有记录的关键字都所有记录的关键字都所有记录的关键字都小于基准小于基准小于基准小于基准记录的关键字记录的关键字记录的关键字记录的关键字uu右侧右侧右侧右侧所有记录的关键字都所有记录的关键字都所有记录的关键字都所有记录的关键字都大于或等于基准大于或等于基准大于或等于基准大于或等于基准记录的关键字记录的关键字记录的关键字记录的关键字klow,klow+1,khighklow,klow+1,klow ,khighn n基准记录则排在这两个子序列基准记录则排在这两个子序列基准记录则排在这两个子序列基准记录则排在这两个子序列中间中间中间中间(这也是该记录的这也是该记录的这也是该记录的这也是该记录的最终排序的位置最终排序的位置最终排序的位置最终排序的位置)。n n然后分别对这两个子序列重复施行上述方法，直到然后分别对这两个子序列重复施行上述方法，直到然后分别对这两个子序列重复施行上述方法，直到然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。所有的记录都排在相应位置上为止。所有的记录都排在相应位置上为止。所有的记录都排在相应位置上为止。小小大大262121252549493535161608081 2 3 4 5 6pivotpivot212135352525161649490808temptemp暂存基准暂存基准暂存基准暂存基准212125254949353516160808212121210808080825252525161616164949494921212121基本思想：基本思想：将后面所有关键字小于基准关键字的记录移到将后面所有关键字小于基准关键字的记录移到前面，将前面所有关键字大小基准关键字的记录移动后面。前面，将前面所有关键字大小基准关键字的记录移动后面。反复交替操作：反复交替操作：*从后向前从后向前找到第一个关键字小于基准的记录与基准交换，找到第一个关键字小于基准的记录与基准交换，*从前向后从前向后找到第一个关键字大于基准的记录与基准交换。找到第一个关键字大于基准的记录与基准交换。2121212108082121252525252121271 2 3 4 5 6 7 8 初始初始 49 38 65 97 76 13 27 49第一趟第一趟temp49pivotji276527651313 979749 27 38 1376 97 65 4949反复交替操作：反复交替操作：*从后向前找到从后向前找到第一个关键字小于第一个关键字小于基准的记录前移基准的记录前移 *从前向后找到从前向后找到第一个关键字大于第一个关键字大于基准的记录后移基准的记录后移设置指针设置指针i（从前向后扫描）从前向后扫描）设置指针设置指针j（从从后向前扫描）后向前扫描）划划 分分在在Rlow.high划分的主要步骤：划分的主要步骤：（1）初值？）初值？（2）temp=Rlow（3）从后向前：当从后向前：当Rj=temp时，时，j-;（4）Rj前移？前移？（5）从前向后：当）从前向后：当Ritemp时，时，j-;（4）Rj前移？前移？（5）从前向后：当）从前向后：当Ritemp时；时；i+;（6）Ri后移？后移？（7）重复（）重复（3）（6）直）直到？到？（8）R?=temp划划 分分 算算 法法？partition(rectype R,int low,int high)i=low;j=high;temp=Rlow;while(ij)while(i=temp.key)j-;if(ij)Ri=Rj;i+;while(ij&Ri.key=temp.key)i+;if(ij)Rj=Ri;j-;Ri=temp;return i;291 2 3 4 5 6 7 8 初始初始 49 38 65 97 76 13 27 49第一趟第一趟pivot 27 38 1376 97 65 4949快速排序快速排序49132738769749 6549 65Rs.t快速排序主要步骤：快速排序主要步骤：(递归）递归）（1）在）在Rs.t进行划分，确定基准的位置进行划分，确定基准的位置k（2）在在Rs.?进行快速排序进行快速排序（3）在）在R?.t进行快速排序进行快速排序递归出口？递归出口？30主要步骤：主要步骤：(递归）递归）Rs.t（1）在）在Rs.t进行划分，确进行划分，确定基准的位置定基准的位置i（2）在在Rs.?进行快速排序进行快速排序（3）在）在R?.t进行快速排序进行快速排序递归出口？递归出口？快速排序的算法快速排序的算法quicksort(R,s,t)rectype R;int s,t;if(?)i=partition(R,s,t);/*/*划分并确定基准位置划分并确定基准位置*/quicksort(R,s,?);/*/*递归处理左序列递归处理左序列*/quicksort(R,?,t);/*/*递递归处理右序列归处理右序列*/31时间性能：时间性能：取决于每一次划分的结果。取决于每一次划分的结果。快速排序的算法分析快速排序的算法分析*最坏情况：最坏情况：最坏情况：最坏情况：每次划分选取的基准都是当前无序区中每次划分选取的基准都是当前无序区中每次划分选取的基准都是当前无序区中每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果只是一关键字最小（或最大）的记录，划分的结果只是一关键字最小（或最大）的记录，划分的结果只是一关键字最小（或最大）的记录，划分的结果只是一个区间，则排序必须做个区间，则排序必须做个区间，则排序必须做个区间，则排序必须做n-1n-1趟趟趟趟，每一趟中需做，每一趟中需做，每一趟中需做，每一趟中需做n-in-i次次次次比较，所以最大比较次数为：比较，所以最大比较次数为：比较，所以最大比较次数为：比较，所以最大比较次数为：32用第一个对象作为基准对象用第一个对象作为基准对象快速排序退化的例子快速排序退化的例子1 2 3 4 5 6 1 2 3 4 5 6 pivotpivot初始初始初始初始i i=1=1i i=2=2i i=3=3i i=4=4i i=5=533快速排序的算法分析快速排序的算法分析*最好情况：最好情况：最好情况：最好情况：每次所取的基准都是当前无序区的每次所取的基准都是当前无序区的每次所取的基准都是当前无序区的每次所取的基准都是当前无序区的“中中中中值值值值”记录，划分的结果是基准的左右两个无序子区间记录，划分的结果是基准的左右两个无序子区间记录，划分的结果是基准的左右两个无序子区间记录，划分的结果是基准的左右两个无序子区间的长度大致相等。的长度大致相等。的长度大致相等。的长度大致相等。设设设设C(n)C(n)表示对长表示对长表示对长表示对长度为度为度为度为n n 的序列进行快速排的序列进行快速排的序列进行快速排的序列进行快速排序所需的比较次数，它等序所需的比较次数，它等序所需的比较次数，它等序所需的比较次数，它等于于于于划分划分划分划分所需的比较次数所需的比较次数所需的比较次数所需的比较次数n-n-1 1，加上加上加上加上平分平分平分平分后左右两个后左右两个后左右两个后左右两个无序无序无序无序子区间子区间子区间子区间进行快速排序进行快速排序进行快速排序进行快速排序所需的比较次数。所需的比较次数。所需的比较次数。所需的比较次数。假设数据长度假设数据长度假设数据长度假设数据长度n=2n=2k k k=log k=log2 2n n34快速排序的算法分析快速排序的算法分析稳定性稳定性:不稳定不稳定不稳定不稳定的排序的排序的排序的排序。（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）时间性能时间性能:最坏时间最坏时间T(n)=O(n2)最好时间最好时间T(n)=O(nlog2n）已证明，平均时间已证明，平均时间T(n)=O(nlog2n)空间性能空间性能:排序算法是利用递归实现的，排序算法是利用递归实现的，排序算法是利用递归实现的，排序算法是利用递归实现的，排序过程中需附加栈空间用于存储递归排序过程中需附加栈空间用于存储递归排序过程中需附加栈空间用于存储递归排序过程中需附加栈空间用于存储递归各层信息，则各层信息，则各层信息，则各层信息，则 S(n)=O(log2n)358.4 8.4 选择排序选择排序(Selection Sort)基本原理基本原理:在待排序的子序列中在待排序的子序列中,选择关选择关键字最小键字最小(或最大或最大)的记录的记录,存放在已排序存放在已排序的子序列中。的子序列中。排序方法排序方法直接选择排序直接选择排序(Straight Select Sort)堆排序堆排序(Heap Sort)36n n基本思想基本思想:在子序列中选择具有最小在子序列中选择具有最小在子序列中选择具有最小在子序列中选择具有最小(或最大或最大或最大或最大)关关关关键字的记录键字的记录键字的记录键字的记录,若它不是这子序列中的第一位，则将若它不是这子序列中的第一位，则将若它不是这子序列中的第一位，则将若它不是这子序列中的第一位，则将它调入到第一位上。它调入到第一位上。它调入到第一位上。它调入到第一位上。直接选择排序直接选择排序 (Straight Select Sort)k1 ，k2，kikd ，k2，k1 ki最小(或最大)例：例：30，20，50，10，40，7010，20，50，30，40，70kd371 2 3 4 5 6 7 8 初始初始 49 65 38 97 76 13 27 49第一趟第一趟 49 65 38 97 76 13 27 49131349第六趟第六趟 13 27 38 49 49 97 65 76第二趟第二趟 13 65 38 97 76 49 27 49第三趟第三趟 13 27 38 97 76 49 65 49第四趟第四趟 13 27 38 97 76 49 65 49第五趟第五趟 13 27 38 49 76 97 65 49第七趟第七趟 13 27 38 49 49 65 97 76276527493897494976496565977667 97主要步骤主要步骤:在在子子序列中序列中选择关键字选择关键字最小的记录最小的记录交换到子序交换到子序列的第一位列的第一位.第第i趟子序列的区间趟子序列的区间?第第i i趟趟:(1)(1)从从Ri Ri Rn Rn中选择最小关键字的记录中选择最小关键字的记录Rk;Rk;(2)(2)若若k!=i,k!=i,则则RiRi与与RkRk交换交换.38直接选择排序直接选择排序的算法的算法第第i i趟趟:(1)(1)从从RiRiRnRn中中选择最小关键字的选择最小关键字的记录记录Rk;Rk;(2)(2)若若k!=i,k!=i,则则RiRi与与RkRk交换交换.selectsort(rectype R,int n)for(int i=1?;i n?;i+)k=i;/选择具有最小排序码的对象选择具有最小排序码的对象 for(j=i+1?;j =n;j+)if(Rj.key Rk.key)k=j?;/当前具最小排序码的对当前具最小排序码的对象象 if(?k!=i)/对换到第对换到第 i 个位置个位置 temp=Ri;Ri=Rk;Rk=temp;39直接选择排序算法分析直接选择排序算法分析时间性能：时间性能：直接选择排序算法由两重循环组直接选择排序算法由两重循环组直接选择排序算法由两重循环组直接选择排序算法由两重循环组成，外循环为成，外循环为成，外循环为成，外循环为n-1n-1趟趟趟趟排序；内循环表明完成一排序；内循环表明完成一排序；内循环表明完成一排序；内循环表明完成一趟排序所需进行的记录关键字间的趟排序所需进行的记录关键字间的趟排序所需进行的记录关键字间的趟排序所需进行的记录关键字间的比较比较比较比较和记录和记录和记录和记录的的的的后移后移后移后移。O(n2)*时间效率：时间效率：时间效率：时间效率：T(n)=T(n)=O(nO(n2 2)*比较次数比较次数:直接选择排序的比较次数直接选择排序的比较次数与初始状态无与初始状态无关关.第第i i趟选择关键字最小的记录要比较趟选择关键字最小的记录要比较n-in-i次次,则总则总的比较次数为的比较次数为:*移动次数移动次数:最好情况是每趟关键字最小的记录总是子最好情况是每趟关键字最小的记录总是子序列中第一位序列中第一位,不需要交换不需要交换,M=0;,M=0;最坏情况是每趟都需最坏情况是每趟都需要将关键字最小的记录交换到子序列的第一要将关键字最小的记录交换到子序列的第一,M=3(n-,M=3(n-1).1).则则平均移动次数为平均移动次数为O(n).O(n).40直接选择排序的算法分析直接选择排序的算法分析稳定性稳定性:不稳定不稳定不稳定不稳定的排序的排序的排序的排序。（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）（关键字相同的记录会交换次序）时间性能时间性能:T(n)=O(n2)空间性能空间性能:需附一个存储单元用于交换，需附一个存储单元用于交换，需附一个存储单元用于交换，需附一个存储单元用于交换，则则则则 S(n)=O(1)41n n堆的定义：堆的定义：n个关键字序列个关键字序列k1,k2,.,kn称为称为堆，当且仅当该序列满足特性：堆，当且仅当该序列满足特性：堆排序堆排序(Heap Sort)ki k2iki k2i+1注：注：若将序列看成按层次编号的若将序列看成按层次编号的完全二叉树完全二叉树，根据二叉，根据二叉树的性质树的性质,即即k ki i 的左右孩子正好分别为的左右孩子正好分别为k k2i 2i 和和k k2i+12i+1，因此因此,堆也可以说是满足如下性质的完全二叉树堆也可以说是满足如下性质的完全二叉树:树中任一分支树中任一分支结点的值均大于或等于它的孩子结点的值结点的值均大于或等于它的孩子结点的值.(1 i n/2)大根堆大根堆ki k2iki k2i+1或或小根堆小根堆42例例:(96,83,27,38,11,9)96832738119大根堆大根堆例例:(10,15,56,25,30,70)101556253070小根堆小根堆注注:在大根堆中根在大根堆中根(第一个第一个)为为最大值最大值.在小根堆中根在小根堆中根(第一个第一个)为为最小值最小值.例例:(42,13,91,23,24,16,5,88)421391232416588不是根堆不是根