Java 选择排序：最简单粗暴的”找最小”

每一轮都挑最矮的站前面——像极了军训排队

引言

选择排序（Selection Sort）的哲学是：不求过程优雅，只求结果正确。

每一轮扫遍全场，找出最小的，然后往前面一扔。比冒泡还简单，但代价是永远 O(n²)，稳定得让人绝望。

为什么面试还要考？因为它揭示了一个深刻的工程思想——**”用最少的交换次数完成排序”**。在某些交换成本极高的场景（比如交换的是大对象或数据库记录），选择排序反而是最优解。

这篇文章，我会把选择排序讲透：

• 用 ASCII 图演示每轮的”挑选+交换”过程
• 推导为什么它不稳定（这是高频考点）
• 列出 4 个高频易错点
• 配套 LeetCode 215（第 k 大元素）的选择排序变形解法

---

1. 核心思想：每轮挑出最小的放前面

1.1 通俗理解

想象一群人按身高排队：

第 1 轮：从所有人里挑出最矮的，让他站到第 1 位
第 2 轮：从剩下的 n-1 个人里挑出最矮的，让他站到第 2 位
第 3 轮：从剩下的 n-2 个人里挑出最矮的，让他站到第 3 位
...

1.2 ASCII 图解演示

以数组 [5, 2, 8, 4, 7] 为例：

初始：[5, 2, 8, 4, 7]

第 1 轮（i=0）：
  扫描整个数组，找最小值
  minIndex = 1（值 2）
  交换 arr[0] 和 arr[1]
  结果：[2, 5, 8, 4, 7]   ← 2 到位

第 2 轮（i=1）：
  扫描 [5, 8, 4, 7]，找最小值
  minIndex = 3（值 4）
  交换 arr[1] 和 arr[3]
  结果：[2, 4, 8, 5, 7]   ← 4 到位

第 3 轮（i=2）：
  扫描 [8, 5, 7]，找最小值
  minIndex = 3（值 5）
  交换 arr[2] 和 arr[3]
  结果：[2, 4, 5, 8, 7]   ← 5 到位

第 4 轮（i=3）：
  扫描 [8, 7]，找最小值
  minIndex = 4（值 7）
  交换 arr[3] 和 arr[4]
  结果：[2, 4, 5, 7, 8]   ← 7 到位

1.3 三个关键观察

1. 每轮只交换一次——这是选择排序的核心优势（比冒泡交换次数少 n 倍）
2. 比较次数是固定的 n(n-1)/2——无论数组是否有序，都得一视同仁地扫
3. 前面 i 个元素一定是有序的——因为每轮都把最小值放到前面

---

2. 完整 Java 实现

import java.util.Arrays;

public class SelectionSort {
    /**
     * 选择排序
     * @param arr 待排序数组（原地修改）
     */
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            // 在未排序部分找最小值下标
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换（只交换一次）
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 10, 14, 37, 13};
        System.out.println("排序前: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

优化点：if (minIndex != i) 检查——如果最小值已经在当前位置，无需交换，省一次操作。

---

3. 复杂度证明

3.1 时间复杂度

比较次数：永远是 n(n-1)/2

• 第 1 轮比较 n-1 次
• 第 2 轮比较 n-2 次
• …
• 第 n-1 轮比较 1 次
• 总比较次数 = (n-1) + (n-2) + … + 1 = n(n-1)/2

交换次数：

• 最坏情况：n-1 次（每轮都交换）
• 最好情况：0 次（数组已经有序）

结论：无论输入数据如何，时间复杂度都是 **O(n²)**，无法优化。

3.2 空间复杂度

• 只使用常数个额外变量（i, j, minIndex, temp）
• **O(1)**，原地排序

3.3 稳定性：不稳定（重要考点）

选择排序不是稳定排序，这是面试高频考点。

反例：[5a, 5b, 3] → 排序后 [3, 5b, 5a]

初始：[5a, 5b, 3]

第 1 轮：
  扫描找最小值，minIndex = 2（值 3）
  交换 arr[0] 和 arr[2]
  结果：[3, 5b, 5a]   ← 5a 和 5b 的相对顺序变了！

原因：交换时跳过了中间元素，打破了相同元素的相对顺序。

怎么改成稳定：用数组插入代替交换，但代价是 O(n) 空间——不如直接用插入排序。

---

4. 四个高频易错点

易错点 1：minIndex 初始化为 0

// ❌ 错误：每轮都会错误地拿 arr[0] 做比较基准
int minIndex = 0;
for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[minIndex]) minIndex = j;
}

