企业官网建设流程全解析

最近点对问题：swift-algorithm-club 中基于分治策略的 O(n log n) 求解实现

【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club

最近点对（Closest Pair）问题是计算几何中的经典问题：给定平面上一组点，找出距离最近的一对点。本指南以 Closest Pair/README.markdown 为核心，结合 ClosestPair.playground 源码，完整讲解 swift-algorithm-club 中利用分治（Divide and Conquer）思想将复杂度从暴力的 O(n²) 优化到 O(n log n) 的实现细节。读完本文，你将掌握该算法的完整求解步骤、strip 窄条构造与"最多比较 8 个点"的几何论证，并能直接运行 playground 验证结果。


问题定义与朴素解法的瓶颈

给定一个包含 n 个点的数组，我们想知道哪两个点之间的距离最短。最直观的做法是把每两个点都拿出来比较一次距离，共需比较 C(n, 2) = n(n-1)/2 次，时间复杂度高达O(n²)。当点数达到数千甚至数万时，这种两两比较的暴力方案将变得不可接受。

于是问题就变成了：如何在不比较每一对点的情况下，依然保证能找到全局最近的那一对？swift-algorithm-club 给出的答案是分治。

分治算法总体思路：五个核心步骤

本仓库的实现把整个求解过程拆解为以下五步：

1. 将点数组按X 轴坐标排序，使其在数组中呈现数学意义上的自然顺序；
2. 从中间一分为二，递归地划分出 Left、Right 两个子数组，直到每个子数组只剩下 3 个点（或更少）；
3. 基准情形：当点少于 3 个时，直接暴力两两比较，返回最小距离及对应的两个点；
4. 递归返回后，处理一个关键盲区——跨越分割线的点对：按 Y 轴重新排序，取出所有与分割线距离小于当前最小距离的点，构造 strip 窄条；
5. 在 strip 内做有约束的暴力搜索，若发现更小的距离则更新结果。

下面逐一对每个步骤做源码级剖析。

第一步：按 X 轴排序，为分治奠定基础

分治的前提是数组有序，这里复用并改造了仓库中归并排序的实现。入口函数 ClosestPairOf(points:) 首先执行一次按 X 轴坐标的排序：

var innerPoints = mergeSort(points, sortAccording : true) let result = ClosestPair(&innerPoints, innerPoints.count) return (result.minValue, result.firstPoint, result.secondPoint)

归并排序的 mergeSort(_:sortAccording:) 与 merge(leftPile:rightPile:sortAccording:) 与标准实现几乎一致，唯一的增强是布尔参数sortAccording：

• sortAccording = true：按 X 坐标升序比较（p1.x < p2.x）；
• sortAccording = false：按 Y 坐标升序比较（p1.y < p2.y）。

这个参数设计是算法整体效率的关键之一，因为算法后续还要对同一批点做一次 Y 轴排序，复用一个排序函数即可完成两次不同维度的有序化。

第二步：划分与基准情形（n ≤ 3 暴力求解）

递归函数 ClosestPair(_ p:inout [Point], _ n:Int) 的核心逻辑如下：当数组规模大于 3 时，从中间切开，mid左侧进入左半边、mid及之后进入右半边：

let mid:Int = n/2 let line:Double = (p[mid].x + p[mid+1].x)/2

line是左右两半之间的垂直分割线，取的是中间两个点在 X 轴上的中点坐标，后续 strip 构造会以它为准。

递归的出口是n <= 3的基准情形——此时直接使用两层嵌套循环暴力两两比较，返回最小距离及对应的两个点。可以看到代码中minDist初始化为Double.infinity，并用可空类型newFirst/newSecond暂存结果，这样即使点对不存在也能安全返回。

第三步：处理跨分割线的点对——构造 strip 窄条

当左右两半各自递归求解完成后，我们拿到了左半部分的最小值minLeft与右半部分的最小值minRight，二者取小者作为当前已知最小距离min。

但这还不够。如下图所示，可能存在一对点，一个在分割线左边、一个在右边，两者距离比左右任何一半内部的最近距离都小。由于递归只在自己的半边内部寻找，这类横跨分割线的点对会被漏掉：


解决思路是构造一个"窄条"（strip）：首先把当前整个数组按 Y 轴重新排序（p = mergeSort(p, sortAccording: false)），然后遍历所有点，凡是与分割线line的 X 轴距离小于当前min的点，都被收进 strip——因为一旦 X 轴距离已经超过min，它与另一侧任何点的欧氏距离必然大于min，绝无可能刷新纪录：

var strip = [Point]() var i=0, j = 0 while i<n { if abs(p[i].x - line) < min { strip.append(p[i]) j+=1 } i+=1 }

第四步：strip 内的搜索——为什么最多只比较 8 个点

strip 内点的搜索依然是两层循环的暴力比较，但这并不会让复杂度退化回 O(n²)，因为它存在一个巧妙的剪枝约束，并且有着严格的几何上界。

