排序

LeetCode 347 https://leetcode.cn/problems/top-k-frequent-elements/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 桶排序。 第一步 答案与元素的出现次数有关，我们首先用一个哈希表 cnt 统计每个元素的出现次数。哈希表的 key 是元素值，value 是 key 在数组中的出现次数。 第二步 设出现次数最大值为 maxCnt，由于 maxCnt≤n，我们可以用桶排序，把出现次数相同的元素，放到同一个桶中。 创建一个大小为 maxCnt+1 的列表 buckets，其中 buckets[c] 存储出现次数为 c 的元素。（每个 buckets[c] 都是一个列表） 遍历 cnt，把出现次数为 c 的元素 x 添加到 buckets[c] 中。 第三步 倒序遍历 buckets，把 buckets[c] 中的元素加到答案中。 一旦答案的长度等于 k，就立刻返回答案。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(n)。 ...

LCR 159 https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 快速选择算法，可以使数组 [0, k] 有序。 时间复杂度：O(n) 空间复杂度：O(logn) ...

LeetCode 75 https://leetcode.cn/problems/sort-colors/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ O(1) 插入元素 不是插入元素，而是修改元素！ 维护 a 中 0 的个数，即改为 0 的位置，记作 p0。维护 a 中 0 和 1 的个数，即改为 1 的位置，记作 p1。 首先将 x 改为 2，如果 x <= 1，nums[p1++] = 1，如果 x == 0，nums[p0++] = 0。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

补充题 1 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 给定一个奇数位升序，偶数位降序的链表，将其重新排序。 将链表拆分成两个链表：奇数节点链表和偶数节点链表。 奇数节点链表：位置 1,3,5,…的节点，原链表奇数位置升序，所以奇数节点链表是升序的。 偶数节点链表：位置 2,4,6,…的节点，原链表偶数位置降序，所以偶数节点链表是降序的。 将偶数节点链表反转，因为降序反转后变成升序。 合并两个升序链表（奇数链表和反转后的偶数链表），合并成新的升序链表。 时间复杂度：O(n)。 空间复杂度：O(1)。 ...

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)。 ...

本文介绍快速排序算法以及基于快速排序的选择方法的实现。 ...