LeetCode 912 https://leetcode.cn/problems/sort-an-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 归并排序。将整个数组分成前后两个部分，递归调用归并排序，使得两部分分别有序，之后使用一个临时数组，将两个有序数组合并，最后将结果复制回原数组。 时间复杂度：O(nlogn)。由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要 O(n) 的时间复杂度，根据主定理我们可以得出归并排序的时间复杂度为 O(nlogn)。 空间复杂度：O(n)。我们需要额外 O(n) 空间的 tmp 数组，且归并排序递归调用的层数最深为 logn，所以我们还需要额外的 O(logn) 的栈空间，所需的空间复杂度即为 O(n+logn) = O(n)。 ...
LeetCode 912 https://leetcode.cn/problems/sort-an-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是手撕堆排序，使用最大堆。在本题中因为不会有新的元素插入，只需要实现自顶向下修复堆的操作即可。建堆时从最后一个非叶子结点开始，依次调用 repair 函数。然后每次将堆顶元素与堆的最后一个元素交换，堆的大小减一，修复堆。最后数组即为升序排列。反之，如果降序排列使用最小堆。 时间复杂度：O(nlogn)。初始化建堆的时间复杂度为 O(n)，建完堆以后需要进行 n−1 次调整，一次调整的时间复杂度为 O(logn)，那么 n−1 次调整即需要 O(nlogn) 的时间复杂度。因此，总时间复杂度为 O(n+nlogn)=O(nlogn)。 空间复杂度：O(1)。只需要常数的空间存放若干变量。 ...
LeetCode 56 https://leetcode.cn/problems/merge-intervals/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 首先将数组按照左端点进行排序，然后如果当前区间左端点 <= 答案中最后一个合并区间的右端点，更新答案区间右端点为两者较大值；反之将当前区间加入答案。 时间复杂度：O(nlogn)，其中 n 是 intervals 的长度。瓶颈在排序上。 空间复杂度：O(1)。排序的栈开销和返回值不计入。 ...
本文介绍堆排序的实现方法，题目选择洛谷的 P1177。 本题使用小根堆，先把所有的元素都 push 进去，然后每次取出堆顶输出并弹掉堆顶，直到堆空为止。 堆的实现需要两个修复操作。当把结点插入堆时，首先将结点放到尾部，这时可能不满足小根堆的性质，因此需要自底向上修复堆。修复的边界条件是 x 已经是根结点或者 x 大于他的父结点。 当删除堆顶元素时，将堆顶元素和尾部元素交换，删除尾部元素，这时也可能不满足小根堆的性质，因此需要自顶向下修复堆。修复的边界条件是 x 已经是叶子结点或者 x 小于他的儿子中的最小值。 堆排序整体的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。 ...
本文介绍快速排序算法以及基于快速排序的选择方法的实现。 ...