C++算法练习之十大排序（二） 堆排序 归并排序

接下来继续讲解十大排序中的堆排序和归并排序堆排序可以参考这篇博文https://blog.csdn.net/weixin_51609435/article/details/122982075堆排序的核心是利用大顶堆根节点最大的完全二叉树来辅助排序。第一步建初始堆 (Build Max Heap)目标把一个无序数组变成一个大顶堆。做法从最后一个非叶子节点下标为n/2−1n/2 - 1n/2−1开始由下至上、由右至左依次调用heapify下沉调整。结果数组的第 0 个元素nums[0]一定是整个数组的最大值。第二步交换与缩容 (Swap Shrink)目标把确定的最大值“踢”到数组末尾。做法将堆顶元素nums[0]与当前堆的最后一个元素交换。结果最大值已经在数组末尾“就座”堆的有效规模减 1。第三步重新调整 (Re-heapify)目标恢复因交换被破坏的堆结构。做法对新的堆顶元素nums[0]执行heapify让它下沉到合适的位置。这一步实际上就是从元素0到元素n-1重新恢复成大顶堆然后继续交换最大的根节点元素和n-1的元素因为此时n已经是上一轮排出来最大的数了循环重复第二步和第三步直到堆的大小减小到 1。什么叫heapify下沉调整假设我们要对节点AAA进行下沉调整比较看节点AAA的两个孩子左孩子LLL和右孩子RRR。选强在LLL和RRR中挑出一个值最大的那一个假设是LLL。判断如果孩子LLL比父亲AAA还要大交换AAA和LLL的位置。如果父亲AAA已经比两个孩子都大了停止下沉结束。递归/循环交换后AAA到了新的位置但它可能还是比现在的孩子小所以要继续执行第 1 步直到它沉到底部或者满足堆性质。例子假设原始数组为[4, 10, 3, 5, 1]4 (下标0) / \ 10 3 (下标1, 2) / \ 5 1 (下标3, 4)第一步建初始堆 (Build Max Heap)我们要把这棵树调整为“大顶堆”。方法是从最后一个非叶子节点下标 1 5/2-1数值10开始往回走。检查节点10进行下沉调整发现已经比子节点都大因此不用调整检查节点4找到子节点较大的1010和4交换10 (换上来了) / \ 4 3 (4掉到了这里) / \ 5 1此时4还要继续下沉和5进行交换10 / \ 5 3 (5换上来了) / \ 4 1 (4最终沉到了这里)第二步排序此时大顶堆已经建成我们交换堆顶的10和末尾的11 (待下沉) / \ 5 3 / 4 [10]第三步重新调整此时原先的大顶堆改变的只有根节点我们对这个根节点进行下沉重新构建1 5 3 4这四个元素的大顶堆就是1和5交换然后1和4再交换得到新的大顶堆5 / \ 4 3 / 1 [10]再执行排序交换5和1得到1 (待下沉) / \ 4 3 [5] [10]然后就是重复操作直到堆的大小减小到 1排序完成代码class Solution { public: // 堆化函数调整以 i 为根的子树使其符合大顶堆性质 // n 为当前堆的有效范围大小 void heapify(vectorint nums, int n, int i) { int largest i; // 假设当前父节点最大 int left 2 * i 1; // 左孩子索引 int right 2 * i 2; // 右孩子索引 // 如果左孩子比父节点大 if (left n nums[left] nums[largest]) { largest left; } // 如果右孩子比当前最大的还大 if (right n nums[right] nums[largest]) { largest right; } // 如果最大值不是父节点说明需要交换并递归调整 if (largest ! i) { swap(nums[i], nums[largest]); // 递归调整受影响的子树 heapify(nums, n, largest); } } // 堆排序主函数 void HeapSort(vectorint nums) { int n nums.size(); if (n 1) return; // 1. 建立初始大顶堆 // 从最后一个非叶子节点开始自底向上调整 // 索引为 n/2 - 1 是最后一个拥有子节点的节点 for (int i n / 2 - 1; i 0; i--) { heapify(nums, n, i); } // 2. 交换与收缩 for (int i n - 1; i 0; i--) { //不需要等于0是因为等于0就只剩根节点一个了也就不需要排序了 // 将当前堆顶最大值移到数组末尾 swap(nums[0], nums[i]); // 重新调整堆顶此时堆的大小减小即 i heapify(nums, i, 0); //第三个参数从0开始是因为是在初始大顶堆的基础上换了第0个元素和最后一个元素此时只需要对0元素进行下沉后续最大的值自然会到第0个元素 } } };归并排序归并排序的核心是利用分治法Divide and Conquer先不断对半分解再将有序的子序列合并。第一步分解阶段 (Divide)目标把一个无序的大数组不断对半拆分为最小的单元。做法从中间位置mid将数组一分为二递归地对左右两个子数组进行拆分。结果数组被拆分成一个个长度为 1 的子序列由于长度为 1它们自身天然是有序的。第二步合并阶段 (Merge)目标将两个已经排好序的小序列像拉链一样合并成一个更大的有序序列。做法创建一个临时数组使用双指针分别对比两个子序列的元素谁小就把谁放入临时数组。结果得到一个更长且有序的合并后序列。第三步递归回溯 (Recursive Return)目标层层向上最终完成整个大数组的排序。做法随着递归函数的返回逐层调用第二步的“合并”操作。循环/重复不断重复第二步的合并直到所有局部有序的子序列合并成一个完整的、与原数组等大的有序数组。例子假设原始数组为[4, 10, 3, 5, 1]第一步自顶向下的分解 (Divide)我们要把这段数组不断对半“劈开”直到不能再劈为止。初始[4, 10, 3, 5, 1]第一次劈开得到左半边和右半边Plaintext[4, 10] [3, 5, 1]继续往下劈开Plaintext[4] [10] [3] [5, 1]右边还能劈最终全部变成单元素Plaintext[4] [10] [3] [5] [1]此时分解阶段结束。每个框里只有 1 个数它们自己对自己是“有序”的。第二步自底向上的合并 (Merge)现在开始两两合并调用 merge 操作合并[4]和[10]因为 4 10得到Plaintext[4, 10] [3] [5] [1]合并[5]和[1]因为 1 5得到Plaintext[4, 10] [3] [1, 5]合并[3]和[1, 5]先取 1再取 3最后剩下 5得到Plaintext[4, 10] [1, 3, 5]最后一步合并[4, 10]和[1, 3, 5]1 比 4 小取 13 比 4 小取 34 比 5 小取 45 比 10 小取 5剩下 10直接接上 得到最终有序数组class Solution { public: // 合并函数假设 [left, mid] 和 [mid1, right] 都已有序将它们合并 void merge(vectorint nums, int left, int mid, int right) { // 创建临时数组大小为当前合并区间的长度 vectorint temp(right - left 1); int i left; // 指向左半区间的起始 int j mid 1; // 指向右半区间的起始 int k 0; // 临时数组的游标 // 1. 比较左右区间的最前面元素谁小就把谁放入 temp while (i mid j right) { if (nums[i] nums[j]) { // 保证了排序的稳定性 temp[k] nums[i]; } else { temp[k] nums[j]; } } // 2. 扫尾如果左边没放完全部接到 temp 后面 while (i mid) { temp[k] nums[i]; } // 3. 扫尾如果右边没放完全部接到 temp 后面 while (j right) { temp[k] nums[j]; } // 4. 将排序好的临时数组覆盖回原数组 for (int p 0; p temp.size(); p) { nums[left p] temp[p]; } } // 归并排序主函数负责不断分解然后调用 merge合并 void mergeSort(vectorint nums, int left, int right) { // 如果区间内只有 1 个元素或者没有元素直接返回分解的终点 if (left right) return; // 找到中间位置防止溢出的写法 int mid left (right - left) / 2; // 递归分解左半部分 mergeSort(nums, left, mid); // 递归分解右半部分 mergeSort(nums, mid 1, right); // 将已经排好序的左半部分和右半部分进行合并 merge(nums, left, mid, right); } };