简单排序算法总结：冒泡排序、选择排序与插入排序
1. 引言
排序是计算机科学中最基础且重要的算法类别之一，它将一组数据按照特定顺序（如升序或降序）重新排列。简单排序算法虽然时间复杂度较高，但其思想直观、实现简单，是理解更复杂排序算法（如快速排序、归并排序）的基石。本文将对三种经典的简单排序算法——冒泡排序、选择排序和插入排序——进行总结，分析其原理、步骤、代码实现及性能特点。
2. 冒泡排序 (Bubble Sort)
2.1 算法思想
冒泡排序通过重复遍历待排序序列，依次比较相邻的两个元素，如果它们的顺序错误（例如，前一个大于后一个，而我们希望升序），就交换它们的位置。每一轮遍历都会将当前未排序部分的最大（或最小）元素“冒泡”到其正确位置（序列的末尾）。
2.2 步骤描述
- 从序列的第一个元素开始，比较相邻的两个元素。
- 如果顺序不符合要求（例如升序时前一个大于后一个），则交换它们。
- 对每一对相邻元素重复步骤1-2，直到序列末尾。完成第一轮后，最大（或最小）元素已“沉”到末尾。
- 对剩余未排序的元素重复上述过程，每次遍历的范围减少一个元素（因为末尾已排序好）。
- 重复步骤，直到没有任何一对元素需要交换，此时序列排序完成。
2.3 代码示例 (Java)
public class BubbleSort { 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 - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 交换 arr[j] 和 arr[j+1] int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } // 如果本轮没有发生交换，说明数组已经有序，提前结束 if (!swapped) { break; } } } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(arr); System.out.println("排序后的数组:"); for (int num : arr) { System.out.print(num + " "); } } }2.4 性能分析
- 时间复杂度：
- 最坏情况（逆序）：O(n²)
- 平均情况：O(n²)
- 最好情况（已有序，且使用优化标志）：O(n)
- 空间复杂度：O(1)，原地排序。
- 稳定性：稳定（相等元素不会交换）。
3. 选择排序 (Selection Sort)
3.1 算法思想
选择排序将序列分为已排序和未排序两部分。每次从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，从而将其加入到已排序部分的末尾。如此反复，直到所有元素排序完毕。
3.2 步骤描述
- 在未排序序列中找到最小（或最大）元素。
- 将其与未排序序列的第一个元素交换位置。
- 此时，该元素已位于其最终排序位置（已排序部分的末尾）。
- 将序列的边界（已排序部分与未排序部分的分界）向后移动一位。
- 重复上述过程，直到未排序部分为空。
3.3 代码示例 (Java)
public class SelectionSort { public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { // 假设当前索引 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) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } public static void main(String[] args) { int[] arr = {64, 25, 12, 22, 11}; selectionSort(arr); System.out.println("排序后的数组:"); for (int num : arr) { System.out.print(num + " "); } } }3.4 性能分析
- 时间复杂度：无论数据初始状态如何，都需要进行 O(n²) 次比较，因此最好、最坏、平均时间复杂度均为 O(n²)。
- 空间复杂度：O(1)，原地排序。
- 稳定性：不稳定（例如序列 [5a, 8, 5b, 2, 9]，第一次选择最小元素2与5a交换后，5a和5b的相对顺序改变了）。
4. 插入排序 (Insertion Sort)
4.1 算法思想
插入排序的工作方式类似于整理手中的扑克牌。它将序列视为已排序和未排序两部分，初始时已排序部分只包含第一个元素。然后依次将未排序部分的每个元素插入到已排序部分的适当位置，直到所有元素都插入完毕。
4.2 步骤描述
- 从第二个元素开始（第一个元素视为已排序）。
- 取出当前元素（称为“键”），在已排序序列中从后向前扫描。
- 如果已排序序列中的元素大于键，则将该元素向后移动一位。
- 重复步骤3，直到找到已排序元素小于或等于键的位置。
- 将键插入到该位置之后。
- 重复步骤2-5，直到所有元素处理完毕。
4.3 代码示例 (Java)
public class InsertionSort { 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--; } // 插入 key 到正确位置 arr[j + 1] = key; } } public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6}; insertionSort(arr); System.out.println("排序后的数组:"); for (int num : arr) { System.out.print(num + " "); } } }4.4 性能分析
- 时间复杂度：
- 最坏情况（逆序）：O(n²)
- 平均情况：O(n²)
- 最好情况（已有序）：O(n)
- 空间复杂度：O(1)，原地排序。
- 稳定性：稳定（只有当前元素小于已排序元素时才移动，等于时不移动）。
- 特点：对于小规模或基本有序的数据集，插入排序效率很高，常作为高级排序算法（如快速排序、归并排序）在小规模子问题上的优化手段。
5. 三种算法对比总结
| 算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 主要特点 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) (优化后) | O(n²) | O(1) | 稳定 | 思想简单，效率低，可通过标志位优化 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 交换次数少（最多 n-1 次），但比较次数固定 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 对小规模或基本有序数据高效，适合增量排序 |
6. 总结与适用场景
冒泡排序、选择排序和插入排序都是基于比较的简单排序算法，时间复杂度为 O(n²)，不适合大规模数据排序。但它们各有特点：
- 冒泡排序：教学意义大于实用价值，有助于理解排序的基本概念。
- 选择排序：交换次数少，当数据移动成本高时有一定优势。
- 插入排序：在实际应用中仍有价值，尤其适用于小规模数据（如 n ≤ 10）或基本有序的数据，也常作为高级排序算法的子过程。
理解这些简单算法是学习更高效排序算法（如快速排序 O(n log n)）的重要基础。在实际开发中，应优先使用语言内置的排序函数（如 Java 的Arrays.sort()），它们通常经过高度优化。