目录

1、选择排序

1.1、介绍

1.2、稳定性

2、执行流程

3、java实现

4、优缺点

---

总结：Java 排序算法进阶路线

1. O(n²) 算法（适合学习原理）

   • 冒泡排序（最慢）→ 选择排序 → 插入排序（推荐先学）

2. O(n log n) 算法（实际应用）

   • 归并排序（稳定）→ 快速排序（最快，但不稳定）→ 堆排序（空间省）

3. Java 内置排序

   • Arrays.sort()：对基本类型用 快速排序，对象类型用 归并排序（保证稳定性）。

---

1、选择排序

1.1、介绍

（Selection Sort）—— 比冒泡“聪明”一点。

每一次从未排序的数据中选出最小（或最大）的元素，放到已排序序列的末尾。

就像你有一堆乱序的书，每次从中挑出最薄的一本，放到书架上，直到所有书排好序。

1.2、稳定性

稳定排序要求：所有值相同的元素，排序后必须保持它们在原数组中的先后顺序。

有这样一个数组（用 A、B 标记两个相同的 5，以便追踪它们的位置）：

原始数组：[5A, 2, 3, 5B, 1]

目标是用 选择排序 把它从小到大排序。

我们要关注的是：排序后，5A 和 5B 的相对顺序是否保持不变？

如果保持 5A 在 5B 前面 → 稳定 ✅
如果变成 5B 在 5A 前面 → 不稳定 ❌

选择排序的执行过程（逐轮分析）

✅第 0 轮：在 [5A, 2, 3, 5B, 1] 中找最小值

• 从索引 0 到 4 遍历，找出最小值是 1，它在索引 4。
• 把 1 和 5A（索引 0）交换：

交换前：[5A, 2, 3, 5B, 1]
交换后：[1, 2, 3, 5B, 5A]

关键来了：

• 原来的 5A 被换到了最后（索引 4）
• 原来的 5B 还在原地（索引 3）
  👉 所以现在：5B 在索引 3，5A 在索引 4 → 5B 在 5A 前面！

虽然它们的值都是 5，但 原来 5A 在前，现在 5B 在前，相对顺序被改变了。

总结

冒泡排序是稳定的，（因为只在 > 时才交换，== 不动）。

❌ 选择排序是不稳定的！

---

2、执行流程

如下图所示：

1. 在数组 [0...n-1] 中找到最小元素，与第 0 个元素交换。
2. 在 [1...n-1] 中找到最小元素，与第 1 个元素交换。
3. 在 [2...n-1] 中找到最小元素，与第 2 个元素交换。
4. … 重复直到整个数组有序。

每一轮确定一个位置的最终值。

---

3、java实现

public class SelectionSort {/*** 选择排序：升序* @param arr 待排序的整型数组*/public static void selectionSort(int[] arr) {// 边界判断if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 外层循环：控制排序的位置（0 ~ n-2）for (int i = 0; i < n - 1; i++) {int minIndex = i; // 假设当前位置就是最小值的索引// 内层循环：在未排序部分 [i+1, n-1] 中找真正的最小值for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 更新最小值的索引}}// 将找到的最小值与位置 i 的元素交换if (minIndex != i) {swap(arr, i, minIndex);}}}/*** 交换数组中两个元素*/private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 测试方法public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11, 90};System.out.println("排序前：" + java.util.Arrays.toString(arr));selectionSort(arr);System.out.println("排序后：" + java.util.Arrays.toString(arr));}
}

输出结果：

排序前：[64, 25, 12, 22, 11, 90]
排序后：[11, 12, 22, 25, 64, 90]

---

4、优缺点

🔍 和冒泡的区别：

• 冒泡：不断交换，把最大值“冒”到最后。
• 选择：每轮只记录最小值的下标，最后只交换一次。

✅ 优点：

• 交换次数少（最多 n-1 次），适合写操作代价高的场景（如写入闪存）。

---

参考文章：

1、六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序-CSDN博客文章浏览阅读10w+次，点赞6.3k次，收藏3.4w次。本文详细介绍了排序算法中的插入排序、希尔排序、选择排序、冒泡排序、堆排序以及两种快速排序方法（Hoare版本和挖坑法）。通过动图演示和代码实现，展示了这些算法的工作原理和时间复杂度，帮助读者深入理解排序算法的内部机制。https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc=%257B%2522request%255Fid%2522%253A%25220faf03d22b2d125d5f49a4649ad59c85%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=0faf03d22b2d125d5f49a4649ad59c85&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v102^control&utm_term=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187