Loading... ## 定义 排序 (Sort) 就是**重新排列**表中的元素，使表中的元素满足**按关键字有序**的过程。 **评价指标**：时间复杂度，空间复杂度。 算法的**稳定性**：设待排序表中有两个元素 $R_i$ 和 $R_j$ ，其对应的关键字相同 ($key_i = key_j$) ，且在排序前满足 $R_i$ 在 $R_j$ 的前面。若使用某一排序算法排序后，$R_i$ 仍然在 $R_j$ 前面，则称这个排序算法是**稳定**的。反之则称该排序算法**不稳定**。 ### 分类 - 内部排序：数据都在内存中。 一般只关注算法的时空复杂度。 - 外部排序：数据过多无法全部存入内存时，需要使用外部排序。 除了时空复杂度，还需要考虑如何减少磁盘 IO 。 ## 插入排序 每次将一个待排序的元素按照其关键字大小插入到前面已排好序的子序列中，直至全部元素插入完成。 ```c++ void InsertSort(int nums[], int n) { for (int i = 1; i < n; i++) { if (nums[i] < nums[i - 1]) { int tmp = nums[i]; for (int j = i - 1; j >= 0 && nums[j] > tmp; j--) nums[j + 1] = nums[j]; nums[j + 1] = tmp; } } } ``` - 时间复杂度：$O(n^2)$ 。最好情况 $O(n)$ ，最坏情况 $O(n^2)$ ，平均 $O(n^2)$ 。 - 空间复杂度：$O(1)$ 。 - 算法稳定性：稳定。 ### 二分插入排序 先用二分查找的思想找出应该插入的位置，然后再移动元素。 > 注意算法的稳定性。 ```c++ void InsertSort(int nums[], int n) { for (int i = 2; i <= n; i++) { nums[0] = nums[i]; int low = 1, high = i - 1; while (low <= high) { int mid = (low + high) / 2; if (nums[mid] > nums[0]) high = mid = 1; else low = mid + 1; } for (int j = i - 1; j >= high + 1; j--) nums[j + 1] = nums[j]; nums[high + 1] = nums[0]; } } ``` ## 希尔排序 先将待排序的表分割成若干形如 $L[i, i + d, i + 2d, ..., i + kd]$ 的特殊子表，对每个子表进行插入排序。接着缩小增量 $d$ ，重复上述过程，直至 $d = 1$ 。 ![image-20240709005528726.png][1] ```c++ void ShellSort(int nums[], int n) { for (int d = n / 2; d >= 1; d = d / 2) { for (int i = d + 1; i <= n; i++) { if (nums[i] < nums[i - d]) { nums[0] = nums[i]; // 暂存在 nums[0] for (int j = i - d; j > 0 && nums[0] < nums[j]; j--) nums[j + d] = nums[j]; nums[j + d] = nums[0]; } } } } ``` - 时间复杂度：最坏情况下 $O(n^2)$ ，当 $n$ 在某个范围内时，可以达到 $O(n^{1.3})$ 。目前无法使用数学手段证明确切的时间复杂度。 - 空间复杂度：$O(1)$ 。 - 算法稳定性：不稳定。 > 希尔排序仅能使用顺序表实现，不可用链表。 一般考点是给出增量序列，分析每一趟排序后的状态。 ## 冒泡排序 从后往前 (或从前往后) 两两比较相邻元素的值，若为逆序则交换他们，直到序列比较完。按照上述过程对所有元素操作一遍，即得到一个有序的序列。 若某一趟排序没有进行任何交换，也可以判断排序结束。 > 冒泡排序可以使用链表实现 ```c++ void BubbleSort(int nums[], int n) { for (int i = 0; i < n - 1; i++) { bool isSwap = false; for (int j = n - 1; j > i; j--) { if (nums[j - 1] > nums[j]) { std::swap(nums[j - 1], nums[j]); isSwap = true; } } if (!isSwap) return; } } ``` - 时间复杂度：$O(n^2)$ 。最好时间复杂度为 $O(n)$ ，最坏时间复杂度为 $O(n^2)$ ，平均 $O(n^2)$ 。 - 空间复杂度：$O(1)$ 。 - 算法稳定性：稳定。 ## 快速排序 在待排序表 $L$ 中任取一个元素 `pivot` 作为基准，通过一趟排序将待排序的表划分为独立的两部分 $L[1, k - 1]$ 和 $L[k + 1, n]$ ，使得 $L[1, k - 1]$ 内的所有元素小于 `pivot` ，$L[k + 1, n]$ 中的所有元素大于等于 `pivot` ，则 `pivot` 放在了其最终位置 $L(k)$ 上。这个过程称为一次 "划分" 。递归地对两个子表重复上述过程，直到每个部分内只有一个元素或为空为止。 ```c++ void QuickSort(int nums[], int begin, int end) { if (begin >= end) return; int pivot = nums[begin]; int left = begin, right = end; while (left < right) { while (left < right && nums[right] >= pivot) right--; while (left < right && nums[left] <= pivot) left++; std::swap(nums[left], nums[right]); } std::swap(nums[begin], nums[left]); QuickSort(nums, begin, left - 1); QuickSort(nums, left + 1, end); } QuickSort(nums, 0, n - 1); ``` - 时间复杂度：$O(nlogn)$ 。每次划分的时间复杂度不超过 $O(n)$ ，总共需要划分 $O(logn)$ 次，因此总时间复杂度为 $O(nlogn)$ 。 - 空间复杂度：$O(logn)$ 。递归需要 $O(logn)$ 的栈开销。 - 算法稳定性：不稳定。 ### 优化 若初始序列有序，则上述快排代码的性能会很差，因为划分的区间不均匀。若每次选中的 `pivot` 能将待排序序列划分为均匀的两个部分，则能减少递归深度，提高算法效率。 因此优化思路就是尽量选择可以把数据中分的 `pivot` 元素。比如从头中尾三个位置中取中间值作为 `pivot` ，或者随机选择一个元素作为 `pivot` 。 ### 补充 408 原题中说，对所有尚未确定最终位置的所有元素进行一遍处理称为**一趟排序**。因此一次划分不等于一趟排序。一次划分仅可以确定一个元素的最终位置，而一趟排序可能可以确定多个元素的最终位置。 ## 选择排序 每次从未排序的序列中选择一个最小 (或最大) 的元素加入有序子序列中。 ```c++ void SelectSort(int nums[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[minIndex]) minIndex = j; } std::swap(nums[i], nums[minIndex]); } } ``` - 时间复杂度：$O(n^2)$ 。选择排序的时间复杂度不会根据表中元素分布而改变。 - 空间复杂度：$O(1)$ 。 - 算法稳定性：不稳定。 ## 堆排序 堆排序也是一种选择排序，原理和选择排序一样，只是使用了堆的特性来实现。 ### 堆 #### 特性 使用顺序表存储堆的时候，对于第 $i$ 个元素来说： - $i$ 的左孩子是下标为 $2i$ 的元素； - $i$ 的右孩子是下标为 $2i + 1$ 的元素； - $i$ 的父节点是下标为 $\lfloor i / 2 \rfloor$ 的元素； #### 建堆 > 下面以大顶堆为例，小顶堆也是差不多的做法。 把所有非终端节点都检查一遍，查看是否满足大顶堆的要求。如果不满足则进行调整。 ```c++ void BuildMaxHeap(int nums[], int len) { for (int i = len / 2; i > 0; i--) HeadAdjust(nums, i, len); } void HeadAdjust(int nums[], int k, int len) { nums[0] = nums[k]; // 暂存子树的根节点 for (int i = 2 * k; i <= len; i *= 2) { if (i < len && nums[i] < nums[i + 1]) i++; if (nums[0] < nums[i]) { nums[k] = nums[i]; k = i; } } nums[k] = nums[0]; } ``` #### 插入 将新元素放到表尾 (堆底) ，然后根据大顶堆的要求，将新插入的元素不断 "上浮" ，直到无法上升为止。 #### 删除 被删除元素用表尾 (堆底) 元素替代，然后将替换上来的元素根据大顶堆的要求不断下坠，直到无法下坠为止。 ### 排序 将堆顶元素加入有序子序列，然后删除堆顶元素，并将堆重新调整为大顶堆。 ```c++ void HeapSort(int nums[], int len) { BuildMaxHeap(nums, len); for (int i = len; i > 1; i--) { // 交换堆顶和堆底元素 std::swap(nums[i], nums[1]); HeadAdjust(nums, 1, i - 1); } } ``` - 时间复杂度：建堆 $O(n)$ ，排序 $O(nlogn)$ 。 - 空间复杂度：$O(1)$ 。 - 算法稳定性：不稳定。 ## 归并排序 **归并**：将两个或多个已经有序的序列合并成一个。$n$ 个序列合并成一个称为 $n$ 路归并。 ```c++ // 取值范围左闭右开，下同。 void Merge (int nums[], int left, int mid, int right) { int *tmp = new int[right - left]; int lSentinel = left, rSentinel = mid, tIndex = 0; while (lSentinel < mid && rSentinel < right) tmp[tIndex++] = nums[lSentinel] < nums[rSentinel] ? nums[lSentinel++] : nums[rSentinel++]; // 处理剩余的数 while (lSentinel < mid) tmp[tIndex++] = nums[lSentinel++]; while (rSentinel < right) tmp[tIndex++] = nums[rSentinel++]; for (int i = 0; i < right - left; i++) nums[left + i] = tmp[i]; delete [] tmp; } void MergeSort(int nums[], int begin, int end) { if (begin >= end - 1) return; int mid = (begin + end - 1) / 2 + 1; MergeSort(nums, begin, mid); MergeSort(nums, mid, end); Merge(nums, begin, mid, end); } ``` ### 归并树 二路归并的归并树形态上就是一棵倒立的二叉树： ![image-20240711012425428.png][2] 因此归并的趟数不会超过树高 $\lceil log_2n \rceil$ 。每趟归并的时间复杂度为 $O(n)$ ，因此归并排序的时间复杂度为 $O(nlogn)$ 。 空间复杂度为 $O(n)$ ，主要来自于辅助数组。 算法稳定性：稳定。 ### 补充 $k$ 路平衡归并： 1. 最多只能有 $k$ 个段归并为一个； 2. 每一趟归并中，若有 $m$ 个归并段参与归并，则经过这一趟处理得到 $\lceil m / k \rceil$ 个新的归并段。 ## 基数排序 基数排序**不是基于比较**的排序算法。 假设长度为 $n$ 的线性表中每个节点 $a_j$ 的关键字由 $d$ 元组 $(k_j^{d-1}, k_j^{d-2}, k_j^{d-3}, ..., k_j^{1}, k_j^{0})$ 组成，其中 $0 \leq k_j^i \leq r - 1 \ (0 \leq j < n, 0 \leq i \leq d - 1)$ ，$r$ 称为基数。 > 这里以求递减序列为例 1. 初始化：设置 $r$ 个空队列 $Q_{r - 1}, Q_{r - 1}, ..., Q_{0}$ ； 2. 将各个关键字位按照权重递增的次序 (比如十进制数的个位，十位，百位) ，对 $d$ 个关键字为分别做 "分配" 和 "收集" ： - 分配：顺序扫描各个元素，若当前处理的关键字位为 $x$ ，则将元素插入 $Q_x$ 队尾。 - 收集：将 $Q_{r - 1}, Q_{r - 1}, ..., Q_{0}$ 各个队列中的节点依次出队并连接。 ![image-20240712003556919.png][3] - 时间复杂度：$O(d \times (n + r))$ 。关键字可以拆分成 $d$ 个部分，每个部分可能取得 $r$ 个值。一趟分配需要 $O(n)$ 的时间，一趟收集需要 $O(r)$ 的时间，总共 $d$ 趟分配和收集。 - 空间复杂度：$O(r)$ 。 - 算法稳定性：稳定。 ### 应用场景 基数排序适合的问题： 1. 数据元素的关键字可以方便地拆分成 $d$ 组，且 $d$ 相对较小。 2. 魅族关键字的取值范围不大，即 $r$ 较小。 3. 数据元素的个数 $n$ 较大。 ## 外部排序 使用**归并排序**，最少只需要在内存中分配三块缓冲区，即可对任意一个大文件进行排序。 假设需要对 16 个磁盘块中的数据进行排序，则主要流程如下： ![image-20240712005315639.png][4] 此时读写磁盘的次数为 $32 + 32 \times 3 = 128$ 次。 ### 优化 > 外部排序的时间开销 = 读写磁盘的时间 + 内部排序需要的时间 + 内部归并需要的时间。 - 对 $r$ 个初始归并段，做 $k$ 路归并，则归并树可以用 $k$ 叉树来表示。 - 若树高为 $h$ ，则归并趟数 = $h - 1$ = $\lceil log_kr \rceil$ 。 第一种方法是增大 $k$ ，可以使用多路归并的方法来达成。因为多路归并可以一次读入更多的块，从而减少读写磁盘的次数。 **负面影响：** 1. $k$ 路归并时，需要开辟 $k$ 个输入缓冲区，会导致内存开销增加。 2. 每挑选一个关键字需要对比 $k - 1$ 次关键字，内部排序所需要的时间增加。(可以通过后面的败者树来解决) 第二种方法是减少 $r$ ，增加初始归并段的长度来减少磁盘 IO 的次数。(置换-选择排序) ### 败者树 败者树可以视为一棵多了个头的完全二叉树。$k$ 个叶节点分别是当前参加比较的元素，非叶子节点用来记忆左右子树中的 "失败者" 。 ![image-20240715005653612.png][5] 基于已经构建好的败者树，每次更新一个元素后选出新的胜者只需要 $\lceil log_2n \rceil$ 次比较。 败者树只需要存储各个分支节点即可。 ![image-20240715010550965.png][6] ### 置换-选择排序 设初始待排序文件为 $FI$ ，初始归并段输出文件为 $FO$ ，内存工作区为 $WA$ 。$FO$ 和 $WA$ 的初始状态为空，且 $WA$ 能容纳 $w$ 个记录。那么置换-选择排序步骤如下： 1. 从 $FI$ 输入 $w$ 个记录到工作区 $WA$ 。 2. 从 $WA$ 中选出其中关键字最小的记录，记为 $minmax$ 。 3. 将 $minmax$ 记录输出到 $FO$ 。 4. 若 $FI$ 不空，则从 $FI$ 中取一个记录输入到 $WA$ 中。 5. 从 $WA$ 中所有关键字比 $minmax$ 的关键字大的记录中选出关键字最小的一个，作为新的 $minmax$ 记录。 6. 重复过程 3 ~ 5 ，直到 $WA$ 中无法更新 $minmax$ 为止，由此得到第一个归并段。向 $FO$ 输出一个归并段的结束标志。 7. 重复过程 2 ~ 6，直到 $WA$ 为空。 ### 最佳归并树 使用归并排序的外部排序，其 IO 次数为归并树的带权路径长度的两倍。想最小化 IO 次数，只需要让其归并树的带权路径长度最小即可。因此可以用霍夫曼树来找出最佳归并树。 对于 $k$ 路归并，也是和二叉树构造霍夫曼树一样的思路。但此时会出现一个问题：初始归并段的数量无法构成严格的 $k$ 叉归并树。此时需要补充几个长度为 0 的 "虚段" ，再进行 $k$ 叉霍夫曼树的构造。 ![image-20240715014153175.png][7] [1]: https://blog.domineto.top/usr/uploads/2024/07/1360158755.png [2]: https://blog.domineto.top/usr/uploads/2024/07/4148813829.png [3]: https://blog.domineto.top/usr/uploads/2024/07/3172336059.png [4]: https://blog.domineto.top/usr/uploads/2024/07/1944741378.png [5]: https://blog.domineto.top/usr/uploads/2024/07/2260537463.png [6]: https://blog.domineto.top/usr/uploads/2024/07/2693720730.png [7]: https://blog.domineto.top/usr/uploads/2024/07/1717697898.png 最后修改：2024 年 11 月 20 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