先看剪枝条件：strip 已按 Y 轴有序，因此对每个点strip[i]，只需向后扫描，一旦发现下一个点的 Y 坐标差已经超过min（意味着距离必然大于min），立即break跳出内层循环：

while i<j { x = i+1 while x < j { if (abs(strip[x].y - strip[i].y)) > min { break } if dist(strip[i], strip[x]) < temp { temp = dist(strip[i], strip[x]) tempFirst = strip[i] tempSecond = strip[x] } x+=1 } i+=1 }

那么"最多只比较 8 个点"的结论从何而来？如下图的几何直觉所示，strip 在空间上是一个宽度为 2×min、高度为 min 的矩形（左右各向分割线外延伸 min，上下只保留 Y 差在 min 以内的点）。我们忽略任何 Y 差大于 min 的点，于是所有被纳入比较的点都必须恰好落在这个 2×min × min 的矩形内：


几何论证如下：把该矩形沿长边对半分成两个 min × min 的小正方形，再沿短边对半分成四个 (min/2) × (min/2) 的小格子。由于任意两点距离小于 min 才会被纳入，而每个小格子的对角线长度为 min/√2 < min，因此每个小格子内至多只能有一个候选点——若同格出现两个点，它们之间的距离必然小于 min，这要么意味着它们就是新的最近点对（会被直接发现），要么违背了"当前最小距离为 min"的前提。四个小格子各至多一个点，总共最多 4 个点；再加上对该点两侧的对称考量，整个窗口内的候选点数量被严格限制在8 个以内（最坏情况）。

也就是说，strip 内每个点最多只需要与固定常数个（≤ 8）邻居比较，而非与 strip 内所有点两两比较。这保证了递归合并阶段是线性代价。

第五步：合并结果并返回

strip 搜索结束后，若发现比当前min更小的距离temp，就用新找到的点对替换原有结果；否则保持左右递归得到的最优解不变，最终返回元组(min, first, second)：

if temp < min { min = temp; first = tempFirst second = tempSecond } return (min, first, second)

代码中temp初始值取当前min、min初始值取Double.infinity的做法，保证了"当前已知最优解"在每一层递归中都能被正确继承，不会因初始化不当而干扰真实计算。

复杂度分析：为什么是 O(n log n)

整个算法的代价由三部分构成：

• 排序：入口处按 X 排序一次，加上每一层递归合并阶段按 Y 排序，两次归并排序均为 O(n log n)；
• 递归划分：每次把问题规模对半分解，递归深度为 O(log n)；
• 合并阶段：构造 strip 是 O(n) 的线性扫描，strip 内每个点最多与固定常数个点比较，合并总代价为 O(n)。

根据主定理，递推关系 T(n) = 2·T(n/2) + O(n) 的解为O(n log n)。相比朴素方案的 O(n²)，这是质的飞跃。文档也明确指出：复杂度能压到 O(n log n)，"主要归功于排序"——排序为分治提供了有序前提，Y 轴有序又让 strip 搜索的剪枝和常数上界成为可能。

另外值得说明的是，最坏情况的几何形态（每个窗口塞满 8 个点）在实际数据中很少出现，真实比较次数通常远小于理论上限，这也是该算法在实践中表现高效的原因之一。

源码走读：从入口到 playground 示例

辅助数据结构与距离函数

实现依赖两个轻量工具：定义点的 Point 结构体（持有x、y两个Double坐标），以及计算欧氏距离的 dist(::)：

struct Point { var x: Double var y: Double init(_ x:Double,_ y:Double) { self.x = x; self.y = y } } func dist(_ a: Point,_ b: Point) -> Double { let equation:Double = (((a.x-b.x)*(a.x-b.x))) + (((a.y-b.y)*(a.y-b.y))) return equation.squareRoot() }

运行示例与预期输出

playground 的 示例代码 构造了 8 个测试点，其中(0,2)与(6,67)两点相距最近（距离约 65.0），其余点的坐标都刻意拉得很远：

var points = [a,b,c,d,e,f,g,h] let endResult = ClosestPairOf(points: points) print("Minimum Distance : \(endResult.minimum), The two points : (\(endResult.firstPoint.x),\(endResult.firstPoint.y)), (\(endResult.secondPoint.x),\(endResult.secondPoint.y))")

运行后终端应输出类似：

Minimum Distance : 65.0, The two points : (0.0,2.0), (6.0,67.0)

你可以直接在 Xcode 中打开 ClosestPair.playground 运行这段代码，也可以修改points数组，用随机点或手工构造的边界数据（例如两点恰好位于分割线两侧）来验证算法在各种输入下都能正确返回最近点对。

延伸阅读

• 分治所依赖的排序算法实现，参见仓库中的 Merge Sort/README.markdown；
• 算法相关的复杂度概念可参考仓库根目录的 Big-O Notation.markdown；
• 最近点对问题在计算几何领域通常被称为 Closest Pair of Points Problem，本文描述的分治解法是该问题的经典求解范式。

本实现由 Ahmed Nader 为 Swift Algorithm Club 编写，完整实现与可运行示例均在 Closest Pair/ClosestPair.playground/Contents.swift 中。

【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club