数据结构与算法 / 系统课时

选择排序

选择排序

选择排序通过反复寻找未排序区间中的最小元素,并把它放到当前区间起点,完成原地升序排列。本课将实现一个可运行的 Java 版本,并准确统计比较次数与数据交换次数。

学习目标

  • 说明选择排序每一轮如何缩小未排序区间。
  • 使用 Java 实现原地选择排序并验证结果。
  • 分析比较次数、交换次数、稳定性和复杂度。

问题定义

给定一个长度为 n 的数组,选择排序把数组划分为“已排序区间”和“未排序区间”。第 i 轮在下标 i 到 n - 1 中寻找最小值,再将其交换到下标 i。完成一轮后,已排序区间向右扩展一个元素。

选择排序逐轮选择最小元素的过程

核心原理

选择排序的关键循环不变式是:第 i 轮开始时,下标 0 到 i - 1 已经包含全局最小的 i 个元素,并且按升序排列。第 0 轮前缀为空。每轮把剩余最小项放在前缀末尾,已确定的项保持不动。交换不增删记录。最后剩一项时它必在正确位置,空数组或单元素直接满足要求。

对于长度为 n 的数组,各轮比较次数依次为 n - 1、n - 2,直到 1,总比较次数固定为:

n(n−1)2\frac{n(n-1)}{2}

无论输入是否接近有序,基础选择排序都必须完成这些比较。交换次数最多为 n - 1;当最小元素已就位时跳过交换。n≥1 时最多 n−1 次,n=0 时为 0。一次交换包含两次数组写入,另有暂存变量赋值。

这个交换式实现不稳定。例如 [2A, 2B, 1C] 首轮交换 2A 与 1C,得到 [1C, 2B, 2A],两条键为 2 的记录顺序反转。可改为抽出第一个最小项并把中间记录右移,代价是移动次数可能变成平方级。它的额外空间复杂度为 O(1),平均和最坏时间复杂度均为 O(n^2)。

完整可运行示例

下面的程序在排序时统计比较次数和真实交换次数。将代码保存为 SelectionSortDemo.java。

java
import java.util.Arrays;

public class SelectionSortDemo {

    public static void main(String[] args) {
        int[] values = {64, 25, 12, 22, 11};

        SortStats stats = selectionSort(values);

        System.out.println("排序结果: " + Arrays.toString(values));
        System.out.println("比较次数: " + stats.comparisons);
        System.out.println("交换次数: " + stats.swaps);
    }

    static SortStats selectionSort(int[] values) {
        long comparisons = 0;
        int swaps = 0;

        for (int i = 0; i < values.length - 1; i++) {
            int minIndex = i;

            // 在未排序区间中寻找最小元素的下标。
            for (int j = i + 1; j < values.length; j++) {
                comparisons++;
                if (values[j] < values[minIndex]) {
                    minIndex = j;
                }
            }

            // 最小元素已经就位时,不进行无意义交换。
            if (minIndex != i) {
                int temp = values[i];
                values[i] = values[minIndex];
                values[minIndex] = temp;
                swaps++;
            }
        }

        return new SortStats(comparisons, swaps);
    }

    static class SortStats {
        final long comparisons;
        final int swaps;

        SortStats(long comparisons, int swaps) {
            this.comparisons = comparisons;
            this.swaps = swaps;
        }
    }
}

运行命令

bash
javac -encoding UTF-8 SelectionSortDemo.java
java SelectionSortDemo

预期输出

text
排序结果: [11, 12, 22, 25, 64]
比较次数: 10
交换次数: 3

复杂度与适用场景

指标 结论
最好、平均、最坏时间复杂度 Θ(n²),比较次数与排列无关
额外空间复杂度 O(1)
稳定性 通常不稳定
数据移动次数 最多 n - 1 次交换

选择排序的优势不是比较少,而是数据移动少。当元素交换成本明显高于比较成本、数据规模较小且不要求稳定性时,它比频繁交换相邻元素的算法更有吸引力。

Tips

  • 使用 minIndex 记录位置,不要在扫描过程中立即交换,否则会破坏“一轮只确定一个位置”的结构。
  • 只有 minIndex != i 时才交换,统计结果才能反映真实数据移动次数。
  • 调试时可在每轮结束后打印数组,检查已排序区间是否持续扩大。

常见错误

1. 未排序区间边界写错

若内层循环从 0 开始,每一轮都会重复扫描已排序区间。正确范围应从 i + 1 开始,并一直比较到数组末尾。

2. 把赋值次数当作交换次数

一次交换通常需要三次赋值,但算法分析中的“交换次数”应按一次元素位置互换计数。统计口径必须在代码和结论中保持一致。

本课练习

  1. 将示例数组改为已经升序的数组,验证比较次数是否仍为 n(n - 1) / 2,并观察交换次数。
  2. 修改程序,使其按降序排列,同时保持比较次数和交换次数统计正确。

本课总结

  • 选择排序每轮从未排序区间选择最小元素,并固定一个最终位置。
  • 比较次数与输入顺序无关,始终为 n(n - 1) / 2。
  • 算法原地执行且移动次数少,但时间复杂度为 O(n^2),通常不稳定。

下一课预告

下一课将学习“冒泡排序”,重点观察相邻元素交换如何把较大元素逐轮推向数组末端,并实现提前终止优化。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

选择排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通