前言前言 排序与我们日常生活中息息相关，比如，我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按 照出发时间或者时长排序、买东西会按照销量或者好评度排序、查找文件会按照修改时间排序等等。在计算机程 序设计中，排序和查找也是最基本的算法，很多其他的算法都是以排序算法为基础，在一般的数据处理或分析 中，通常第一步就是进行排序，比如说二分查找，首先要对数据进行排序。 本文着重讲解了数据结构中比较重要的排序环节，对各种排序算法做了详细的说明和讲解，帮助读者迅速掌握排 序的基本原理。 适用人群适用人群 本文是基础教程，数据结构和算法是编程能力提高的关键，所以本文适合编程初学者，同时也适合有一定编程能 力的开发人员。 学习前提学习前提 在你开始做本文提供的各种类型例子练习之前，你需要对 C 语言有一定的了解，有高等数学基础的人学习本文会 更加轻松。 鸣谢：http://blog.csdn.net/jackyvincefu/article/category/1698579 目录目录 前言前言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 第 1 章第 1 章 排序的基本概念排序的基本概念. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 第 2 章第 2 章 直接插入排序直接插入排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 第 3 章第 3 章 希尔排序希尔排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212 第 4 章第 4 章 冒泡排序冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1616 第 5 章第 5 章 快速排序快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2121 第 6 章第 6 章 直接选择排序直接选择排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2727 第 7 章第 7 章 堆排序堆排序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3030 第 8 章第 8 章 归并排序归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3535 第 9 章第 9 章 箱排序箱排序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4040 第 10 章第 10 章 基数排序基数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4444 第 11 章第 11 章 各种内部排序方法的比较和选择各种内部排序方法的比较和选择. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4747 11 排序的基本概念排序的基本概念 排序（sort）或分类排序（sort）或分类 所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下： 输入：n 个记录 R1，R2，…，Rn，其相应的关键字分别为 K1，K2，…，Kn。 输出：Ril，Ri2，…，Rin，使得 Ki1≤Ki2≤…≤Kin。(或 Ki1≥Ki2≥…≥Kin)。 1．被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键 字(Key)。 注意： 在不易产生混淆时，将关键字项简称为关键字。 2．排序运算的依据--关键字 用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。 关键字的选取应根据问题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内 容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需 用"总分数"作为关键字。 排序的稳定性排序的稳定性 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持 不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定 的。 注意： 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法 不满足稳定性要求，则该排序算法就是不稳定的。 第 1 章 排序的基本概念 | 4 排序方法的分类排序方法的分类 1．按是否涉及数据的内、外存交换分 在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内 排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。 注意： • 内排序适用于记录个数不很多的小文件。 • 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。 2．按策略划分内部排序方法 可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。 排序算法分析排序算法分析 1．排序算法的基本操作 大多数排序算法都有两个基本的操作： (1) 比较两个关键字的大小； (2) 改变指向记录的指针或移动记录本身。 注意： 第(2)种基本操作的实现依赖于待排序记录的存储方式。 2．待排文件的常用存储方式 （1） 以顺序表(或直接用向量)作为存储结构 排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）。 （2） 以链表作为存储结构 排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序。 （3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引 表) 第 1 章 排序的基本概念 | 5 排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链 表上实现，仍需避免排序过程中移动记录的排序方法。 3．排序算法性能评价 （1） 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条： • 执行时间和所需的辅助空间 • 算法本身的复杂程度 （2） 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为O(n)。 （3） 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的 规模，还取决于输入实例中数据的状态。 文件的顺序存储结构表示文件的顺序存储结构表示 #define n l00 //假设的文件长度，即待排序的记录数目 typedef int KeyType； //假设的关键字类型 typedef struct{ //记录类型 KeyType key； //关键字项 InfoType otherinfo；//其它数据项，类型InfoType依赖于具体应用而定义 }RecType； typedef RecType SeqList[n+1]；//SeqList为顺序表类型，表中第0个单元一般用作哨兵 注意： 若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。 【例】关键字为字符串时，可定义宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a=1")。 注意： - 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 第 2 章 直接插入排序 | 9 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可 观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视 为雕虫小技，而应该深刻理解并掌握这种技巧。 给定输入实例的排序过程给定输入实例的排序过程 设待排序的文件有8个记录，其关键字分别为：49，38，65，97，76，13，27，49。为了区别两个相同的关键 字49，后一个49的下方加了一下划线以示区别。其排序过程见【动画模拟演示】 (http://student.zjzk.cn/cours e_ware/data_structure/web/flashhtml/insertsort.htm) 。 算法分析算法分析 1．算法的时间性能分析 对于具有 n 个记录的文件，要进行 n-1 趟排序。 各种状态下的时间复杂度： ┌─────────┬─────┬──────┬──────┐ │ 初始文件状态 │ 正序 │ 反序 │无序(平均)│ ├─────────┼─────┼──────┼──────┤ │ 第i趟的关键 │ 1 │ i+1 │（i-2）/2│ │ 字比较次数 │ │ │ │ ├─────────┼─────┼──────┼──────┤ │总关键字比较次数 │n-1 │(n+2)(n-1)/2│ ≈n2/4│ ├─────────┼─────┼──────┼──────┤ │第i趟记录移动次数 │ 0 │ i+2 │ （i-2）/2│ ├─────────┼─────┼──────┼──────┤ │总的记录移动次数 │ 0 │(n-1)(n+4)/2│ ≈n2/4│ ├─────────┼─────┼──────┼──────┤ │时间复杂度 │ 0（n）│ O（n2） │ O（n2）│ └─────────┴─────┴──────┴──────┘ 注意：初始文件按关键字递增有序，简称"正序"。初始文件按关键字递减有序，简称"反序"。 2．算法的空间复杂度分析 算法所需的辅助空间是一个监视哨，辅助空间复杂度 S(n)=O(1)。是一个就地排序。 3．直接插入排序的稳定性 第 2 章 直接插入排序 | 10 直接插入排序是稳定的排序方法。 第 2 章 直接插入排序 | 11 33 希尔排序希尔排序 本节介绍第二种插入排序方法：希尔排序。 希尔排序(Shell Sort)是插入排序的一种。因 D.L.Shell 于 1959 年提出而得名。 希尔排序基本思想希尔排序基本思想 基本思想： 先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 d1 的倍数的记录放在 同一个组中。先在各组内进行直接插人排序；然后，取第二个增量 d20&&R[0].key0 do { increment=increment/3+1； //求下一增量 ShellPass(R，increment)； //一趟增量为increment的Shell插入排序 }while(increment>1) } //ShellSort 注意： 当增量 d=1 时，ShellPass 和 InsertSort 基本一致，只是由于没有哨兵而在内循环中增加了一个循环 判定条件"j>0"，以防下标越界。 算法分析算法分析 1．增量序列的选择 Shell 排序的执行时间依赖于增量序列。 好的增量序列的共同特征： • 最后一个增量必须为 1； • 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。 2．Shell 排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因： • 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 • 当 n 值较小时，n 和 n2 的差别也较小，即直接插入排序的最好时间复杂度 O(n)和最坏时间复杂度 0(n2)差 别不大。 • 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量 di 逐渐缩 小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有 序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。 第 3 章 希尔排序 | 14 3．稳定性 希尔排序是不稳定的。参见上述实例，该例中两个相同关键字 49 在排序前后的相对次序发生了变化。 第 3 章 希尔排序 | 15 44 冒泡排序冒泡排序 交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序 的记录为止。应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。 本文介绍第一种交换排序方法：冒泡排序。 排序方法排序方法 将被排序的记录数组 R[1..n]垂直排列，每个记录 R[i]看作是重量为 R[i].key 的气泡。根据轻气泡不能在重气泡之 下的原则，从下往上扫描数组 R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任 何两个气泡都是轻者在上，重者在下为止。 （1）初始 R[1..n]为无序区。 （2）第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比 较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key=i；j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key=pivot.key) //pivot相当于在位置i上 j--； //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] if(ipivot.key R[j--]=R[i]; //相当于交换R[i]和R[j]，交换后j指针减1 } //endwhile R[i]=pivot； //基准记录已被最后定位 return i； } //partition 快速排序执行过程快速排序执行过程 快速排序执行的全过程可用递归树来描述。 分析： • 递归执行的路线如图中带箭头的包络线所示。 • 递归树上每一结点左旁方括号表示当前待排序的区间，结点内的关键字是划分的基准关键字 注意： 叶结点对 应的子区间只有一个关键字，无须划分，故叶结点内没有基准关键字 • 划分后得到的左、右两个子区间分别标在该结点的左、右两个孩子结点的左边方括号内。 【例】根结点左旁 方括号[49，38，65，97，76，13，27，49]表示初始待排序的关键字，根内的 49 表示所选的划分基准记 录的关键字，划分结果是[27，28，13]49[76，97，65，49_]，其左右子区间分别标在根结点的两个孩子的 左边。 • 每个分支结点右旁圆括号中的内容表示对该结点左旁区间的排序过程结束之后返回的结果。它是其左右孩子 对应的区间排序完成之后，将左右孩子对应的排序结果分别放在该分支结点的关键字前后所得到的关键字序 列。 【例】分支结点 76 的左右孩子对应的区间排序后的结果分别是(49_，65)和(97)，将它们分别放在 76 的前后即得(49，65，76，97)，这是对结点76左旁区间[76，97，，65，49]排序的结果。 • 算法的执行顺序是递归树中的箭头顺序，实际上当把划分操作视为访问结点的操作时，快速排序的执行过程 相当于是先序遍历其递归树。 注意： 任何递归算法均可用递归树来描述其执行过程。 第 5 章 快速排序 | 24 快速排序各次划分后的状态变化快速排序各次划分后的状态变化 [49 38 65 97 76 13 27 49] //初始关键字 [27 38 13] 49 [76 97 65 49] //第 1 次划分完成之后，对应递归树第 2 层 [13] 27 [38] 49 [49 65] 76 [97] //对上一层各无序区划分完成后，对应递归树第 3 层 13 27 38 49 49 [65] 76 97 //对上一层各无序区划分完成后，对应递归树第 4 层 13 27 38 49 49 65 76 97 //最后的排序结果 算法分析算法分析 快速排序的时间主要耗费在划分操作上，对长度为 k 的区间进行划分，共需 k-1 次关键字的比较。 1. 最坏时间复杂度 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为 空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少 一个。 因此，快速排序必须做 n-1 次划分，第i次划分开始时区间长度为 n-i+1，所需的比较次数为 n- i(1≤i≤n-1)，故总的比较次数达到最大值：Cmax = n(n-1)/2=O(n2) 如果按上面给出的划分算法，每次取当前无序区的第 1 个记录为基准，那么当文件的记录已按递增序(或递减 序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而 最多。 1. 最好时间复杂度 在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的 长度大致相等。总的关键字比较次数：O(nlgn) 注意： 用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树 的高度为 O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个 排序过程所需要的关键字比较总次数 C(n)=O(nlgn)。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为 O(n2)，最好时间复杂 度为 O(nlgn)。 1. 基准关键字的选取 在当前无序区中选取划分的基准关键字是决定算法性能的关键。 "三者取中"的规则 第 5 章 快速排序 | 25 "三者取中"规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为 基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的 Partition 算法 完全相同。 取位于 low 和 high 之间的随机数k(low≤k≤high)，用 R[k] 作为基准 选取基准最好的方法是用一个随机函数产生一个取位于 low 和 high 之间的随机数 k(low≤k≤high)，用 R[k] 作 为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排 序。 注意： 随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对 初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数 据随机分布的算法。 1. 平均时间复杂度 尽管快速排序的最坏时间为 O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快 速排序亦因此而得名。它的平均时间复杂度为 O(nlgn)。 1. 空间复杂度 快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为 O(lgn)，故递归后需栈 空间为 O(lgn)。最坏情况下，递归树的高度为 O(n)，所需的栈空间为 O(n)。 1. 稳定性 快速排序是非稳定的，例如[2，2，1]。 第 5 章 快速排序 | 26 66 直接选择排序直接选择排序 选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的 子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。 本节介绍第一种选择排序：直接选择排序。 直接选择排序的基本思想直接选择排序的基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： • 初始状态：无序区为 R[1..n]，有序区为空。 • 第 1 趟排序：在无序区 R[1..n]中选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R[1]交换，使 R[1..i]和 R[2..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。 …… • 第 i 趟排序：第i趟排序开始时，当前有序区和无序区分别为 R[1..i-1]和 R[i..n][1≤i≤n-1]。该趟排序从当前 无序区中选出关键字最小的记录 R[k]，将它与无序区的第 i 个记录 R[i]交换，使 R[1..i]和 R[i+1..n]分别变为 记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。 这样，n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。 直接选择排序的过程直接选择排序的过程 直接选择排序的过程【参见动画演示】 (http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/ zhijiexuanze.htm) 算法描述算法描述 直接选择排序的具体算法如下： void SelectSort(SeqList R) { int i，j，k； for(i=1;i1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。 R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换 Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } //endfor } //HeapSort (4) BuildHeap 和 Heapify 函数的实现 因为构造初始堆必须使用到调整堆的操作，先讨论 Heapify 的实现。 Heapify 函数思想方法 每趟排序开始前 R[l..i]是以 R[1]为根的堆，在 R[1]与 R[i]交换后，新的无序区 R[1..i-1]中只有 R[1]的值发生了变 化，故除 R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是 R[low..high]时，只 须调整以 R[low]为根的树即可。 "筛选法"调整堆 R[low]的左、右子树(若存在)均已是堆，这两棵子树的根 R[2low]和 R[2low+1]分别是各自子树中关键字最大的 结点。若 R[low].key不小于这两个孩子结点的关键字，则 R[low]未违反堆性质，以 R[low]为根的树已是堆，无 须调整；否则必须将 R[low]和它的两个孩子结点中关键字较大者进行交换，即 R[low]与 R[large](R[large].ke y=max(R[2low].key，R[2low+1].key)) 交换。交换后又可能使结点 R[large]违反堆性质，同样由于该结点的两棵 子树(若存在)仍然是堆，故可重复上述的调整过程，对以 R[large]为根的树进行调整。此过程直至当前被调整的 结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较 大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。 BuildHeap 的实现 要将初始文件 R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。 显然只有一个结点的树是堆，而在完全二叉树中，所有序号 -1，…，1的结点作为根的子树都调整为堆即可。 第 7 章 堆排序 | 33 大根堆排序实例大根堆排序实例 对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参 见【动画演示】 (http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/duipaixu.htm) 。 算法分析算法分析 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用 Heapify 实现的。 堆排序的最坏时间复杂度为 O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为 O(1)，它是不稳定的排序方法。 第 7 章 堆排序 | 34 88 归并排序归并排序 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文 件。 两路归并算法两路归并算法 算法基本思路算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到 一个局部的暂存向量 R1(相当于输出堆)中，待合并完成后将 R1 复制回 R[low..high]中。 （1）合并过程 合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 R[i]和 R[j]的 关键字，取关键字较小的记录复制到 R1[p]中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p 加 1。 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中 剩余记录依次复制到 R1 中即可。 （2）动态申请 R1 实现时，R1 是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。 归并算法归并算法 void Merge(SeqList R，int low，int m，int high) {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 //子文件R[low..high] int i=low，j=m+1，p=0； //置初始值 RecType *R1； //R1是局部向量，若p定义为此类型指针速度更快 R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))； if(! R1) //申请空间失败 Error("Insufficient memory available!")； while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]； while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]； while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]； for(p=0，i=low；i<=high；p++，i++) R[i]=R1[p]；//归并完成后将结果复制回R[low..high] } //Merge 第 8 章 归并排序 | 36 归并排序归并排序 归并排序有两种实现方法：自底向上和自顶向下。 自底向上的方法自底向上的方法 （1）自底向上的基本思想 自底向上的基本思想是：第 1 趟归并排序时，将待排序的文件 R[1..n]看作是 n 个长度为 1 的有序子文件，将这些 子文件两两归并，若 n 为偶数，则得到 个有序的子文件两两归并，如此反复，直到最后得到一个长度为 n 的有序文件为止。 上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为"二路归并排序"。类似地有 k(k>2)路归并排序。 （2） 二路归并排序的全过程 【参见动画演示】 (http://student.zjzk.cn/course_ware/data_structure/web/fl ashhtml/guibingpaixu.htm) （3） 一趟归并算法 分析： 在某趟归并中，设各子文件长度为length(最后一个子文件的长度可能小于lengt h)，则归并前R[1..n]中共有 个有序的子文件：R [1..length]，R[length+1..2length]，…， 。 注意： 调用归并操作将相邻的一对子文件进行归并时，必须对子文件的个数可能是奇数、以及最后一个子文件的 长度小于 length 这两种特殊情况进行特殊处理： • 若子文件个数为奇数，则最后一个子文件无须和其它子文件归并(即本趟轮空)； • 若子文件个数为偶数，则要注意最后一对子文件中后一子文件的区间上界是 n。 具体算法如下： 第 8 章 归并排序 | 37 void MergePass(SeqList R，int length) { //对R[1..n]做一趟归并排序 int i； for(i=1;i+2*length-1<=n;i=i+2*length) Merge(R，i，i+length-1，i+2*length-1)； //归并长度为length的两个相邻子文件 if(i+length-1 ... 还剩50页未读 继续阅读 下载pdf到电脑，查找使用更方便 pdf的实际排版效果，会与网站的显示效果略有不同！！ 需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载 下载pdf
