数据结构预算法第十章排序

10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6各种排序方法的比较典型例题第十章排序10.1概述1.排序就是将一组任意顺序的数据按一定的规律排列起来的过程。2.排序过程中的两种基本操作(1)比较两个关键值的大小。(2)根据比较结果，移动记录的位置。3.对关键字排序的3个原则：(1)关键字值为数值型，则按键值大小为依据。(2)关键字值为ASCII码，则按键值的内码编排顺序为依据。(3)关键字值为汉字字符串类型，则大多以汉字拼音的字典次序为依据。4.排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对元先具有相同的键值元素间的位置关系，排序前和排序后保持一致，称此排序方法为稳定排序，反之称为不稳定排序。5.待排序记录的3种存储方式(1)待排序记录存放在地址连续的一组存储单元上（线性表的顺序存储结构类似）。(2)待排序记录放在静态链表中（记录之间的次序关系由指针指示，排序不需要移动记录）。(3)待排序记录存放在地址连续的一组存储单元，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束后，再按照地址向量中的值调整记录的存储位置。6.内排序：整个排序过程都在内存进行的排序为内排序。7.外排序：待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。10.2插入排序10.2.1直接插入排序1.基本思想：直接插入排序是将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。{48}62357755143598{4862}357755143598{354862}7755143598{35486277}55143598{3548556277}143598{143548556277}3598{14353548556277}98{1435354855627798}2.监视哨的作用：（1）在进入确定插入位置的循环之前，保存了插入值r[i]的副本，避免因记录的移动而丢失r[i]中的内容。（2）使内循环总能够结束，以免循环过程中数组下标越界。3.效率分析直接插入排序是稳定排序，最适合待排序关键字基本有序的序列。时间复杂度O(),辅助空间为O(1)。2n例设待排序的表有10个记录,其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用直接插入排序方法进行排序的过程。初始关键字9876543210i=1[89]76543210i=2[789]6543210i=3[6789]543210i=4[56789]43210i=5[456789]3210i=6[3456789]210i=7[23456789]10i=8[123456789]0i=9[0123456789]10.2.2二分插入排序highlowi插入位置58612397751436495280imm14364952586180239775highlow插入位置imm14364952586180239775highlow插入位置1.基本思想：直接插入排序算法虽简单，但当记录数量大时，则比较次数将大大增加，对于有序表，为了减少关键字的比较次数，可采用二分插入排序。2.效率分析二分插入排序是稳定的排序。时间复杂度和空间复杂度和直接插入排序的一样。10.2.3希尔排序希尔排序又称“缩小增量排序”，它也是一种插入排序的方法，但时间上比前两种排序方法有比较大的改进。1.基本思想：先将整个待排序记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序时”，再对全体记录进行一次直接插入排序。2.特点：子序列不是简单的逐段分割，而是将相隔某个“增量”的记录组成一个子序列，所以关键字较小的记录不是一步一步地前移，而是跳跃式前移，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序。3.效率分析：希尔排序是一种不稳定排序。例如：162512304711233691831第一趟希尔排序，设增量d=5112312918162536304731第二趟希尔排序，设增量d=3918121123162531304736第三趟希尔排序，设增量d=1911121618232530313647例设待排序的表有10个记录,其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序的过程。9876543210初始状态(连线部分为下一趟作准备)4321098765d=5(d=5执行结果)0123456789d=2(d=2执行结果)0123456789d=1(d=1执行结果)10.3快速排序快速排序又称为交换排序，是根据记录的关键字的大小，通过记录交换来实现排序的。10.3.1.冒泡排序1.基本思想：冒泡排序也称沉底法，每相邻两个记录关键字比较大小，大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数）。2.效率分析：冒泡排序是一种稳定排序。例如：例设待排序的表有10个记录,其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用冒泡排序方法进行排序的过程。初始关键字9876543210i=00987654321i=10198765432i=20129876543i=30123987654i=40123498765i=50123459876i=60123456987i=70123456798i=8012345678910.3.2快速排序1.基本思想：任取待排序序列中的某个元素作为基准，通过一趟快速排序将待排序的元素分割成左右两个子序列，其中左子序列元素的排序关键字均比基准（也称为枢轴）元素的关键字值小；右子序列元素的关键字均比基准元素的关键字值大，基准元素得到了它在整个序列中的最终位置并被存放好，这个过程称为一趟快速排序。2.效率分析：快速排序是不稳定排序。例设待排序的表有10个记录,其关键字分别为{6,8,7,9,0,1,3,2,4,5}。说明采用快速排序方法进行排序的过程。初始关键字68790132455423016978142305697801234569780123456978012345697801234569780123456879012345678910.4选择排序选择排序是从待排序序列中选取一个关键字值最小的记录，把它与第一个记录交换存储位置，使之成为有序。然后在余下的无序的记录中，再选出关键字最小的记录与无序区中的第一个记录交换位置，又使之成为有序。依此类推，直至完成整个排序。10.4.1简单选择排序基本思想:(1)初始状态：整个数组r划分成两个部分，即有序区（初始为空）和无序区。(2)基本操作：从无序区中选择关键字值为最小的记录，将其与无序区的第一个记录交换位置（实质是添加到有序区尾部。）(3)从初态（有序区为空）开始，重复步骤（2），直到终态（无序区为空）。效率分析：简单选择排序是不稳定排序。例如例：设待排序的表有10个记录,其关键字分别为{6,8,7,9,0,1,3,2,4,5}。说明采用直接选择排序方法进行排序的过程。初始关键字6879013245i=00879613245i=10179683245i=20129683745i=30123689745i=40123489765i=50123459768i=60123456798i=70123456798i=8012345678910.4.2堆排序堆排序是利用堆树来进行排序的方法。堆树是一种特殊的完全二叉树，如果该完全二叉树中每一个结点的值均大于或等于它的两个子结点的值，则称其为大顶堆（或大根堆）；如果该完全二叉树中每一个结点的值均小于或等于它的两个子结点的值，则称其为小顶堆（或小根堆）。基本思想：（1）建堆：把用数组存储的n个待排序数据，看作成一棵完全二叉树的顺序存储形式，并对这棵完全二叉树进行一系列的比较交换，将其建成一棵堆树。（2）交换：将堆顶数据和当前待排序序列的最后那个数据相交换，堆顶数据即可排到其最终位置，待排序数据从而减少一个。（3）调整：由于最后那个数据交换到堆顶，它破坏了原有的堆结构，应将其不断向下交换，直到剩余的待排序数据重新调整成一棵堆树。（4）不断重复（2）（3）两步，直到待排序数据只剩下一个为止，此时所有数据即已排成有序。堆的定义完全二叉树的数组表示KiK2i+1&&KiK2i+2KiK2i+1&&KiK2i+2例设待排序的结点键值序列为e[]={93,35,29,45,48,82,76,17,},按上述思想形成如下图所示的初始堆。例设待排序的表有10个记录,其关键字分别为{6,8,7,9,0,1,3,2,4,5}。说明采用堆排序方法进行排序的过程。68790241359876524130(a)初始状态(b)建立的初始堆087652413867452013(a)交换9与0，输出9(b)筛选调整06745213(c)交换8与0，输出8763452102634510(d)筛选调整(e)交换7与2，输出76534210(f)筛选调整堆排序过程：053421543021(g)交换6与0，输出6(h)筛选调整(i)交换5与1，输出51430242301(j)筛选调整1232320(k)交换4与1，输出4(l)筛选调整(m)交换3与1，输出3021201(n)筛选调整11010(o)交换2与1，输出2(p)筛选调整(q)交换1与0，输出1010(r)输出010.5归并排序归并排序是将两个或两个以上的有序子表合并成为一个新的有序表。基本思想：（1）将n个记录的待排序序列看成是由n个长度都1的有序子表组成。（2）将两个相邻的子表归并为一个有序子表。（3）重复上述步骤，直至归并为一个长度为n的有序表。归并排序的示例为：(19)(13)(05)(27)(01)(26)(31)(16)(13,19)(05,27)(01,26)(16,31)(05,13,19,27)(01,16,26,31)(01,05,13,16,19,26,27,31)例设待排序的表有8个记录,其关键字分别为{18,2,20,34,12,32,6,16}。说明采用归并排序方法进行排序的过程。初始关键字18220341232616第1趟归并21820341232616第2趟归并21820346121632第3趟归并26121618203234基数排序前面所讨论的排序算法均是基于关键字之间的比较来实现的,而基数排序是通过“分配”和“收集”过程来实现排序,是一种借助于多关键字排序的思想对单关键字排序的方法。例设待排序的表有10个记录,其关键字分别为{75,23,98,44,57,12,29,64,38,82}。说明采用基数排序方法进行排序的过程。初始关键字75239844571229643882按个数排序12822344647557983829按十位排序1223293844576475829810.6各种排序方法的比较通常可按平均时间将排序方法分为三类：（1）平方阶O(n2)排序，一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶O(nlog2n)排序，如快速、堆和归并排序；（3）线性阶O(n)排序，如基数排序。排序方法时间复杂度空间复杂度稳定性复杂性平均情况最坏情况最好情况直接插入排序O(n2)O(n2)O(n)O(1)稳定简单希尔排序O(nlog2n)O(nlog2n)O(1)不稳定较复杂冒泡排序O(n2)O(n2)O(n)O(1)稳定简单快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定较复杂直接选择排序O(n2)O(n2)O(n2)O(1)不稳定简单堆排序O(nlog2n)O(nlog2n)O(nlog2