1、第十章第十章排序排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较10.1 概概 述述一、排序的定义一、排序的定义二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类一、什么是排序？一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,49,23,97,75调整为1
2、4,23,36,49,49,52,58,61,75,80,97姓名姓名年龄年龄体重体重1李由李由57622王天王天54763七大七大24754张强张强24725陈华陈华2453如果按关键字年龄用一种方法排序后得到下表：如果按关键字年龄用一种方法排序后得到下表：注意反色的三条记录保持原有排列顺序，则称该排序方法是注意反色的三条记录保持原有排列顺序，则称该排序方法是稳定的稳定的！姓名姓名年龄年龄体重体重3七大七大24754张强张强24725陈华陈华24532王天王天54761李由李由5762如果另一方法排序后得到下表：如果另一方法排序后得到下表：姓名姓名年龄年龄体重体重4张强张强24723七大七大
3、24755陈华陈华24532王天王天54761李由李由5762原原3,4,5记录顺序改变，则称该排序方法是记录顺序改变，则称该排序方法是不稳定的不稳定的！一般情况下，假设含n个记录的序列记录的序列为 R1,R2,，Rn 其相应的关键字序列关键字序列为 K1,K2,，Kn 这些关键字相互之间可以进行比较比较，即在它们之间存在着这样一个关系关系：Kp1Kp2Kpn按此固有关系将上式记录序列重新排列将上式记录序列重新排列为 Rp1,Rp2,，Rpn 的操作操作称作排序排序。排序算法的稳定性：排序算法的稳定性：如果待排序的序列中，存在多个具有多个具有相同关键字的记录相同关键字的记录，若经过排序这些记录
4、的相对次序保持不变相对次序保持不变，则称这种排序算法是稳定稳定的；经过排序这些记录的相对次序相对次序发生了改变发生了改变，则称这种排序算法是不稳定不稳定的。的。二、内部排序和外部排序二、内部排序和外部排序 待排序记录存放在计算机随机存储器随机存储器中进行的排序过程，为内部排序内部排序；反之,若待排序记录的数量很大，以至内存一次不能容纳全部记录内存一次不能容纳全部记录，在排序过程中尚需对外存外存进行访问的排序过程，为外部外部排序排序。三、内部排序的方法三、内部排序的方法 内部排序的过程是一个内部排序的过程是一个逐步扩大记录逐步扩大记录的有序序列长度的有序序列长度的过程。在排序的过的过程。在排序的
5、过程中，参与排序的记录序列中存在两程中，参与排序的记录序列中存在两个区域：个区域：有序区和无序区有序区和无序区。使有序区中记录的数目增加一个或几使有序区中记录的数目增加一个或几个的操作称为一趟排序。个的操作称为一趟排序。有序序列区有序序列区 无 序 序 列 区经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区逐步扩大记录有序序列长度的方法大致有下列几类：1.1.插入类插入类 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；如直接插入排序,折半插入排序,希尔排序.2.2.交换类交换类 通过“交换”无序序列中的记录从而得到其中关键字
6、最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;如起泡排序,快速排序,3.3.选择类选择类 从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;如简单选择排序.树形选择排序,堆排序.4.4.归并类归并类 通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;如归并排序5.5.其它方法其它方法 如基数排序 下面将对每一类的排序算法介下面将对每一类的排序算法介绍一至两个排序算法。绍一至两个排序算法。10.2 插插 入入 排排 序序一趟直接插入排序直接插入排序的基本思想：把把n n个记录的
7、序列划分为已个记录的序列划分为已排序部分排序部分和和未排序部分未排序部分，将记录将记录RiRi 插入到有序子序列插入到有序子序列R1.i-1R1.i-1中，使记录的有中，使记录的有序序列从序序列从R1.i-1R1.i-1变为变为R1.iR1.i。有序序列R1.i-1无序序列 Ri.nRi显然，完成这个“插入”需分三步进行：1查找Ri的插入位置j+1；2将Rj+1.i-1中的记录后移一个位置；3将Ri复制到Rj+1的位置上。直接插入直接插入排序排序（基于顺序查找）（基于顺序查找）折半插入折半插入排序排序（基于折半查找）（基于折半查找）希尔希尔排序排序（基于逐趟缩小增量）（基于逐趟缩小增量）利用“
8、顺序查找顺序查找”实现“在R1.i-1中查找查找Ri的插入位置”示例示例:初始状态初始状态 18 12 10 12 30 16 第第1趟（趟（i=2）(12)12 18 10 12 30 16 第第2趟（趟（i=3）(10)10 12 18 12 30 16 第第3趟（趟（i=4）(12)10 12 12 18 30 16 第第4趟（趟（i=5）(30)10 12 12 18 30 16 第第5趟（趟（i=6）(16)10 12 12 16 18 30待排序记录序列为待排序记录序列为(18(18，1212，1010，1212，3030，1616）简单插入排序每一趟执行后的序列状态简单插入排序每
9、一趟执行后的序列状态:监视哨监视哨一、直接插入排序一、直接插入排序从Ri-1起向前向前进行顺序查找，监视哨设置在R0；R0=Ri;/设置设置“哨兵哨兵”循环结束表明Ri的插入位置为 j+1R0jRifor(j=i-1;R0.keyRj.key;-j);/从后往前找从后往前找j=i-1插入位置插入位置算法的实现要点：算法的实现要点：对于在查找过程中找到的那些关键字大于Ri.key的记录，在查找的同时实现记录向后移动；for(j=i-1;R0.key Ri+1.key,Ri.key Ri+1.key,则则交换交换RiRi和和Ri+1Ri+1的位置。第一趟全部比较完毕的位置。第一趟全部比较完毕后后R
10、nRn是序列中最大的记录是序列中最大的记录。再从再从R1R1开始两两比较开始两两比较RiRi和和Ri+1 Ri+1(i=1,2,.,n-2i=1,2,.,n-2)的关键字的大小，若的关键字的大小，若Ri.key Ri+1.keyRi.key Ri+1.key则则交换交换RiRi和和Ri+1Ri+1的位置。第二趟全部比较完毕后的位置。第二趟全部比较完毕后Rn-1Rn-1是序是序列中次大记录列中次大记录。如此反复，进行如此反复，进行n-1n-1趟趟冒泡排序后所有待排序冒泡排序后所有待排序的的n n个记录序列按关键字有序个记录序列按关键字有序。假设在排序过程中，记录序列R1.n的状态为：第 i 趟起
11、泡排序无序序列R1.n-i+1有序序列 Rn-i+2.nn-i+1无序序列R1.n-i有序序列 Rn-i+1.n比较相邻记录，将关关键字最大的记录键字最大的记录交换交换到 n-i+1 的位置上冒泡排序示例冒泡排序示例初始状态初始状态 65 97 76 13 27 49 58 第第1趟趟 65 76 13 27 49 58 97第第2趟趟 65 13 27 49 58 76 97第第3趟趟 13 27 49 58 65 76 97第第4趟趟 13 27 49 58 65 76 97第第5趟趟 13 27 49 58 65 76 97第第6趟趟 13 27 49 58 65 76 97设待排记录序
12、列的关键字为设待排记录序列的关键字为(65,97,76,13,27,49,58)(65,97,76,13,27,49,58)冒泡排序每一趟执行后的序列状态如下：冒泡排序每一趟执行后的序列状态如下：目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动移动至该记录之前至该记录之前，反之，凡关键字大于枢轴关键字大于枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分分割成两部分割成两部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1)枢轴枢轴 (i+1jt)。二、一趟
13、快速排序（一次划分）二、一趟快速排序（一次划分）52 49 80 36 14 58 61 97 23 75stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow 可见，经过可见，经过“一次划分一次划分”，将关键字序列，将关键字序列 52,49,80,36,14,58,61,97,23,75 调整为调整为:23,49,14,36,(52)
14、58,61,97,80,75 在调整过程中，设立了两个指针：low 和high，它们的初值分别为：s 和 t，之后逐渐减小 high，增加 low，并保证 Rhigh.key52，和 Rlow.key52,否则进行记录的“交换”。三、快速排序三、快速排序 首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行进行快速排序快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序四、快速排序的时间分析四、快速排序的时间分析假设一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间：其中 Tpass(n)为
15、对 n 个记录进行一次划分所需时间。若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)结论结论:快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)10.4 选选 择择 排排 序序简简 单单 选选 择择 排排 序序堆堆 排排 序序树树 形形 选选 择择 排排 序序一、简单选择排序一、简单选择排序基本思想基本思想：一趟简单选择排序的操作为：通一趟简单选择排序的操作为：通过过n-in-i次次关键字间的比较，从关键字间的比较，从n-i+1n-i+1个个记录中记录中选出选出关键字最小关键字最小的记录的记录
16、，并和，并和第第i i（1in)1in)个记录交换之。个记录交换之。对对L.r1.n中记录进行简单选择排中记录进行简单选择排序的算法为：序的算法为：令令i从从1至至n-1,进行进行n-1趟选趟选择操作。择操作。假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n简单选择排序简单选择排序初始状态初始状态 2 7 2 4 3 1 第第1趟（趟（i=1）1 7 2 4 3 2第第2趟（趟（i=2）1 2 7 4 3 2 第第3趟（趟（i=3）1 2 2 4 3 7第第4趟（趟（i=4）1 2
17、 2 3 4 7 第第5趟（趟（i=5）1 2 2 3 4 7待排序记录序列的关键字序列为（待排序记录序列的关键字序列为（2 2，7 7，2 2，4 4，3 3，1 1）简单选择排序每一趟执行后的序列状态：简单选择排序每一趟执行后的序列状态：简单选择排序的算法描述如下：void SelectSort(Elem R,int n)/对记录序列对记录序列R1.n作简单选择排序。作简单选择排序。for(i=1;in;+i)/选择第选择第 i 小的记录，并交换到位小的记录，并交换到位 /SelectSortj=SelectMinKey(R,i);/在在 Ri.n 中选择关键字最小的记录中选择关键字最小的
18、记录if(i!=j)RiRj;/与第与第 i 个记录交换个记录交换时间性能分析时间性能分析 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数关键字间的比较次数 总计为：2)1()(11nninni其时间复杂度为其时间复杂度为O(nO(n2 2)二、树形选择排序二、树形选择排序 树形选择排序树形选择排序又称又称锦标赛排序锦标赛排序，是，是一种按照锦标赛的思想进行选择排序的一种按照锦标赛的思想进行选择排序的方法。方法。基本思想基本思想：首先对首先对n n个记录的关键字进行个记录的关键字进行两两两两比较比较，然后在其中，然后在其中n/2n/2个较小者个较小者之间再之间再进行进行两两比较
19、两两比较，如此重复，直至选出最，如此重复，直至选出最小关键字的记录为止。小关键字的记录为止。384965977613274938651327381313选出选出最小关键字最小关键字13例：例：49 38 65 97 76 13 27 493849659776274938657627382727 将叶结点中的最小关键字将叶结点中的最小关键字(13)改为改为最大最大值值（），然后修改，然后修改该叶子结点到根的路径该叶子结点到根的路径上各结点的关键字上各结点的关键字，则根结点的关键字即，则根结点的关键字即为次小关键字。由此选出为次小关键字。由此选出次小关键字次小关键字27。3849659776493
20、8657649384938 同理，可依次选出从小到大的所有关同理，可依次选出从小到大的所有关键字。居键字。居第三的关键字为第三的关键字为38。树形选择排序的特点：树形选择排序的特点：树形选择排序的树形选择排序的时间复杂度时间复杂度为为O(nlog2n)。这种排序方法尚有这种排序方法尚有辅助存储空间较多辅助存储空间较多，和和“最大值最大值”进行多余的比较进行多余的比较等特点。等特点。为了弥补这一缺点，可采用另一形式为了弥补这一缺点，可采用另一形式的选择排序的选择排序堆排序堆排序。rir2i r2i+1 完全二叉树中 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。三、堆排序三、堆排序
21、堆是满足下列性质的数列r1,r2,，rn：或或122iiiirrrr122iiiirrrr堆的定义堆的定义:(小顶堆小顶堆)(大顶堆大顶堆)i=1,2,.,n/21236276549817355403498例如例如:是堆是堆14不不 堆排序即是利用堆排序即是利用堆的特性堆的特性对记录序对记录序列进行排序的一种排序方法。列进行排序的一种排序方法。如何由一个如何由一个无序序列无序序列“建堆建堆”？实现堆排序需要解决实现堆排序需要解决两个问题两个问题:如何在如何在输出堆顶元素输出堆顶元素之后，之后，调调整剩余元素成为一个新的堆整剩余元素成为一个新的堆？建堆建堆是一个从下往上进行调整的过程是一个从下往
22、上进行调整的过程。40554973816436122798例如例如:建大顶堆建大顶堆,排序之前的关键字序列为123681734998817355 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。9849406436122740,55,49,73,12,27,98,81,64,36如何在输出堆顶元素之后，调整如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？剩余元素成为一个新的堆？假设在输出假设在输出堆顶元素堆顶元素之后，以之后，以堆中堆中最后一个元素最后一个元素替代之，此时，替代之，此时，根结点的左右子树均为堆，则仅需根结点的左右子树均为堆，则仅需自上至下进行
23、调整自上至下进行调整即即“筛选筛选”。所谓“筛选筛选”指的是，自自堆顶至堆顶至叶子重新调整为大顶堆或小顶堆的叶子重新调整为大顶堆或小顶堆的过程过程。堆堆堆堆筛选筛选98814973556412362740例如例如:是大顶堆是大顶堆12在在9898和和1212进行互换即输出进行互换即输出9898之后，它就之后，它就不不是堆了。是堆了。因此，需要对它进行因此，需要对它进行“筛选筛选”。98811298比较比较比较12731264例：例：13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 27
24、3849502765769713输出：13 276549502738769713输出：13 27 38小顶堆小顶堆13,38,27,50,76,65,49,9713,38,27,50,76,65,49,97输出堆顶元素并写出调整建堆的过程输出堆顶元素并写出调整建堆的过程.4965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 5097657627384
25、95013输出：13 27 38 49 50 6510.5 归归 并并 排排 序序 归并排序的过程基于下列基本基本思想思想进行：将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻位置相邻的记录有序子序列归并为一个一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n这个操作对顺序表而言，是轻而易举的。2-2-路归并排序的过程路归并排序的过程初始状态初始状态 25 57 4837 1292 86第趟归并第趟归并 25 57 37 48 12 92 86第趟归并第趟归并 25
26、 374857 128692第趟归并第趟归并 12 253748578692待排记录序列为待排记录序列为(25,57,48,37,12,92,86)(25,57,48,37,12,92,86)路归并排序路归并排序每一趟执行后的序列状态每一趟执行后的序列状态:容易看出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即：每一趟归并的时间复杂度为 O(n)，总共需进行 log2n 趟。10.7 各种排序方法的综合比较各种排序方法的综合比较一、排序方法的稳定性能一、排序方法的稳定性能 1.稳定的排序方法指的是，对于两个关键两个关键字相等字相等的记录，它们在序列中的相对位置在序列中的相对位置，
27、在排序之前和经过排序之后，没有改变排序之前和经过排序之后，没有改变。2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法稳定的排序方法。排序之前:Ri(K)Rj(K)排序之后:Ri(K)Rj(K)例如：例如：排序前(56,34,47,23,66,18,82,47)若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是稳定稳定的;若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是不稳定不稳定的。3.对于不稳定的排序方法，只要能举出一个实例说明即可。4.快速排序、堆排序和希尔排序是不稳定的排序方法。例如例如:对 4,
28、3,4,2 进行快速排序，得到 2,3,4,4 二、时间性能二、时间性能1.平均的时间性能平均的时间性能基数排序基数排序时间复杂度为时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间复杂度为时间复杂度为 O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和简单选择排序简单选择排序时间复杂度为时间复杂度为 O(n):2.当待排记录序列按当待排记录序列按关键字顺序有序关键字顺序有序时时 3.简单选择排序、堆排序和归并排序简单选择排序、堆排序和归并排序的时间性能不随不随记录序列中关键字的分布而改变。直接插入排序直接插入排序和起泡排序起泡排序能达到O(n)的时间复杂度，快速排序快速排序的时间性能蜕化为O(n2)。二、空间性能二、空间性能(略略)指的是排序过程中所需的辅助空间大小 1.所有的简单排序方法简单排序方法(包括：直接插入、起泡和简单选择)和堆排序堆排序的空间复杂度为为O(1)；2.快速排序为快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；3.归并排序归并排序所需辅助空间最多，其空间复杂度为 O(n);4.链式基数排序链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。
