第9章排序案例.ppt

lirui,1,第9章排序,9.1插入排序9.2交换排序9.3选择排序9.4归并排序9.5基数排序9.6各种内部排序方法的比较讨论,2,9.1插入排序,一、直接插入排序二、折半插入排序三、希尔排序,3,一、直接插入排序,直接插入排序的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增加1的有序表。,例如：已知待排序的一组记录的初始排列如下所示：R（49），R（38），R（65），R（97），R（76），R（13），R（27），R（19）。,4,假设在排序过程中，前四个记录已按关键字递增的次序，重新排列，构成一个含4个记录的有序序列:,现要将第5个（关键字为76）的记录插入上述序列，可以得到一个新的含5个记录的有序序列，则首先要找到插入的位置，然后进行插入。,假设从R（97）起向左进行顺序查找，由于657697，则R（76）应插入在R（65）和R（97）之间，从而得到下列新的有序序列:,R（38），R（49），R（65），R（76），R（97）（2）,称从式（1）到式（2）的过程为一趟直接插入排序。,38，49，65，97（1）,5,一般情况下，第i趟直接插入排序的操作为：,在含有i-1个记录的有序子序列r1i-1中插入一个记录ri后，变成含有i个记录的有序子序列r1i；,并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r0处设置监视哨。,整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序序列的子序，然后从第2个记录起逐个进行插入直至整个序列变成按关键字非递减有序序列为止。,在自i-1起往前搜索的过程中，可以同时后移记录。,6,例,49386597761327,i=238(3849)6597761327,i=365(384965)97761327,i=497(38496597)761327,i=576(3849657697)1327,i=613(133849657697)27,i=1(),i=7(133849657697)27,27,97,76,65,49,38,27,排序结果：(13273849657697),7,记录按关键字非递增有序排列时比较的次数达最大值记录移动次数达到最大值,关键字间的比较次数和移动记录的次数,约为n2/4。由此，直接插入排序的时间复杂度为O（n2）。,记录按关键字非递减有序排列时比较的次数达最小值:记录不需要移动。,8,二、折半插入排序,插入排序的基本操作是在一个有序表中进行查找和插入，则从上章的讨论可知，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序。,9,i=1(30)1370853942620,i=213(1330)70853942620,.,i=820(613203039427085),折半插入排序,10,三、希尔排序,基本思想：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,排序过程：先取一个正整数d1n，把全部记录分成若干个组，所有距离为d1倍数的记录放一组，在各组内进行插入排序;然后取d2d1，重复上述分组和排序工作;直至di=1，即所有记录放进一个组中排序为止,11,例：4938659776132748554,49,13,38,27,65,48,97,55,76,4,12,27,4,55,38,13,希尔排序所需的比较和移动次数约为n1.3，当n时，可减少到n(log2n)2。,14,9.2交换排序,一、起泡排序二、快速排序,15,一、起泡排序,首先将最后一个记录的关键字与倒数第二个记录的关键字进行比较，若为逆序rn.keyrn-1.key，则将两个记录交换；然后依次类推，直至第2个记录和第1个记录的关键字比较为止。上述过程称作第一趟冒泡排序，其结果使得关键字最小的记录“漂浮”到第一个记录的位置上。,16,然后进行第二趟冒泡排序，对后n-1个记录进行同样操作，其结果是使关键字次小的记录“漂浮”到第2个记录的位置上。，重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。,17,例,3849657613273097,第一趟,38,49,76,97,13,97,27,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,30,18,算法描述与分析,起泡排序的效率，若初始序列为“正序”，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较；反之，若初序列“逆序”，则需进行n-1趟排序，需进行,次比较。并作等数量级的记录移动，因此，总的时间复杂度为O（n2）。,19,二、快速排序,其基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。,20,由此，可以该“枢轴”记录最后所落的位置最作分界线，将序列L.rs，L.rs+1，L.rt分割成两个子序列L.rs，L.rs+1，L.ri-1和L.ri+1，L.ri+2，L.rt，这个过程称作一趟快速排序。,一趟快速排序的具体做法是：对rst中记录进行一趟快速排序，附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为Pivotkey，,然后从low所指位置起向后搜索找到第一个关键字大于Pivotkey的记录和枢轴记录相互交换做，重复这两步直至low=high。,首先从high所指位置起向前搜索找到第一个关键字小于Pivotkey的记录和枢轴记录相互交换，,21,X初始关键字：,4938659776132750,完成一趟排序：(273813)49(76976550),22,分别进行快速排序(13)27(38)49(5065)76(97)快速排序结束：13273849506576,23,通常，快速排序平均时间复杂度为O(nlogn)，但待排序记录的键值几乎已排序时，情况反而恶化，每一趟快速排序的基准记录位置就是第一个记录位置或最后一个记录位置。最坏情况下的时间复杂度为T(n)=O(n)。,快速排序的平均时间为Tavg(n)=knlnn，其中n为待排序序列记录的个数，k为某个常数，经验证明，在所有同数量级的此类（先进的）排序方法中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。,快速排序递归算法需要栈空间来实现递归，一般情况下需要的空间为S(n)=O(log2n)，最坏情况下，需要的栈空间为S(n)=O(n)。,快速排序方法是不稳定的。,24,9.3选择排序,一、简单选择排序二、树形选择排序三、堆排序,25,一、简单选择排序,一趟简单选择排序的操作为：通过n-1次关键字的比较，从n个记录中选择出关键字最小的记录，并和第1个记录交换。,再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第2个记录交换,重复上述操作，共进行n-1趟排序后，排序结束.,26,初始：49386597761327,i=1,13,49,一趟:13386597764927,i=2,27,38,27,六趟:13273849657697,排序结束:13273849657697,28,简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为0，最大值为3(n-1)。然而，无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为(n(n-1)/2。因此，总的时间复杂度也是O（n2）。,算法描述与算法评价,29,二、树形选择排序,树形选择排序，又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法,首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。,30,树形选择排序示例,31,树形选择排序示例,输出13之后,32,树形选择排序示例,输出13、27之后,33,三、堆排序,2、堆和完全二叉树堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）,1、堆的定义n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆,34,例（13,38,27,50,76,65,49,97）,35,3、堆排序：若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则可得到n个元素的次小值；如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。,实现堆排序需解决的两个问题如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？二个问题解决方法筛选,36,4、筛选,37,38,39,40,41,42,43,5、建堆,建堆：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选,44,例如含8个元素的无序序列（49，38，65，97，76，13，27，50）,45,13,49,49,27,46,时间复杂度：最坏情况下T(n)=O(nlogn),空间复杂度：S(n)=O(1),总共进行的比较的次数为：2(log2(n-1)+log2(n-2)+log22)2n(log2n)由此，堆排序在最坏的情况下，其时间复杂度为O(nlogn)。,47,初始关键字:49386597761327,一趟归并后：38496597137627,二趟归并后：38496597132776,三趟归并后：13273849657697,9.4归并排序,48,时间复杂度：T(n)=O(nlog2n),空间复杂度：S(n)=O(n),与快速排序和堆排序相比，归并排序的最大特点，它是一种稳定的排序方法。但在一般情况下，很少利用2路归并排序方法进行内部排序。,49,9.5基数排序,一、多关键字排序二、链式基数排序,50,23A23A23A23A,一、多关键字排序,已知扑克牌中52张牌面的次序为：,两个关键字：花色（）面值（23A）并且“花色”地位高于“面值”,51,方法1：先对花色排序，将其分为4个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4个组连接起来即可最高优先法,52,方法2：先按13个面值给出13个编号组(2号，3号，.，A号)，将牌按面值依次放入对应的编号组，分成13堆。再按花色给出4个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3号组中牌取出分别放入对应花色组,这样，4个花色组中均按面值有序，然后，将4个花色组依次连接起来即可最低位优先法,53,一般情况下，假设有n个记录的序列R1，R2，Rn，且每个记录Ri中含有d个关键字（Ki0，Ki1，Kid-1），则称序列对关键字（K0，K1，Kd-1）有序是指：对于序列中任意两个记录Ri和Rj（1ijn）都满足下列有序关系,（Ki0，Ki1，Kid-1）（Kj0，Kj1，Kjd-1）其中K0称为最主位关键字，Kd-1称为最次位关键字。,54,为实现多关键字排序，通常有两种方法：(1)先对最高位关键字进行排序(MSD)最高优先法(2)先对最高低关键字进行排序(LSD)最低位优先法,55,第一种方法是先对最高位关键字K0（如花色）进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的K0值；,然后分别就每个子序列对次关键字K1（如面值）进行排序，按K1值不同再分成若干更小的子序列；,依次重复，直至对Kd-2进行排序之后得到的每一子序列中的记录都具有相同的关键字（K0，K1，Kd-2），而后分别每个子序列对Kd-1进行排序，最后将所有子序列依次联接在一起成为一个有序序列，这种方法称之为最高优先法（MostSignificantDigitfirst）（MSD)。,56,第二种方法是从最低位关键字Kd-1起进行排序。然后再对高一位的关键字Kd-2排序，依次重复，直至对最高位关键字K0排序后，便成为一个有序序列。这种方法称之为最低位优先法(LSD)。,MSD与LSD不同特点,按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。,按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次“分配”与“收集”实现排序。,57,二、链式基数排序,基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法,链式基数排序：用链表作存储结构的基数排序逻辑关键字可以看成由若干个关键字复合而成的。,58,由于如此分解而得的每个关键字Kj都在相同的范围内（对数字，0Kj9，对字母“A”KjZ”），按LSD进行排序更为方便，只要从最小数位关键字起，按关键字的不同值将序列中记录“分配”到RADIX个队伍中后再“收集”之，如此重复d次。,按这种方法实现排序称之为基数排序，其中“基”指的是RADIX的取值范围，在上述两种关键字的情况下，它们分别是“10”和“26”。,首先以静态链表存储n个待排记录，并令表头指针指向第一个记录，如图(a)所示。,59,第一趟分配对最低数位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至10个链对列中去，每个队列中的记录关键字的个位数相等，如图(b)所示。,其中fi和ei分别为第i个队列的头指针和尾指针；,第一趟收集是改变所有非空队列的对尾记录的指针值域，令其指向下一个非空队列的对头的记录，重新将10个队列中的记录链成一个链表，如图（c）所示；,第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如图(d)(g)所示，至此排序完毕。,60,链式基数排序举例,61,62,63,算法评价时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd),空间复杂度：S(n)=2rd个队列指针。+n个指针域空间,对于n个记录（假设每个记录含有d个关键字，每个关键字的取值范围为rd个值，进行链式基数排序的时间复杂度为O(d(n+rd)，其中每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需进行d趟分配和收集。,其中：n记录数d关键字数rd关键字取值范围,64,9.6各种内部排序方法的比较讨论,65,从上表可以得出如下结论：,（1）从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。,（2）上表中的“简单排序”包括除希尔排序之外的所有插入排序，起泡排序和简单选择排序，其中以直接插入排序为最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法，因此常将它和其它的排序方法，诸如快速排序、归并排序等结合起来使用。,66,（3）基数排序的时间复杂度也可写成O(nd)。因此，它最适合用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则也可先按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。,（4）从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n2)的简单排序也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。,67,1、对于给定的键值序列12，2，16，30，8，28，4，10分别写出直接插入排序、折半插入排序、希尔排序、直接选择排序、起泡排序的过程，并算出比较和记录移动次数。,第9章作业,68,2、对于给定的键值序列41，62，13，84，35，96，57，39，79，61，15，83，分别写出快速排序、归并排序、堆排序的各趟排序结果。3、本章介绍的内部排序方法中，哪几种是稳定的？哪几种是不稳定的？,69,一、单项选择题1、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列