排序与选择解题框架
本节目标
用分治、分区和归并统一理解排序、逆序对统计与第 k 小选择。
排序不是只为输出有序数组服务。它还能建立大小关系、把跨区间比较压缩为一次计数，并让第 k 小元素只保留必要的一侧继续处理。
识别信号
- 题目要求按大小重排，或要利用“左边不大于右边”的有序关系；
- 需要统计满足
i < j且a[i] > a[j]的成对关系； - 只问排名第
k的元素，而不是完整排序结果； - 暴力做法会反复比较两个子区间中的元素。
问题模型
把区间拆成更小的子区间，先解决子问题，再利用子问题已经满足的性质合并答案，这就是分治模型。快速排序让分区后左侧元素不大于右侧元素；归并排序让两个已排序区间线性合并；逆序对在合并时统计跨区间贡献；快速选择只递归包含目标排名的一侧。
通用模板
快速分区选择中点值为 pivot。令 i 从左边界前一位、j 从右边界后一位出发，分别跳过已经在正确侧的元素；当二者尚未交叉时交换。循环结束后，[left, j] 的元素不大于 pivot，[j + 1, right] 的元素不小于 pivot，两个子区间都严格缩小。
归并模板先递归排序左右半区，再用双指针把较小者放入临时数组。左右指针之外的前缀已经有序，因而每次选择都能安全写入；合并结束后只回写当前区间。
本小节的 C++ 代码都是完整竞赛程序：当主数组及其长度贯穿整道题时，将它们作为共享数组放在全局作用域；归并类模板还全局复用辅助数组 tmp。递归函数因此只接收区间边界、目标排名等随子问题变化的状态。Python 保持语言中更自然的显式传参，不使用 global 模拟同一形式。
模板变体
逆序对复用归并：若 nums[j] < nums[i]，右侧当前值也小于左半区从 i 到 mid 的全部未合并元素，计数 cnt 一次增加 mid - i + 1。
快速选择复用快速分区。设分界位置为 pos、左段长度为 leftLen：k <= leftLen 时只进入左段；否则进入右段并把排名改为 k - leftLen。每轮都丢弃另一侧，所以不必完成整个排序。
母题序列
按必学顺序练习：
常见误区
- 分区指针不从区间外侧开始，或相等值不推进，都会让重复值卡住。
- 递归区间写成包含分界点的原区间，无法保证规模缩小。
- 合并时用
<而非<=选择左值，会破坏稳定性；统计逆序对时把相等值也算进去则偏大。 - 快速选择把
k当作零基下标，或进入右区间后忘记扣掉左段长度。
迁移方向
分区可迁移到三路划分、荷兰国旗和第 k 大问题；归并可迁移到区间贡献、二维偏序与离线计数。遇到“答案是否可行”的单调关系时，排序后的边界又会自然连接到二分答案。