Java 实现选择排序：[通俗易懂的排序算法系列之一]

发布于：2025-04-06 ⋅ 阅读:(33) ⋅ 点赞:(0)

引言

大家好！从今天开始，我计划写一个关于常见排序算法的系列文章，旨在用通俗易懂的方式，结合 Java 代码实现，帮助大家理解和掌握这些基础但非常重要的数据结构与算法知识。

排序是计算机科学中最基本的操作之一，无论是在日常开发还是面试中，都经常遇到。理解不同排序算法的原理和特性，对于编写高效、健壮的代码至关重要。

本系列的第一篇，我们来聊聊 选择排序 (Selection Sort)。

什么是选择排序？

选择排序是一种简单直观的排序算法。它的核心思想非常符合人类的直觉：

想象一下，你面前有一排高矮不一的人，你想让他们按身高从矮到高排好队。使用选择排序的方法就是：

  1. 第一轮： 从所有未排序的人中，找到最矮的那个人。然后，让他站到队伍的最左边（也就是第一个位置）。
  2. 第二轮： 从剩下的未排序的人中，再次找到最矮的那个人。让他站到当前已排好队的人后面（也就是第二个位置）。
  3. 重复这个过程： 每一轮都从未排序的人中选出最矮的，放到已排序队伍的末尾，直到所有人都排好队。

总结起来，选择排序的工作原理就是：每一轮从未排序的区间中挑选出最小值（或最大值），然后将其放置在已排序区间的末尾（或开头）。

算法步骤详解

以升序排序为例，选择排序的具体步骤如下：

  1. 初始状态： 整个数组被视为“未排序”区间。
  2. 第 1 轮：
    • 在整个数组（索引 0 到 n-1）中查找最小值。
    • 将找到的最小值与数组的第一个元素（索引 0）交换位置。
    • 现在，索引 0 的元素是最小的，属于“已排序”区间；索引 1 到 n-1 属于“未排序”区间。
  3. 第 2 轮：
    • 在未排序区间（索引 1 到 n-1）中查找最小值。
    • 将找到的最小值与未排序区间的第一个元素（索引 1）交换位置。
    • 现在，索引 0 到 1 的元素已排序；索引 2 到 n-1 属于未排序区间。
  4. 重复…
  5. 第 i 轮：
    • 在未排序区间（索引 i-1 到 n-1）中查找最小值。
    • 将找到的最小值与未排序区间的第一个元素（索引 i-1）交换位置。
    • 现在，索引 0 到 i-1 的元素已排序；索引 i 到 n-1 属于未排序区间。
  6. 结束： 当进行到第 n-1 轮时，只需要比较最后两个元素，将较小者放到索引 n-2 的位置，最大的元素自然就留在了最后一个位置（索引 n-1）。整个数组排序完成。

图示 (可选): 你可以在 CSDN 编辑器中用简单的文本或上传图片来模拟这个过程，例如：

Initial:  [31, 5, 1, 19, 8]
Round 1: Find min (1) in [31, 5, 1, 19, 8]. Swap 1 and 31.
          -> [1, 5, 31, 19, 8]  (Sorted: [1])
Round 2: Find min (5) in [5, 31, 19, 8]. 5 is already at index 1. No swap needed.
          -> [1, 5, 31, 19, 8]  (Sorted: [1, 5])
Round 3: Find min (8) in [31, 19, 8]. Swap 8 and 31.
          -> [1, 5, 8, 19, 31]  (Sorted: [1, 5, 8])
Round 4: Find min (19) in [19, 31]. 19 is already at index 3. No swap needed.
          -> [1, 5, 8, 19, 31]  (Sorted: [1, 5, 8, 19])
Done.   Last element (31) is automatically in place.

Java 代码实现

下面是选择排序的 Java 代码实现：

import java.util.Arrays;

public class SelectSort { // 类名建议大写开头

    public static void main(String[] args) {
        int[] arr = {31, 5, 1, 19, 8, 11, 45, 22, 35, 49, 40, 48, 50};
        System.out.println("排序前的数组: " + Arrays.toString(arr));
        standardSelectSort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }

    /**
     * 标准选择排序：
     * 每一轮从未排序的部分找到最小值，放到已排序部分的末尾（也就是未排序部分的开头）。
     * @param arr 要排序的数组
     */
    public static void standardSelectSort(int[] arr) {
        // 处理边界情况：null 或 长度小于2 的数组无需排序
        if (arr == null || arr.length < 2) {
            return;
        }

        // 外层循环控制轮数，总共需要 n-1 轮
        // i 代表当前轮次需要确定最小值的目标位置，也即已排序区间的边界
        // i 只需要到 arr.length - 2，因为当处理完第 n-1 个元素时，最后一个元素自动就位
        for (int i = 0; i < arr.length - 1; i++) {

            // !!! 关键点 1: 记录最小值的索引
            // 每一轮开始，假设当前未排序部分的第一个元素 (arr[i]) 就是最小的
            int minIndex = i;

            // 内层循环：从 i+1 开始遍历剩余的未排序部分，查找真正最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                // !!! 关键点 2: 比较，找到更小的值
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 如果发现更小的值，更新最小值的索引
                }
            }

