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

示例演示

对于序列 {52, 39, 67, 95, 70, 8, 25, 52}，关键字处在最后一层的叶子节点上。两两 PK，谁小谁上去到父亲节点。找到最小值后，将其替换为无穷大，再次两两 PK 找次小值，以此类推。

复杂度评估

堆排序

定义与方法

堆通常指满足特定性质的完全二叉树。若所有非终端结点的值均不大于其左右孩子结点的值，称为大顶堆；反之则为小顶堆。大顶堆的根节点一定是整个序列中最大的，小顶堆则是最小的。

排序流程：

1. 将待排序序列对应成一棵完全二叉树，并转换成初始堆。
2. 根结点具有最大（或最小）的关键字值，交换根结点和最后一个结点的位置。
3. 除最后一个结点外，前 n-1 个结点仍构成完全二叉树，调整它们为一个新堆。
4. 重复上述步骤，直到只剩下一个根结点。

筛选机制

所谓'筛选'，指的是调整的过程。对一棵左/右子树均为堆的完全二叉树，调整根结点使整个二叉树也成为一个堆。这是一个从上往下进行的过程。

例如序列 {40, 55, 49, 73, 12, 27, 98, 81, 64, 36}。建好大顶堆后，最大值 98 在根节点。将其与末尾 36 交换，此时 12 下沉到根位置，破坏了堆性质，需要重新筛选。先看 12、81、49，将 81 提上来；接着 73、12、36，将 73 提上来。最终恢复大顶堆结构，继续交换根节点与当前末尾。

建初始堆

建堆是一个从下往上进行'筛选'的过程。如果建一个大顶堆，最顶上的根结点一定是最大的。

以序列 {40, 55, 49, 73, 12, 27, 98, 81, 64, 36} 为例：

1. 从最后一个非叶节点开始向前遍历。
2. 下标 4 和 9 比较，36 比 12 大，36 上去。
3. 左边下标 3、7、8，81 比 73、64 大，81 上去。
4. 右边下标 2、5、6，98 比 27、49 大，98 上去。
5. 依次向上调整，注意调整过程中可能会打破子树上的堆，需要递归继续调。

关键实现

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;
    }
}

复杂度评估

总结

三种选择排序策略各有特点：

• 直接选择排序：每趟选最小值交换，逻辑简单，适合小规模数据。
• 树形选择排序：利用二叉树减少比较次数，适合外部排序场景。
• 堆排序：基于完全二叉树性质，通过建堆和筛选实现高效排序。升序建大堆，降序建小堆。筛选是破坏后比较交换，从上到下；建堆是从下往上筛选。