目录
总结：Java 排序算法进阶路线
O(n²) 算法（适合学习原理）
冒泡排序（最慢）→ 选择排序 → 插入排序（推荐先学）
O(n log n) 算法（实际应用）
归并排序（稳定）→ 快速排序（最快，但不稳定）→ 堆排序（空间省）
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、执行流程
如下图所示：
- 在数组
[0...n-1]中找到最小元素，与第 0 个元素交换。 - 在
[1...n-1]中找到最小元素，与第 1 个元素交换。 - 在
[2...n-1]中找到最小元素，与第 2 个元素交换。 - … 重复直到整个数组有序。
每一轮确定一个位置的最终值。
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 次），适合写操作代价高的场景（如写入闪存）。
参考文章：