// ✅ 正确：每轮从 i 开始
int minIndex = i;
for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[minIndex]) minIndex = j;
}

易错点 2：内层循环从 0 开始

// ❌ 错误：会重复比较已有序的前面元素
for (int j = 0; j < n; j++) { ... }

// ✅ 正确：从 i+1 开始，只扫描未排序部分
for (int j = i + 1; j < n; j++) { ... }

易错点 3：外层循环 i < n

// ❌ 错误：多跑一轮空比较
for (int i = 0; i < n; i++) { ... }

// ✅ 正确：n 个元素排 n-1 轮
for (int i = 0; i < n - 1; i++) { ... }

易错点 4：忘记 if (minIndex != i) 优化

// ⚠️ 不是 bug，但浪费一次交换
swap(arr, i, minIndex);

// ✅ 优化：只在需要时交换
if (minIndex != i) {
    swap(arr, i, minIndex);
}

---

5. 选择排序 vs 冒泡排序

维度	选择排序	冒泡排序
比较次数	固定 n(n-1)/2	最坏 n(n-1)/2，最好 n-1
交换次数	最坏 n-1，最好 0	最坏 n(n-1)/2
时间复杂度	永远 O(n²)	最坏 O(n²)，最好 O(n)
稳定性	不稳定	稳定
适用场景	交换成本高	基本有序

选择排序的核心优势：交换次数极少（最多 n-1 次），适合交换成本极高的场景。

---

6. 适用场景与禁区

6.1 适用场景

• 数据量极小（n < 100）：代码简单，常数小
• 交换成本极高：比如交换的是大对象、长字符串、数据库记录
• **需要”最少的写入次数”**：嵌入式 flash 写入
• 无稳定性要求：比如纯数值排序

6.2 不适用场景

• 大数据量（n > 1000）：O(n²) 跑不动
• 要求稳定排序：选择排序不稳定，改成稳定版本需要额外 O(n) 空间
• 生产环境：直接用 Arrays.sort()

---

7. 面试常见变形

变形 1：双向选择排序

思路：每轮同时找最小和最大，分别放到两端

public static void bidirectionalSelectionSort(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int minIndex = left, maxIndex = right;
        for (int j = left; j <= right; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
            if (arr[j] > arr[maxIndex]) maxIndex = j;
        }
        // 交换最小值到 left
        swap(arr, left, minIndex);
        // 注意：如果 maxIndex == left，交换后 maxIndex 需要更新
        if (maxIndex == left) maxIndex = minIndex;
        // 交换最大值到 right
        swap(arr, right, maxIndex);
        left++;
        right--;
    }
}

优点：轮次减半。

变形 2：选择第 k 小元素

思路：只跑 k 轮，第 k 轮结束后 arr[k-1] 就是第 k 小

public static int findKthSmallest(int[] arr, int k) {
    int n = arr.length;
    for (int i = 0; i < k; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        swap(arr, i, minIndex);
    }
    return arr[k - 1];
}

适用：k 较小（k < n/2）时比全排序更省时间。

---

8. LeetCode 真题实战

题目 1：215. 数组中的第 K 个最大元素（中等）

描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

选择排序解法：

public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    // 找第 k 大 = 找第 n-k 小
    int target = n - k;
    for (int i = 0; i <= target; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) minIndex = j;
        }
        swap(nums, i, minIndex);
    }
    return nums[target];
}

复杂度：时间 O(n²)，空间 O(1)。在 LeetCode 上会超时（n=10000）。

实战建议：面试时先用选择排序展示思路，再优化成快速选择（O(n)）拿满分。

题目 2：912. 排序数组（中等）

选择排序解法：直接套用模板。

结果：n=50000 时超时，提交后只能过部分用例。

---

总结

一句话精髓

选择 = 每轮扫全场找最小 + 只交换一次。

三个关键洞察

1. **永远 O(n²)**——比较次数固定，无法优化（这是它最大的缺点）
2. 不稳定——交换会破坏相同元素的相对顺序（高频考点）
3. 交换次数极少——最多 n-1 次，适合交换成本极高的场景

下一步行动

1. 手写双向选择排序，理解 maxIndex == left 的细节
2. 用选择排序解 LeetCode 215，观察超时边界
3. 对比选择排序和冒泡排序的交换次数，理解何时选哪种

---