一、堆排序Heap Sort算法堆排序基于完全二叉树 大顶堆实现属于不稳定排序平均 / 最好 / 最坏时间复杂度均为O(n log n)空间复杂度O(1)原地排序。 整体流程分为两大阶段构建大顶堆循环交换堆顶并调整堆。public class HeapSort { public static void main(String[] args) { int[] arr {3, 1, 4, 2, 7, 5, 9, 6, 8}; heapSort(arr); System.out.print(堆排序结果); for (int num : arr) { System.out.print(num ); } } /** * 堆排序入口方法 * param arr 待排序数组 */ public static void heapSort(int[] arr) { int len arr.length; // 第一步构建初始大顶堆从最后一个非叶子节点向前调整 for (int i len / 2 - 1; i 0; i--) { heapify(arr, i, len); } // 第二步循环交换堆顶与堆底缩小堆范围并重新调整堆 for (int i len - 1; i 0; i--) { // 交换堆顶最大值和当前堆末尾元素 int temp arr[0]; arr[0] arr[i]; arr[i] temp; // 仅对根节点调整堆有效长度缩小为i heapify(arr, 0, i); } } /** * 堆维护方法以i为根调整子树满足大顶堆规则 * param arr 原数组 * param root 当前根节点下标 * param heapLen 当前堆有效长度 */ public static void heapify(int[] arr, int root, int heapLen) { while (true) { // 假设当前根是最大值下标 int maxIndex root; // 左孩子下标 int left 2 * root 1; // 右孩子下标 int right 2 * root 2; // 左孩子存在且值更大更新最大值下标 if (left heapLen arr[left] arr[maxIndex]) { maxIndex left; } // 右孩子存在且值更大更新最大值下标 if (right heapLen arr[right] arr[maxIndex]) { maxIndex right; } // 根已经是最大值无需调整退出循环 if (maxIndex root) { break; } // 交换根与最大值节点 int temp arr[root]; arr[root] arr[maxIndex]; arr[maxIndex] temp; // 向下迭代继续调整交换后的子树 root maxIndex; } } }1. 核心思路与数组下标映射1大顶堆规则完全二叉树结构任意父节点数值 ≥ 左右子节点数值堆顶是当前区间最大值。 堆排序整体两步对整个数组构建初始大顶堆将堆顶最大值与堆末尾元素交换缩小有效堆长度对剩余元素重新调整大顶堆循环直到全部有序。2数组下标映射无需新建二叉树数组直接存储完全二叉树通过下标换算父子节点父节点下标i左孩子下标2 * i 1右孩子下标2 * i 23堆维护 heapify 统一逻辑堆调整方法heapify作用保证以i为根的子树满足大顶堆规则。 两种场景共用同一个维护方法初始建堆从最后一个非叶子节点倒序向前逐个调用 heapify交换堆顶后调整仅需对根节点下标 0 调用一次 heapify。4heapify 调整逻辑传入数组、当前父节点下标、堆有效长度循环查找父、左、右三者最大值下标若最大值不是父节点交换父子元素把最大值下标作为新父节点继续向下循环调整直到满足大顶堆或超出边界。2. 时间复杂度推导单次heapify向下调整遍历层数为树高度复杂度O(log n)初始建堆遍历所有非叶子节点总代价O(n)交换 调整阶段共 n 次循环每次调用一次heapify总代价O(n log n)整体总时间复杂度O(n log n)无论原始数组有序 / 逆序 / 乱序均稳定。空间复杂度原地排序仅常数临时变量O(1)。二、归并排序Merge Sort算法归并排序采用分治思想稳定排序时间复杂度稳定O(n log n)缺点是需要额外临时数组空间复杂度O(n)。/** * 合并左右两个有序区间 * param arr 原数组 * param left 左区间起始下标 * param mid 左右区间分割点 * param right 右区间结束下标 */ public static void merge(int[] arr, int left, int mid, int right) { // 右区间起始指针 int s2 mid 1; // 创建临时数组存储本次合并后的有序数据长度当前区间元素总数 int[] temp new int[right - left 1]; // temp数组写入下标 int index 0; // 1. 双指针循环同时遍历左右有序区间取较小值存入temp while (s1 mid s2 right) { if (arr[s1] arr[s2]) { temp[index] arr[s1]; s1; index; } else { temp[index] arr[s2]; s2; index; } } // 2. 左区间剩余元素全部拷贝进temp while (s1 mid) { temp[index] arr[s1]; s1; index; } // 3. 右区间剩余元素全部拷贝进temp while (s2 right) { temp[index] arr[s2]; s2; index; } // 4. 将临时有序数组写回原数组对应区间关键步骤防止数据丢失 for (int j 0; j temp.length; j) { arr[left j] temp[j]; } }1. 分治核心逻辑1递归拆分策略递归将数组以中点切分为左、右两个区间持续拆分直到区间只剩单个元素天然有序再逐层向上合并有序区间。递归出口left right区间无元素或仅一个元素无需处理仅传递左右边界下标划分区间不新建子数组节约内存。2双指针合并有序序列有两个有序子区间时借助临时数组完成合并双指针 S1、S2 分别指向左右有序区间起始对比两个指针指向元素将更小的值存入临时数组对应指针后移某一侧区间遍历完毕后把另一侧剩余元素全部拷贝进临时数组合并完成后将临时数组整体写回原数组[left, right]对应位置防止原数据覆盖丢失。2. 递归内存执行流程递归拆分时每层方法入栈保存 left、right、mid 参数递归到底触发出口后逐层出栈执行合并逻辑每次合并会创建临时数组存放有序结果属于堆内存合并完成将临时数组数据覆盖写回原数组上层递归继续合并更大区间。3. 复杂度总结时间复杂度拆分层数log n每层合并总遍历元素 n稳定O(n log n)空间复杂度需要辅助临时数组O(n)特性稳定排序适合外排序海量磁盘数据排序。三、堆排序 vs 归并排序维度堆排序归并排序时间复杂度稳定 O (n log n)稳定 O (n log n)空间复杂度O (1) 原地排序O (n) 需要临时数组排序稳定性不稳定稳定适用场景内存内大数据排序、空间受限场景外排序、要求稳定排序场景实现难点完全二叉树下标换算、堆调整递归分治、双指针合并、数组回写
)
