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

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[j1] 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; // 在 i1 到 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()它们通常经过高度优化。