归并排序

LCR 170 https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 求数组中的逆序对只需要在归并排序的代码的基础上添加一行代码即可。当 nums[i] > nums[j] 时，说明从 i 到 mid 这 (mid - i + 1) 个元素都与 j 构成了逆序对，更新全局变量 cnt。 if (nums[i] <= nums[j]) { tmp[k] = nums[i]; i++; } else { cnt += (mid - i + 1); tmp[k] = nums[j]; j++; } 时间复杂度：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/ 归并排序。将整个数组分成前后两个部分，递归调用归并排序，使得两部分分别有序，之后使用一个临时数组，将两个有序数组合并，最后将结果复制回原数组。 时间复杂度：O(nlogn)。由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要 O(n) 的时间复杂度，根据主定理我们可以得出归并排序的时间复杂度为 O(nlogn)。 空间复杂度：O(n)。我们需要额外 O(n) 空间的 tmp 数组，且归并排序递归调用的层数最深为 logn，所以我们还需要额外的 O(logn) 的栈空间，所需的空间复杂度即为 O(n+logn) = O(n)。 ...

LeetCode 148 https://leetcode.cn/problems/sort-list/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题使用归并排序。 找到链表的中间结点 head 2 的前一个节点，并断开 head2 与其前一个节点的连接。这样我们就把原链表均分成了两段更短的链表。 分治，递归调用 sortList，分别排序 head（只有前一半）和 head2。 排序后，我们得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点。 时间复杂度：O(nlogn)，其中 n 是链表长度。递归式 T(n)=2T(n/2)+O(n)，由主定理可得时间复杂度为 O(nlogn)。 空间复杂度：O(logn)。递归需要 O(logn) 的栈开销。 ...