数据结构：选择排序与堆排序详解及 Java 实现 | 极客日志

Javajava算法

数据结构：选择排序与堆排序详解及 Java 实现

选择排序系列包含直接选择、树形选择与堆排序。核心在于每趟从待排序列中选出极值记录并交换至有序区。直接选择法逻辑简单但效率低；树形选择通过锦标赛机制减少比较；堆排序基于完全二叉树结构，性能最优。文中结合 Java 代码详解建堆、筛选过程及性能分析，帮助深入理解排序算法原理。

Ne0发布于 2026/3/150 浏览

数据结构：选择排序与堆排序详解及 Java 实现

选择排序系列详解

选择排序的核心思想其实很直观：每一趟从待排序列中选取一个关键字值最小（或最大）的记录，通过交换位置逐步构建有序序列。第 1 趟从 n 个记录中选出最小值放到第 1 位，第 2 趟从剩下的 n-1 个记录中选出次小值放到第 2 位，直到所有记录归位。

直接选择排序

原理与过程

直接选择排序是最基础的选择排序方式。它的基本操作是：在所有记录中选出关键字最小的记录，把它与第一个记录进行位置交换；然后在其余记录中再选出关键字次小的记录与第二个记录交换，依此类推。

下图展示了直接选择排序的完整过程：

文章配图

实例演示

假设待排序的 8 个记录的关键字序列为 { 5, 3, 6, 4, 7, 1, 8, 2 }。初始序列视为无序序列，我们从无序区中选择最小的元素跟该区的第一个数交换，构成有序区。

在这里插入图片描述

每趟遍历完成后，有序序列记录的个数加 1，无序序列的个数减 1。虽然逻辑简单，但它的效率并不高，因为无论数据是否有序，比较次数都是固定的。

代码实现

public void selectSort() {
    RecordNode temp; // 定义一个临时变量 temp
    for (int i = 0; i < this.curlen - 1; i++) { // 进行 i-1 次遍历，this.curlen：数组的长度
        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;
        }
    }
}

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