数据结构：选择排序原理与 Java 代码实现 | 极客日志

Javajava算法

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

选择排序包含直接选择、树形选择和堆排序三种变体。核心思想是每趟从待排序序列中选出关键字最小（或最大）的记录，放到已排序序列的末尾。直接选择排序时间复杂度为 O(n²)，空间复杂度 O(1)。堆排序利用完全二叉树性质，通过建堆和筛选操作，将时间复杂度优化至 O(n log n)，适合大数据量场景。通过图解和 Java 代码详细解析了这三种算法的原理及实现细节。

月亮邮递员发布于 2026/3/25更新于 2026/4/252 浏览

选择排序详解

选择排序的核心思想很直观：每一趟从待排序列中选取一个关键字值最小（或最大）的记录，放到已排序序列的末尾。第 1 趟从 n 个记录中选出最小的，第 2 趟从剩下的 n-1 个里选次小的，直到所有记录归位。

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