排序-并查集

“排序并查集” 不是一个常见的术语，我认为您可能在表述上存在一些误解。通常，”排序” 和 “并查集” 是两种不同的数据结构和算法。

1. 排序：排序是一种将数据元素按照一定规则重新排列的操作。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。这些算法根据元素的比较和交换操作来实现排序。

2. 并查集：并查集（Disjoint Set Union，简称 DSU）是一种用于处理元素分组问题的数据结构。它主要支持两种操作：合并（Union）和查找（Find）。合并操作将两个不相交的集合合并为一个集合，而查找操作用于确定一个元素属于哪个集合。并查集常用于解决集合的合并、连通性问题等。

以下是一个简单的 Java 实现示例，展示如何实现并查集：

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return;
        }

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

public class UnionFindExample {
    public static void main(String[] args) {
        int n = 6; // 元素个数
        UnionFind uf = new UnionFind(n);

        uf.union(0, 1);
        uf.union(2, 3);
        uf.union(4, 5);

        System.out.println(uf.find(1) == uf.find(0)); // 输出 true，因为已经合并
        System.out.println(uf.find(1) == uf.find(2)); // 输出 false，因为不在同一个集合中
    }
}

在上面的示例中，我们首先创建了一个 UnionFind 类来实现并查集。parent 数组存储每个元素的父节点，rank 数组存储每个集合的秩（树的深度）。在 find 方法中使用路径压缩优化，通过递归将节点的父节点直接指向根节点，以减小树的深度。

union 方法用于合并两个集合，根据秩的大小选择将一个集合的根节点连接到另一个集合的根节点，并更新秩。

这只是一个简单的并查集实现示例。在实际应用中，可能需要更多的优化和扩展，例如按秩合并、路径压缩等。