Vince Jiang

CSCI3160 / 辅导 · 本站更新

CSCI3160 T03 · Part 1/2 归并数逆序对

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T03，第 1 部分 / 共 2 部分 · 原件 T03-分治-未核-隐藏.pdf（本地课件） p.1–24 定位：让递归同时返回有序数组和逆序数，在一次归并中数完全部跨半贡献。 前后：下一份 Part 2

本讲按原件提纲分为：

p.1–3：逆序对沿原位置分区【新】

p.1 列两个任务：线性对数时间逆序计数与支配计数。p.2 逆序对要求i<j且A[i]>A[j]；p.3 例A=(10,3,9,8,2,5,4,1,7,6)，按原下标分两半。排序只用于子问题返回后的合并，不能一开始把整数组排序而丢失位置关系。

p.4–6：旧方法多花一个对数

p.4 剩余任务是跨左右两半的逆序。p.5 每层重新排序并做多次二分，合并O(nlog n)。p.6 因此递推2T(n/2)+O(nlog n)，各层成本分别nlog n、n(log n−1)、…，合计O(nlog²n)。

p.7–9：加强返回契约

p.7 “ask a harder question”

p.8 每个递归不仅返回逆序数，还返回升序数组；p.9 左子问题返回(2,3,8,9,10)及8，右返回(1,4,5,6,7)及4。左内部计数可逐项算4+1+2+1=8，右为2+1+0+1=4。

p.10–12：一次归并完成两项工作

p.10 已排序两半支持线性合并；p.11 要数所有左元素a大于右元素b的跨对；p.12 同步归并并累计。每输出一个左元素，加此前已经输出的右元素个数，因为这些右元素全比它小；输出右元素时本版本先不加数。

完整的返回契约可以实现为：

CountSort(A):
  若长度 ≤ 1：返回 (0,A的副本)
  按原位置分为左右两半
  (x,L)=CountSort(左半)；(y,R)=CountSort(右半)
  i=j=cross=0；B=[]
  当 i<|L| 或 j<|R|：
    若 i<|L| 且 (j=|R| 或 L[i]≤R[j])：
      B追加L[i]；cross+=j；i+=1
    否则：B追加R[j]；j+=1
  返回 (x+y+cross,B)

这里 i、j 都从 0 起，短路判断保证不会越界。末尾即使一边耗尽，仍按同一收费规则处理。

p.13–15：第一对何时计入

p.13 空输出、计数0。p.14 先输出右边的1，计数仍0；p.15 输出左边2，此前输出一个右元素，新增(2,1)，总1。图（p.15）：上下两排已排序数组，箭头标下一候选。元素：右指针位置1等于已输出右元素数。看什么：指针下标从0起，但累计值是数量，末尾可以到数组长度。

p.16–18：左元素收费，右元素只移动

p.16 输出左3再加1，总2；p.17 输出右4，p.18 输出右5，累计仍2。这些右元素以后会与尚未输出的较大左元素配对，暂时不加不代表遗漏。

p.19–21：右侧全部输出后

p.19 输出右6，p.20 输出右7，计数仍2，此时右侧已输出5项。p.21 输出左8，加5，总7，新增(8,1),(8,4),(8,5),(8,6),(8,7)。

p.22–24：合并总数与整题总数

p.22 左9再加5，总12；p.23 左10再加5，总17。完整逆序数为左右8+4加跨17=29。p.24 合并线性，递推2T(n/2)+O(n)，每层O(n)、共O(log n)层，总O(nlog n)。每次跨对恰在其两个端点首次被分到两侧的节点计一次，所以无重无漏。

补充：把收费规则写成不变量。 输出前缀始终有序；右指针 j 等于已输出右元素个数；跨计数等于已经输出的左元素与右半所形成的全部逆序对数。输出左值 x 时，已输出右值全小于 x，尚未输出右值都不小于 x，因此恰新增 j 对。这样既不漏未来右值，也不把一对收两次费。

推广到允许重复值时，相等必须先输出左值，才能保证“已输出右值全严格小于 x”。自取左 [2,2]、右 [1,2]：先输出右1，j=1；两次左2各加1，跨数2；最后右2只推进。若相等先右，就会把相等的2误计为逆序。

自测：右半耗尽后，只复制左半剩余元素而不计数可以吗？

不可以。原例剩余左8、9、10，每项仍要加右半长度5，共15；先前只加了2，漏掉它们就会把17误写成2。尾段不是没有逻辑，只是不用再做大小比较。

本讲核心考点

  • 递归同时返回计数和有序数组，使跨半统计线性（p.7–24；C 级）。

附录

本部分所需过程已在正文展开。

来源与证据

  • 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

  • 原件：T03-分治-未核-隐藏.pdf（本地课件），本部分 p.1–24；页码均为 PDF 页号。

  • 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

  • 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

  • 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

  • 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。