并查集与排序（归并、快排、堆排）

前面几篇都在讲"怎么组织数据、怎么查找"。本篇补两个 CS61B 里极其常用、却容易被低估的工具：**并查集（Union-Find）**管"动态连通性"，三大 O(n log n) 排序管"把数据排好序"。它们一个藏在 Kruskal 最小生成树里，一个藏在 Arrays.sort 背后——看似简单，细节全是坑。

一、并查集：谁和谁是一伙的？

一句话：并查集维护若干"不相交集合"，支持两个操作——find(x) 找 x 的祖先（代表），union(x,y) 把 x、y 所在集合合并。它回答的是"这两个元素连通吗"。

典型场景：逐步加边建网络，随时问"a 和 b 现在通不通"；或 Kruskal 算法里判断加一条边会不会成环。

1.1 朴素 vs 优化

朴素实现 union 直接把一棵树挂到另一棵，最坏退化成链，find 变 O(n)。两个经典优化把它压到几乎 O(1)（反阿克曼函数 α(n)，实际常数级）：

按秩/大小合并（union by rank/size）：总是把"矮的树"挂到"高的树"下面，避免长高。
路径压缩（path compression）：find 时把沿途节点直接接到祖先，扁平化。

class UnionFind {
    private int[] parent, rank;
    UnionFind(int n){
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;   // 初始各自为营
    }
    int find(int x){                                   // 带路径压缩
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    boolean union(int x, int y){                       // 带按秩合并
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;                    // 已连通，成环
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
        return true;
    }
}

public static void main(String[] args){
    UnionFind uf = new UnionFind(5);
    uf.union(0, 1); uf.union(2, 3); uf.union(1, 2);
    System.out.println("0 与 3 连通? " + (uf.find(0) == uf.find(3)));
    System.out.println("0 与 4 连通? " + (uf.find(0) == uf.find(4)));
}

1 2	0 与 3 连通? true 0 与 4 连通? false

坑①：find 里 parent[x] = find(parent[x]) 是路径压缩的关键一行，漏写就退回朴素。另：union 返回 false 正说明"已连通"，Kruskal 借此跳过会成环的边——这反而是有用信号，不是错误。

二、归并排序：稳稳的 `O(n log n)`

分治法：把数组对半切，递归排好左右两半，再合并两个有序段（双指针）。

static void mergeSort(int[] a, int l, int r){
    if (l >= r) return;
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}
static void merge(int[] a, int l, int m, int r){
    int[] tmp = new int[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, l, tmp.length);
}

特性：稳定、最坏也是 O(n log n)，但要 O(n) 辅助空间。适合链表排序（无需额外大空间）和对"稳定性"有要求的场景。

三、快速排序：平均最快，但怕有序

选一个基准（pivot），把比它小的放左、大的放右（partition），再递归两边。原地、缓存友好，实践中常最快。

static void quickSort(int[] a, int l, int r){
    if (l >= r) return;
    int p = partition(a, l, r);     // 返回基准最终位置
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}
static int partition(int[] a, int l, int r){
    int pivot = a[r], i = l;        // Lomuto 划分，基准取最右
    for (int j = l; j < r; j++)
        if (a[j] < pivot) { int t = a[i]; a[i] = a[j]; a[j] = t; i++; }
    int t = a[i]; a[i] = a[r]; a[r] = t;
    return i;
}

坑②：最坏 O(n²)——当数组已序且 pivot 总取最值（每次只削掉一个元素）。工程上用随机 pivot 或三数取中来规避；Arrays.sort 对基本类型用的是"双轴快排 + 切换到插排"的混合体（introsort 思路）。

四、堆排序：原地、稳定 `O(n log n)` 但欠稳

先 O(n) 建堆，然后反复 extractMin 把最值放到末尾。原地、最坏 O(n log n)，但不稳定，且缓存表现不如快排。

static void heapSort(int[] a){
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);  // 建堆 O(n)
    for (int end = n - 1; end > 0; end--){
        int t = a[0]; a[0] = a[end]; a[end] = t;             // 堆顶换到末尾
        siftDown(a, 0, end);                                 // 下沉恢复
    }
}
static void siftDown(int[] a, int i, int n){
    while (2 * i + 1 < n){
        int c = 2 * i + 1;
        if (c + 1 < n && a[c + 1] > a[c]) c++;
        if (a[i] >= a[c]) break;
        int t = a[i]; a[i] = a[c]; a[c] = t; i = c;
    }
}

五、三排序 + 并查集：一张总表

算法	平均	最坏	空间	稳定	备注
归并排序	`O(n log n)`	`O(n log n)`	`O(n)`	✅	适合链表、外部排序
快速排序	`O(n log n)`	`O(n²)`	`O(log n)`	❌	平均最快，怕有序
堆排序	`O(n log n)`	`O(n log n)`	`O(1)`	❌	原地、最坏稳，缓存差
并查集（含两优化）	`O(α(n))`	`O(α(n))`	`O(n)`	—	动态连通性

本质一句话：排序三兄弟都是 O(n log n)，差别在"稳定与否、要不要额外空间、最坏怕不怕"；并查集则是个不同赛道——它不排序，只回答"连通吗"，却靠两个小优化达到近乎常数。

六、Java 与 C++：库里到底用了谁？

操作	Java	C++
对象数组排序	`Arrays.sort` → TimSort（稳定）	`std::sort` → introsort（不稳定）
基本类型排序	双轴快排变体	introsort（快排+堆排+插排）
并查集	无内置，自写	无内置，自写（或 Boost）

坑③：别以为 Arrays.sort 一定是快排——对对象它用 TimSort（稳定、归并系），对基本类型才用快排系。混用 Integer[] 与 int[] 排序，稳定性天差地别。

七、小结

是什么：并查集管动态连通（find/union + 路径压缩 + 按秩合并）；归并/快排/堆排是三种 O(n log n) 排序。
坑：并查集漏写路径压缩会退化；快排遇有序最坏 O(n²)；堆排不稳定；Java 对象排序稳定、基本类型不稳定。
本质一句话：要连通性用并查集，要全序用排序；排序里"要稳定选归并、要原地选堆排、要平均最快选快排"——按约束挑，别无脑快排。

带着三个问题读每一篇会更有收获：① 我的数据需要连通判断还是排序？前者并查集，后者排序。 ② 排序要稳定吗？要就归并/TimSort。 ③ 快排最坏怎么防？随机 pivot 或 introsort。