排序系列
前言
大家好，我是老马。
以前从工程的角度，已经梳理过一次排序算法。
这里从力扣算法的角度，重新梳理一遍。
核心内容包含：
1）常见排序算法介绍
2）背后的核心思想
3）leetcode 经典题目练习+讲解
4）应用场景、优缺点等对比总结
5）工程 sdk 包，这个已经完成。
6) 可视化
冒泡排序
🫧 一、什么是冒泡排序？
冒泡排序是一种简单直观的比较排序算法。它的名字来源于“大的元素像气泡一样逐渐浮到顶部”的过程。
🔧 二、算法原理（核心思想）
冒泡排序通过反复遍历待排序的序列，每次比较相邻的两个元素，如果顺序错误就交换，直到没有元素需要交换为止。
举例：
排序 [5, 2, 4, 3]：
- 第1轮：
[2, 4, 3, 5]（5浮到最后） - 第2轮：
[2, 3, 4, 5] - 第3轮：有序，无需再动
🧠 三、代码逻辑
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 优化点：如果一轮无交换说明已有序
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
- 外层循环控制“轮次”
- 内层循环执行“冒泡”：大的向后交换
📈 四、复杂度分析
| 情况 | 比较次数 | 交换次数 | 时间复杂度 |
|---|---|---|---|
| 最好 | O(n) | 0 | ✅ O(n)（优化后） |
| 最坏 | O(n²) | O(n²) | ❌ O(n²) |
| 平均 | O(n²) | O(n²) | ❌ O(n²) |
| 空间复杂度 | O(1)（原地排序） |
🏷️ 五、特点总结
| 特性 | 是否说明 |
|---|---|
| 原地排序 | ✅ 是 |
| 稳定排序 | ✅ 是（不打乱相等元素顺序） |
| 递归实现 | 🚫 一般不用 |
| 实现难度 | ⭐ 非常简单 |
✅ 六、冒泡排序的优点 & 缺点
| 优点 | 缺点 |
|---|---|
| 实现简单，容易理解 | 效率太低，不适合大数据量 |
| 稳定排序 | 频繁交换导致性能差 |
| 有“优化空间”（加标志位提前退出） | 时间复杂度最坏仍是 O(n²) |
🧠 七、优化版冒泡排序
-
优化 1：加布尔变量
swapped- 如果某一轮没有交换，说明已排好序，可以提前退出。
-
优化 2：记录最后一次交换的位置
- 可以减少下一轮的比较范围（略复杂）
✅ 八、冒泡排序适合的场景
| 场景 | 说明 |
|---|---|
| ✅ 数据量小 | 比如数组长度 <= 100 的排序问题，冒泡的性能勉强可接受。 |
| ✅ 部分有序的数据 | 如果数据接近有序，冒泡排序（带优化）能在 O(n) 内完成排序。 |
| ✅ 对稳定性有要求的简单排序 | 冒泡排序是稳定排序，适合处理相同元素保持相对位置的问题。 |
| ✅ 教学演示、入门练习 | 冒泡排序的逻辑简单，非常适合用来练习排序、数组操作、交换等基础技巧。 |
| ✅ 需要原地排序（O(1)空间） | 冒泡排序是原地排序，无需额外内存。 |
力扣上冒泡排序的经典题目
冒泡排序虽然在实际应用中不常用于大规模数据处理，但它在某些场景下仍然有价值，特别是：
虽然力扣大部分题目需要更高效的排序（如快速排序、库函数），但以下这些题目可以通过冒泡排序解决或辅助理解：
🔹 1. LeetCode 912. 排序数组
- 题目描述：给你一个整数数组，请将数组升序排序。
- ✅ 可以用冒泡排序实现（虽不高效），适合练习。
- 🔧 但面试中推荐用快排、归并、堆排等。
🔹 2. LeetCode 283. 移动零
- 题目描述：将所有 0 移动到数组末尾，同时保持非零元素的相对顺序。
- ✅ 冒泡思想变形：让 0 不断往后“冒泡”，保持相对顺序 ✅ 稳定性。
- 可以不用真的排序，但冒泡的思想很好用。
🔹 3. LeetCode 75. 颜色分类（荷兰国旗问题）
- 题目描述：只包含 0、1、2 的数组，按颜色顺序排序。
- ✅ 可用冒泡或选择排序变形实现。
- 面试推荐使用双指针更优方式，但冒泡版可以作为思维训练。
🔹 4. LeetCode 1470. 重新排列数组
- 尽管不是排序题，但涉及到数组变换，可以借助冒泡排序巩固交换思维。
