【数据结构与算法】第32篇：交换排序（一）：冒泡排序

一、冒泡排序的基本思想1.1 算法原理重复遍历数组每次比较相邻两个元素如果顺序错误就交换。每一趟遍历都会把当前未排序部分的最大元素“冒泡”到最后。步骤比较相邻元素如果前一个比后一个大交换对每一对相邻元素重复比较每趟结束后最后一个元素就是当前最大值重复以上步骤直到没有需要交换的元素1.2 图解示例初始[5, 1, 4, 2, 8]text第1趟 比较5和1 → 交换 → [1, 5, 4, 2, 8] 比较5和4 → 交换 → [1, 4, 5, 2, 8] 比较5和2 → 交换 → [1, 4, 2, 5, 8] 比较5和8 → 不交换 → [1, 4, 2, 5, 8] 第1趟结束最大值8已在末尾 第2趟 比较1和4 → 不交换 → [1, 4, 2, 5, 8] 比较4和2 → 交换 → [1, 2, 4, 5, 8] 比较4和5 → 不交换 第2趟结束 第3趟 比较1和2 → 不交换 比较2和4 → 不交换 无交换排序完成二、基础实现c#include stdio.h void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { // 交换 int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 1, 4, 2, 8}; int n sizeof(arr) / sizeof(arr[0]); printf(原数组: ); printArray(arr, n); bubbleSort(arr, n); printf(排序后: ); printArray(arr, n); return 0; }运行结果text原数组: 5 1 4 2 8 排序后: 1 2 4 5 8三、优化一提前终止3.1 优化思路如果某一趟遍历中没有发生任何交换说明数组已经有序可以提前结束排序。3.2 代码实现cvoid bubbleSortOptimized1(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; // 标记是否发生交换 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } // 如果没有交换说明已有序 if (swapped 0) { printf(第%d趟无交换提前结束\n, i 1); break; } printf(第%d趟结束\n, i 1); } }四、优化二记录最后交换位置4.1 优化思路每趟遍历中最后一次发生交换的位置之后的所有元素都已经有序。下一趟只需比较到这个位置即可。4.2 代码实现cvoid bubbleSortOptimized2(int arr[], int n) { int lastSwap n - 1; // 最后交换位置 for (int i 0; i n - 1; i) { int swapped 0; int newLastSwap 0; for (int j 0; j lastSwap; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; newLastSwap j; // 记录最后交换位置 } } if (swapped 0) break; lastSwap newLastSwap; // 缩小下一趟范围 printf(第%d趟结束最后交换位置%d\n, i 1, lastSwap); } }五、完整代码含两种优化c#include stdio.h #include stdlib.h #include time.h // 基础冒泡 void bubbleSortBasic(int arr[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } // 优化1提前终止 void bubbleSortOptimized1(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } if (swapped 0) break; } } // 优化2记录最后交换位置 void bubbleSortOptimized2(int arr[], int n) { int lastSwap n - 1; for (int i 0; i n - 1; i) { int swapped 0; int newLastSwap 0; for (int j 0; j lastSwap; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; newLastSwap j; } } if (swapped 0) break; lastSwap newLastSwap; } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } // 复制数组 void copyArray(int src[], int dst[], int n) { for (int i 0; i n; i) { dst[i] src[i]; } } // 生成随机数组 void generateRandomArray(int arr[], int n) { for (int i 0; i n; i) { arr[i] rand() % 1000; } } // 生成近乎有序数组 void generateNearlySortedArray(int arr[], int n) { for (int i 0; i n; i) { arr[i] i; } // 交换少量元素 for (int i 0; i n / 20; i) { int p1 rand() % n; int p2 rand() % n; int temp arr[p1]; arr[p1] arr[p2]; arr[p2] temp; } } int main() { srand(time(NULL)); printf( 冒泡排序优化对比 \n\n); // 测试1随机数组 int n 10000; int *arr1 (int*)malloc(n * sizeof(int)); int *arr2 (int*)malloc(n * sizeof(int)); int *arr3 (int*)malloc(n * sizeof(int)); generateRandomArray(arr1, n); copyArray(arr1, arr2, n); copyArray(arr1, arr3, n); clock_t start, end; double time1, time2, time3; start clock(); bubbleSortBasic(arr1, n); end clock(); time1 (double)(end - start) / CLOCKS_PER_SEC * 1000; start clock(); bubbleSortOptimized1(arr2, n); end clock(); time2 (double)(end - start) / CLOCKS_PER_SEC * 1000; start clock(); bubbleSortOptimized2(arr3, n); end clock(); time3 (double)(end - start) / CLOCKS_PER_SEC * 1000; printf(随机数组 (n%d):\n, n); printf( 基础冒泡: %.2f ms\n, time1); printf( 优化1提前终止: %.2f ms\n, time2); printf( 优化2缩小范围: %.2f ms\n, time3); printf( 优化2 比 基础 快 %.2f 倍\n\n, time1 / time3); // 测试2近乎有序数组 generateNearlySortedArray(arr1, n); copyArray(arr1, arr2, n); copyArray(arr1, arr3, n); start clock(); bubbleSortBasic(arr1, n); end clock(); time1 (double)(end - start) / CLOCKS_PER_SEC * 1000; start clock(); bubbleSortOptimized1(arr2, n); end clock(); time2 (double)(end - start) / CLOCKS_PER_SEC * 1000; start clock(); bubbleSortOptimized2(arr3, n); end clock(); time3 (double)(end - start) / CLOCKS_PER_SEC * 1000; printf(近乎有序数组 (n%d):\n, n); printf( 基础冒泡: %.2f ms\n, time1); printf( 优化1提前终止: %.2f ms\n, time2); printf( 优化2缩小范围: %.2f ms\n, time3); free(arr1); free(arr2); free(arr3); // 测试3演示优化效果 printf(\n 演示优化效果 \n); int demo[] {5, 1, 2, 3, 4}; int m sizeof(demo) / sizeof(demo[0]); printf(原数组: ); printArray(demo, m); // 使用优化2可以看到每趟结束后的状态 int lastSwap m - 1; for (int i 0; i m - 1; i) { int swapped 0; int newLastSwap 0; for (int j 0; j lastSwap; j) { if (demo[j] demo[j 1]) { int temp demo[j]; demo[j] demo[j 1]; demo[j 1] temp; swapped 1; newLastSwap j; } } printf(第%d趟后: , i 1); printArray(demo, m); if (swapped 0) { printf(未发生交换提前结束\n); break; } lastSwap newLastSwap; printf(下一趟只需比较到下标 %d\n, lastSwap); } return 0; }运行结果示例text 冒泡排序优化对比 随机数组 (n10000): 基础冒泡: 385.42 ms 优化1提前终止: 382.15 ms 优化2缩小范围: 368.33 ms 优化2 比 基础 快 1.05 倍 近乎有序数组 (n10000): 基础冒泡: 195.67 ms 优化1提前终止: 0.23 ms 优化2缩小范围: 0.21 ms 演示优化效果 原数组: 5 1 2 3 4 第1趟后: 1 2 3 4 5 下一趟只需比较到下标 3 第2趟后: 1 2 3 4 5 未发生交换提前结束六、复杂度分析情况比较次数交换次数时间复杂度最好已有序n-10O(n)最坏逆序n(n-1)/2n(n-1)/2O(n²)平均n(n-1)/2n(n-1)/4O(n²)空间复杂度O(1)原地排序稳定性稳定相等时不交换七、冒泡排序的特点优点缺点实现简单容易理解时间复杂度高 O(n²)空间复杂度低 O(1)大规模数据效率低稳定排序-可以提前终止在有序时效率高-原地排序不需要额外空间-适用场景数据规模很小n 1000数据基本有序教学演示理解排序思想八、小结这一篇我们学习了冒泡排序及其优化版本优化点效果基础冒泡无始终执行 n-1 趟优化1无交换则提前终止有序时 O(n)优化2记录最后交换位置减少每趟比较范围核心要点每趟把最大元素“冒泡”到末尾优化1某趟无交换 → 已有序优化2最后交换位置之后已有序下一篇我们讲快速排序。九、思考题冒泡排序为什么叫“冒泡”排序这个名字是怎么来的如果数组已经有序优化后的冒泡排序需要比较多少次优化2中为什么newLastSwap j而不是j1冒泡排序和直接插入排序相比哪个在基本有序时效率更高为什么欢迎在评论区讨论你的答案。