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

选择排序详解

选择排序的核心思想在于每一趟从待排序列中选取一个关键字值最小的记录，将其放到已排序序列的末尾。第 1 趟从 n 个记录中选出最小值，第 2 趟从剩余的 n-1 个记录中选出次小值，依此类推，直到所有记录归位。

直接选择排序

核心思路

首先在所有记录中找出关键字最小的记录，与第一个记录交换；然后在剩余记录中找次小记录，与第二个记录交换。重复此过程，直到整个序列有序。

执行示例

假设待排序序列为 { 5, 3, 6, 4, 7, 1, 8, 2 }。初始视为无序序列，每趟遍历后，有序区长度 +1，无序区长度 -1。图示中红色标记代表已排序区域，实际推导时可用方框标注。

代码实现

public void selectSort() {
    RecordNode temp;
    // 进行 i-1 次遍历，this.curlen 为数组长度
    for(int i=0; i<this.curlen-1; i++) {
        int min = i;
        // 在无序区寻找最小值索引
        for(int j=i+1; j<this.curlen; j++) {
            if (r[j].key.compareTo(r[min].key) < 0) {
                min = j;
            }
        }
        // 如果找到更小的元素，则交换位置
        if (min != i) {
            temp = r[i];
            r[i] = r[min];
            r[min] = temp;
        }
    }
}

性能分析

直接选择排序的时间复杂度始终为 O(n²)，空间复杂度为 O(1)。虽然移动次数较少，但比较次数固定，稳定性较差（不稳定排序）。

树形选择排序

核心思路

先对 n 个记录两两比较，将较小者作为优胜者上升到父结点。重复此过程，直到选出最小关键字值。整个过程可用一棵含有 n 个叶子结点的完全二叉树表示。

执行示例

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

总结

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