神兽连萌手游果盘版
135.12MB · 2025-12-04
大家好，我是小杨。最近在复习软件设计师考试，翻到“排序算法”这一章时，突然发现很多原本熟悉的算法，名字还记得，但细节却模模糊糊了。
于是，我决定静下心来，把这五种最经典的排序算法——冒泡排序、插入排序、选择排序、归并排序、堆排序——重新梳理一遍。不仅写了 Java 实现，还加了详细注释，并深入思考了它们“名字”的由来。
希望这篇笔记能帮你理清思路，也欢迎收藏、转发，一起温故知新！
在看代码之前，我们先来聊聊一个有趣的问题：这些算法的名字是怎么来的？
理解名字的由来，能让我们更直观地记住它们的“行为特征”。
| 算法 | 名字关键词 | 核心动作 |
|---|---|---|
| 冒泡排序 | 气泡上浮 | 大元素“冒”到末尾 |
| 插入排序 | 插入 | 将元素插入正确位置 |
| 选择排序 | 选择 | 选择最小/最大元素 |
| 归并排序 | 归并（合并） | 合并两个有序数组 |
| 堆排序 | 堆（数据结构） | 利用堆的性质排序 |
重复遍历数组，比较相邻元素，若顺序错误则交换，直到没有需要交换的元素。
public class BubbleSort {
/**
* 冒泡排序主方法
* 原理：重复遍历数组，比较相邻元素，较大者“冒泡”到末尾
*/
public static void bubbleSort(int[] arr) {
int n = arr.length; // 获取数组长度
boolean swapped; // 标志位：记录本轮是否发生交换
// 外层循环：控制排序轮数，共进行 n-1 轮
for (int i = 0; i < n - 1; i++) {
swapped = false; // 每轮开始前重置标志位
// 内层循环：从头到未排序部分的末尾进行比较
// 每轮后，最大值已确定，所以范围是 n-i-1
for (int j = 0; j < n - i - 1; j++) {
// 如果当前元素大于下一个元素，则交换
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1); // 交换相邻元素
swapped = true; // 标记发生了交换
}
}
// 优化：如果某一轮没有发生任何交换，说明数组已经有序，提前结束
if (!swapped) break;
}
}
/**
* 交换数组中两个位置的元素
*/
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, 34, 25, 12, 22, 11, 90};
System.out.println("排序前: " + java.util.Arrays.toString(arr));
bubbleSort(arr);
System.out.println("排序后: " + java.util.Arrays.toString(arr));
}
}
将数组分为“已排序”和“未排序”两部分，逐个将未排序元素插入到已排序部分的正确位置。
public class InsertionSort {
/**
* 插入排序主方法
* 原理：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置
*/
public static void insertionSort(int[] arr) {
// 从第二个元素开始（索引1），因为第一个元素默认为已排序
for (int i = 1; i < arr.length; i++) {
int key = arr[i]; // 当前要插入的元素
int j = i - 1; // 已排序部分的最后一个元素索引
// 在已排序部分从后向前扫描，找到 key 的插入位置
// 条件：j >= 0 且 arr[j] > key，说明需要将 arr[j] 向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 将较大的元素向后移动一位
j--; // 继续向前比较
}
// 找到插入位置，将 key 放入正确位置
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
System.out.println("排序前: " + java.util.Arrays.toString(arr));
insertionSort(arr);
System.out.println("排序后: " + java.util.Arrays.toString(arr));
}
}
在未排序部分中选择最小元素，与未排序部分的第一个元素交换。
public class SelectionSort {
/**
* 选择排序主方法
* 原理：在未排序部分中找到最小元素，与未排序部分的第一个元素交换
*/
public static void selectionSort(int[] arr) {
int n = arr.length;
// 外层循环：控制已排序部分的边界
// i 表示当前未排序部分的起始位置
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; // 更新最小值的索引
}
}
// 将找到的最小值与未排序部分的第一个元素交换
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));
}
}
分治法：先递归分割数组，再合并两个有序子数组。
public class MergeSort {
/**
* 归并排序主方法（递归实现）
* 原理：分治法 —— 分割、递归排序、合并
*/
public static void mergeSort(int[] arr, int left, int right) {
// 递归终止条件：当子数组只有一个或零个元素时停止
if (left < right) {
// 计算中点，避免整数溢出
int mid = left + (right - left) / 2;
// 递归排序左半部分
mergeSort(arr, left, mid);
// 递归排序右半部分
mergeSort(arr, mid + 1, right);
// 将两个已排序的子数组合并成一个有序数组
merge(arr, left, mid, right);
}
}
/**
* 合并两个已排序的子数组
* arr[left..mid] 和 arr[mid+1..right]
*/
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 左子数组长度
int n2 = right - mid; // 右子数组长度
// 创建临时数组存储左右子数组
int[] L = new int[n1];
int[] R = new int[n2];
// 复制数据到临时数组
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left; // k 是原数组的指针
// 合并过程：比较左右数组元素，较小者放入原数组
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++]; // 取左数组元素
} else {
arr[k++] = R[j++]; // 取右数组元素
}
}
// 将剩余元素复制到原数组（如果有的话）
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("排序前: " + java.util.Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后: " + java.util.Arrays.toString(arr));
}
}
public class HeapSort {
/**
* 堆排序主方法
* 原理：构建最大堆，然后逐个将堆顶（最大值）与堆尾交换，并重新堆化
*/
public static void heapSort(int[] arr) {
int n = arr.length;
// 第一步：构建最大堆
// 从最后一个非叶子节点开始，向上调整每个节点
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 第二步：逐个提取堆顶元素
// 将最大值（arr[0]）与当前堆的最后一个元素交换
// 然后对剩余元素重新堆化
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 将最大值移到末尾
heapify(arr, i, 0); // 对前 i 个元素重新堆化，堆大小减1
}
}
/**
* 堆化操作：维护最大堆性质
* 以索引 i 为根的子树进行堆化
*/
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 假设当前节点是最大的
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 如果左子节点存在且大于根节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点存在且大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，则交换并递归堆化受影响的子树
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest); // 递归堆化新的子树
}
}
/**
* 交换数组中两个位置的元素
*/
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 = {12, 11, 13, 5, 6, 7};
System.out.println("排序前: " + java.util.Arrays.toString(arr));
heapSort(arr);
System.out.println("排序后: " + java.util.Arrays.toString(arr));
}
}
| 算法 | 最坏时间 | 平均时间 | 最好时间 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 小数据量，教学演示 | |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 近乎有序，小数据 | |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 内存敏感，小数据 | |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 大数据，稳定排序 | |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 大数据，原地排序 |
System.out.println() 打印中间过程，理解会更深刻。
