选择排序详解：直接、树形与堆排序实战

过程解析

以序列 { 52, 39, 67, 95, 70, 8, 25, 52 } 为例。叶子节点位于最底层，两两 PK，胜者（较小值）上浮。例如 52 和 39 比，39 上移；70 和 8 比，8 上移。最终根节点为全局最小值。找到最小值后，将其标记为 ∞，再次沿路径向上比较，即可确定次小值。

性能分析

相比直接选择排序，树形选择减少了比较次数，时间复杂度约为 O(n log n)，但需要额外的辅助空间来存储树结构，且实现较为复杂。

堆排序

定义与性质

堆是一种特殊的完全二叉树结构。若所有非终端结点的值均大于等于其孩子结点，称为大顶堆；反之则为小顶堆。大顶堆的根节点一定是当前序列中的最大值，小顶堆则是最小值。

排序方法

堆排序利用堆的性质进行排序。首先将待排序序列构建成一个初始堆（通常是大顶堆用于升序），此时根节点最大。将根节点与末尾节点交换，使最大元素归位。然后缩小堆的范围，重新调整剩余节点使其满足堆性质。重复此过程直至堆大小为 1。

关键步骤：筛选与建堆

如何'筛选'？ 筛选是指当堆的某个子树被破坏时，自上而下调整的过程。例如，交换根节点后，新的根节点可能小于子节点，需将其与较大的子节点交换，并递归向下调整，直到恢复堆性质。

如何'建初始堆'？ 建堆是自下而上的过程。从最后一个非叶子节点开始向前遍历，依次调用筛选函数。因为叶子节点天然满足堆性质，所以只需关注内部节点。

以序列 { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 为例，从下标 4 开始调整，确保每个子树都是大顶堆，最后调整根节点完成建堆。

代码实现

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)。它是一种不稳定排序，但在处理大规模数据时表现优异，尤其适合内存受限的场景。

总结

三种选择排序变体各有侧重：

• 直接选择排序：逻辑简单，适合小规模数据或对交换次数敏感的场景。
• 树形选择排序：减少了比较次数，但空间开销较大，实际应用较少。
• 堆排序：综合性能最佳，时间复杂度稳定，是工程实践中常用的排序算法之一。

实际开发中，若需排升序建立大顶堆，降序则建立小顶堆。理解筛选与建堆的自底向上特性，是掌握堆排序的关键。