第四章：基础算法
4.1 排序算法
4.1.1 冒泡排序（Bubble Sort）
基本概念
冒泡排序是最简单直观的排序算法之一，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们。名字来源于较大的元素会经由交换慢慢"浮"到数列的顶端，就像水中的气泡上升一样。
生活中的例子
想象一下，你有一排不同高度的人，需要按照从矮到高的顺序排列：
- 你从左边开始，比较第1个和第2个人的高度
- 如果第1个人比第2个人高，他们交换位置
- 然后比较第2个和第3个人，如此类推
- 一轮比较后，最高的人会到达最右边
- 重复这个过程，每次排除已经到位的最高者
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换它们。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
图解过程
假设我们有数组：[5, 3, 8, 4, 2]
第一轮遍历：
- 比较5和3：5>3，交换 → [3, 5, 8, 4, 2]
- 比较5和8：5<8，不交换 → [3, 5, 8, 4, 2]
- 比较8和4：8>4，交换 → [3, 5, 4, 8, 2]
- 比较8和2：8>2，交换 → [3, 5, 4, 2, 8]
第一轮结束后，最大的元素8已经到达正确位置。
第二轮遍历：
- 比较3和5：3<5，不交换 → [3, 5, 4, 2, 8]
- 比较5和4：5>4，交换 → [3, 4, 5, 2, 8]
- 比较5和2：5>2，交换 → [3, 4, 2, 5, 8]
以此类推…
代码实现
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
// 每次遍历比较相邻元素
for (int j = 0; j < n - i - 1; 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²) - 当数组完全逆序时
- 最好情况：O(n) - 当数组已经有序时（使用优化版本）
- 平均情况：O(n²)
空间复杂度：O(1) - 只需要一个临时变量用于交换
稳定性：稳定 - 相等元素的相对位置不会改变
适用场景
- 数据量小的情况
- 数据几乎已经排好序的情况
- 作为教学或入门算法
4.1.2 选择排序（Selection Sort）
基本概念
选择排序是一种简单直观的排序算法。它的工作原理是每次从待排序数据中选出最小（或最大）的一个元素，放在已排序序列的末尾。与冒泡排序不同，选择排序每轮只进行一次交换，减少了交换操作的次数。
生活中的例子
想象你在整理一副扑克牌：
- 你从左边开始，找出剩余牌中最小的一张
- 将这张牌与最左边的牌交换位置
- 然后在剩余的牌中继续寻找最小的牌
- 重复这个过程，直到所有牌都排好序
这就像是你在选择商品时，每次都挑选价格最低的那个放入购物车的最前面。
算法步骤
- 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
图解过程
假设我们有数组：[64, 25, 12, 22, 11]
第一轮：
- 找出最小元素11
- 将11与第一个元素64交换 → [11, 25, 12, 22, 64]
第二轮：
- 在剩余元素[25, 12, 22, 64]中找出最小元素12
- 将12与第二个元素25交换 → [11, 12, 25, 22, 64]
第三轮：
- 在剩余元素[25, 22, 64]中找出最小元素22
- 将22与第三个元素25交换 → [11, 12, 22, 25, 64]
第四轮：
- 在剩余元素[25, 64]中找出最小元素25
- 25已经在正确位置，不需要交换 → [11, 12, 22, 25, 64]
排序完成！
代码实现
public static void selectionSort(int[] arr) {
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;
}
}
}
性能分析
时间复杂度：
- 最坏情况：O(n²)
- 最好情况：O(n²) - 即使数组已经排序，仍需要遍历整个数组
- 平均情况：O(n²)
空间复杂度：O(1) - 只需要一个临时变量用于交换
稳定性：不稳定 - 可能改变相等元素的相对位置
例如：[5, 5*, 2] → [2, 5*, 5]，原本在前面的5*被交换到后面去了
适用场景
- 数据量较小的情况
- 对交换操作成本较高的情况（因为选择排序交换次数少）
- 对内存空间要求严格的情况（因为只需要常数级额外空间）
- 当查找最小值或最大值是主要操作时
4.1.3 插入排序（Insertion Sort）
基本概念
插入排序是一种简单直观的排序算法，它的工作原理类似于我们玩扑克牌时的整理牌方式。对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序对于小规模数据或基本有序的数据效率较高。
生活中的例子
想象你正在打扑克牌：
- 开始时，你手里只有一张牌，这张牌自然是有序的
- 每次从牌堆抽一张新牌，将其与手中已有的牌从右向左比较
- 找到新牌应该放置的位置，将其插入
- 重复这个过程，直到所有牌都排好序
这就像是图书管理员在整理书架时，拿起一本新书，找到它应该在的位置，然后插入进去。
算法步骤
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5，直到所有元素排序完成。
图解过程
假设我们有数组：[12, 11, 13, 5, 6]
初始状态：
- 认为第一个元素12已经排序 → [12 | 11, 13, 5, 6]
第一次插入：
- 取出11，与已排序元素12比较
- 12 > 11，将12后移
- 插入11 → [11, 12 | 13, 5, 6]
第二次插入：
- 取出13，与已排序元素12比较
- 12 < 13，13已在正确位置
- 保持不变 → [11, 12, 13 | 5, 6]
第三次插入：
- 取出5，与已排序元素13, 12, 11依次比较
- 13 > 5，将13后移
- 12 > 5，将12后移
- 11 > 5，将11后移
- 插入5 → [5, 11, 12, 13 | 6]
第四次插入：
- 取出6，与已排序元素13, 12, 11, 5依次比较
- 13 > 6，将13后移
- 12 > 6，将12后移
- 11 > 6，将11后移
- 5 < 6，插入6 → [5, 6, 11, 12, 13]
排序完成！
代码实现
public static void insertionSort(int[] arr) {
int n = arr.length;
// 从第二个元素开始，第一个元素视为已排序
for (int i = 1; i < n; i++) {
// 保存当前要插入的元素
int key = arr[i];
int j = i - 1;
// 将比key大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// 在正确位置插入key
arr[j + 1] = key;
}
}
性能分析
时间复杂度：
- 最坏情况：O(n²) - 当数组完全逆序时
- 最好情况：O(n) - 当数组已经有序时
- 平均情况：O(n²)
空间复杂度：O(1) - 只需要一个临时变量用于存储当前插入的元素
稳定性：稳定 - 相等元素的相对位置不会改变
适用场景
- 数据量较小的情况
- 数据几乎已经排好序的情况（此时接近O(n)的性能）
- 对稳定性有要求的场景
- 在线算法（数据边输入边排序）
- 作为更复杂排序算法的子过程