简单排序算法总结：冒泡排序、选择排序与插入排序

1. 引言

排序是计算机科学中最基础且重要的算法类别之一，它将一组数据按照特定顺序（如升序或降序）重新排列。简单排序算法虽然时间复杂度较高，但其思想直观、实现简单，是理解更复杂排序算法（如快速排序、归并排序）的基石。本文将对三种经典的简单排序算法——冒泡排序、选择排序和插入排序——进行总结，分析其原理、步骤、代码实现及性能特点。

2. 冒泡排序 (Bubble Sort)

2.1 算法思想

冒泡排序通过重复遍历待排序序列，依次比较相邻的两个元素，如果它们的顺序错误（例如，前一个大于后一个，而我们希望升序），就交换它们的位置。每一轮遍历都会将当前未排序部分的最大（或最小）元素“冒泡”到其正确位置（序列的末尾）。

2.2 步骤描述

1. 从序列的第一个元素开始，比较相邻的两个元素。
2. 如果顺序不符合要求（例如升序时前一个大于后一个），则交换它们。
3. 对每一对相邻元素重复步骤1-2，直到序列末尾。完成第一轮后，最大（或最小）元素已“沉”到末尾。
4. 对剩余未排序的元素重复上述过程，每次遍历的范围减少一个元素（因为末尾已排序好）。
5. 重复步骤，直到没有任何一对元素需要交换，此时序列排序完成。

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 步骤描述

1. 在未排序序列中找到最小（或最大）元素。
2. 将其与未排序序列的第一个元素交换位置。
3. 此时，该元素已位于其最终排序位置（已排序部分的末尾）。
4. 将序列的边界（已排序部分与未排序部分的分界）向后移动一位。
5. 重复上述过程，直到未排序部分为空。

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 步骤描述

1. 从第二个元素开始（第一个元素视为已排序）。
2. 取出当前元素（称为“键”），在已排序序列中从后向前扫描。
3. 如果已排序序列中的元素大于键，则将该元素向后移动一位。
4. 重复步骤3，直到找到已排序元素小于或等于键的位置。
5. 将键插入到该位置之后。
6. 重复步骤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. 三种算法对比总结

6. 总结与适用场景

冒泡排序、选择排序和插入排序都是基于比较的简单排序算法，时间复杂度为 O(n²)，不适合大规模数据排序。但它们各有特点：

• 冒泡排序：教学意义大于实用价值，有助于理解排序的基本概念。
• 选择排序：交换次数少，当数据移动成本高时有一定优势。
• 插入排序：在实际应用中仍有价值，尤其适用于小规模数据（如 n ≤ 10）或基本有序的数据，也常作为高级排序算法的子过程。

理解这些简单算法是学习更高效排序算法（如快速排序 O(n log n)）的重要基础。在实际开发中，应优先使用语言内置的排序函数（如 Java 的Arrays.sort()），它们通常经过高度优化。