            // !!! 关键点 3: 交换
            // 在内层循环结束后，minIndex 就指向了从未排序部分 [i...n-1] 中找到的最小值的索引
            // 如果最小值的索引不是当前轮次的起始位置 i，则进行交换
            // 这是一个小优化：如果最小值本身就在位置 i，则无需交换
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
            // (可选) 打印每一轮的结果，方便调试和理解
            // System.out.println("第 " + (i + 1) + " 轮排序后: " + Arrays.toString(arr));
        }
    }
}

代码解读

  1. standardSelectSort(int[] arr) 函数： 接受一个整型数组作为参数。
  2. 边界检查： if (arr == null || arr.length < 2) 判断数组是否有效且需要排序。
  3. 外层循环 for (int i = 0; i < arr.length - 1; i++)：
    • 控制排序的轮数，从 0 到 n-2，共 n-1 轮。
    • 变量 i 不仅是轮数计数器，也代表了当前轮次要放置最小值的目标索引，同时也是已排序区间的右边界（不含 i）。
  4. int minIndex = i;：
    • 每一轮开始时，我们假设未排序区间的第一个元素（即 arr[i]）就是最小的，并记录其索引 i 到 minIndex。
  5. 内层循环 for (int j = i + 1; j < arr.length; j++)：
    • 负责在未排序区间 [i+1, n-1] 中进行查找。
    • j 从 i+1 开始，遍历 i 后面的所有元素。
  6. if (arr[j] < arr[minIndex])：
    • 将当前遍历到的元素 arr[j] 与当前记录的最小值 arr[minIndex] 进行比较。
    • 如果 arr[j] 更小，就更新 minIndex 为 j。
  7. if (minIndex != i) 和交换操作：
    • 内层循环结束后，minIndex 就保存了从未排序区间 [i, n-1] 中找到的真正最小值的索引。
    • 如果 minIndex 不等于 i，说明最小值不在当前轮次的目标位置 i，需要将 arr[i] 和 arr[minIndex] 进行交换。使用一个临时变量 temp 完成交换。
    • 如果 minIndex == i，说明 arr[i] 本身就是这一段的最小值，无需进行交换操作，这是一个小优化。

算法特性分析

  • 时间复杂度：
    • 选择排序包含两层嵌套循环。外层循环执行 n-1 次。内层循环的执行次数从 n-1 次（第一轮）递减到 1 次（最后一轮）。
    • 比较操作的总次数约为 (n-1) + (n-2) + ... + 1 = n*(n-1)/2，即 O(n²)。
    • 交换操作最多发生 n-1 次（外层循环每次最多交换一次）。
    • 因此，无论输入数组的初始顺序如何（最好、最坏、平均情况），选择排序的时间复杂度都是 O(n²)。
  • 空间复杂度：
    • 选择排序是原地排序 (in-place) 算法。它只需要常量级别的额外空间来存储 minIndex 和 temp 变量。
    • 空间复杂度为 O(1)。
  • 稳定性：
    • 选择排序是不稳定 (unstable) 的排序算法。
    • 稳定性指：如果数组中有两个相等的元素，排序后它们的相对顺序保持不变。
    • 在选择排序中，考虑数组 [5a, 8, 5b]（5a 和 5b 值相等，但我们用 a/b 区分它们）。
      • 第一轮，找到最小值 5a，它已经在位置 0，不交换。数组 [5a, 8, 5b]。
      • 第二轮，从未排序的 [8, 5b] 中找最小值，是 5b。将 5b 与位置 1 的 8 交换。数组变为 [5a, 5b, 8]。
    • 可以看到，原本 5a 在 5b 前面，排序后 5a 仍然在 5b 前面。这个例子没问题。
    • 再看 [5a, 5b, 3]：
      • 第一轮，找到最小值 3。将 3 与 5a 交换。数组变为 [3, 5b, 5a]。
    • 此时，5b 跑到了 5a 的前面，它们的相对顺序改变了。因此，选择排序是不稳定的。

优缺点与适用场景

  • 优点：
    • 实现简单， 逻辑直观易懂。
    • 移动次数少： 对于需要排序的数据，交换（移动）操作的次数是确定的，最多为 n-1 次。如果数据移动成本远高于比较成本，选择排序可能优于某些交换次数更多的算法（如冒泡排序）。
  • 缺点：
    • 时间复杂度高： O(n²) 的时间复杂度使其在处理大规模数据时效率低下。
    • 不稳定。
  • 适用场景：
    • 数据量较小的排序。
    • 教学或理解排序算法原理。
    • 当数据移动成本非常高昂时可以考虑（虽然 O(n²) 的比较次数通常是更大的瓶颈）。

总结

选择排序是一种基础的排序算法，通过每轮选择未排序部分的最小值并放到正确位置来实现排序。它的 Java 实现直观，空间复杂度为 O(1)，但时间复杂度为 O(n²)，且不稳定。

希望通过本文，你对选择排序有了更清晰的认识。这是我们排序算法系列的第一篇，接下来我们会继续探讨其他排序算法，如冒泡排序、插入排序、归并排序、快速排序等。

如果你觉得这篇文章对你有帮助，欢迎点赞、评论、收藏和关注！你的支持是我持续创作的最大动力！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布