选择排序的 Java 实现：直接选择、树形选择与堆排序

这种方法用完全二叉树模拟淘汰赛：叶子放原始数据，两两比较，较小者上升到父结点，最终根结点就是最小值。

对序列 { 52, 39, 67, 95, 70, 8, 25, 52 }，建成树后最小值为 8：

找到最小值后，把它的叶子改成无穷大 "∞"，然后从该叶子向上重新比较，就能取出次小值。反复此过程得到有序序列。

树形选择减少了比较次数，但需要 O(n) 额外空间维护树结构。工程中这个常数开销往往比直接选择还大，实际用得很少。

堆排序

堆是一种完全二叉树，分两种形态：

• 大顶堆：每个父节点的值 ≥ 子节点（根最大）
• 小顶堆：每个父节点的值 ≤ 子节点（根最小）

堆排序分为两步：

1. 建堆：把无序数组调整成大顶堆（或小顶堆）
2. 反复交换堆顶与末尾元素，然后调整剩余部分重新成堆

调整的过程叫'筛选'（sift down）：当堆顶被替换后，从上往下比较，若违反堆性质则下沉。以序列 { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 为例，初始大顶堆，98 在根。

交换 98 和末尾的 36 后，12 跑到根上，需要筛选恢复堆性质。

比较 12、81、49，81 最大，与 12 交换。

继续向下：73、12、36，73 最大，再交换。

反复交换-筛选，最大值依次'沉底'，排序完成。

建堆则是从下往上堆化：从最后一个非叶节点开始向前，对每个节点做筛选，确保子树都满足堆性质。同样用上面的例子：

最后调整根节点，得到初始大顶堆。

完整堆排序的 Java 实现：

public class HeapSort {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        buildMaxHeap(arr, len);
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
    }

    private static void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2) - 1; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private static void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largestIndex = i;
        if (left < len && arr[left] > arr[largestIndex]) {
            largestIndex = left;
        }
        if (right < len && arr[right] > arr[largestIndex]) {
            largestIndex = right;
        }
        if (largestIndex != i) {
            swap(arr, i, largestIndex);
            heapify(arr, largestIndex, len);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

堆排序的时间复杂度 O(n log n)，空间 O(1)，但交换时会打乱顺序，不稳定。如果要升序排序，需要建大顶堆；降序则建小顶堆。

三种选择排序，直接选择最简单但慢，O(n²) 的代价几乎无法用于大量数据；树形选择试图优化比较次数，却引入了显著的空间开销；堆排序在时间和空间上都找到了平衡，原地 O(n log n) 让它成为实用之选，只不过稳定性欠奉。建堆和筛选这两个操作贯穿始终，理解它们也就理解了堆排序的核心。