数据结构实战：选择排序原理与 Java 实现

执行示例

以序列 { 52, 39, 67, 95, 70, 8, 25, 52 } 为例。叶子节点位于最后一层，两两 PK，谁小谁上父亲节点。找到最小值后，将其替换为无穷大'∞'，再次两两 PK 即可找到次小值，以此类推完成排序。

性能分析

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

堆排序

定义与方法

堆是一种特殊的完全二叉树结构。若所有非终端结点的值均不大于其左右孩子结点，称为大顶堆；反之则为小顶堆。堆排序利用堆的性质，每次将堆顶元素（最大或最小值）与末尾元素交换，再重新调整堆。

筛选过程

所谓'筛选'，是指当堆顶被破坏后，从上往下调整使整棵树恢复堆性质的过程。例如，最大值 98 与末尾元素交换后，原末尾元素下沉至根节点，此时需重新筛选，确保左/右子树仍满足堆条件。

建初始堆

建堆是一个从下往上进行'筛选'的过程。对于长度为 n 的序列，从最后一个非叶节点开始向前遍历，依次调整节点性质。注意调整过程中可能会打破子树的堆性质，需递归继续调整。

代码实现

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)。它是不稳定排序，但在处理大规模数据时表现优于直接选择排序。

总结

• 直接选择排序：逻辑简单，适合小规模数据，但效率较低。
• 树形选择排序：减少比较次数，适合外部排序场景，但空间开销较大。
• 堆排序：效率高，适合大规模数据。升序建大堆，降序建小堆。筛选是破坏后调整，建堆是从下往上调整。