冒泡排序--附图解以及代码

冒泡排序Bubble Sort详解1. 什么是冒泡排序冒泡排序是一种基于比较的交换排序算法。它的核心思想是重复遍历待排序序列依次比较相邻的两个元素若顺序错误逆序则交换直到没有逆序对为止。每一轮遍历都会将当前未排序部分中的最大或最小元素“冒泡”到序列的末端如同气泡从水底浮起因此得名。2. 算法步骤以升序为例从数组第一个元素开始依次比较相邻元素arr[i]和arr[i1]。若arr[i] arr[i1]则交换两者位置。继续向后比较直到数组末尾。此时整个序列的最大值已被交换到最后一位。忽略已排好的最后一个元素对剩余的前n-1个元素重复上述过程。每一轮结束后未排序部分的最大值都会“冒泡”到正确位置。重复n-1轮或直到某一轮未发生任何交换排序结束。3. 动态演示4. 算法复杂度与稳定性特性值最好时间复杂度O(n) —— 数组已有序优化版最坏时间复杂度O(n²) —— 数组完全逆序平均时间复杂度O(n²)空间复杂度O(1) —— 原地排序无需额外数组稳定性稳定—— 相等元素的相对顺序不变5. 优缺点优点算法逻辑简单易于理解和实现。稳定排序适合对稳定性有要求的场景。原地排序内存占用极低。经过优化后对近乎有序的数组效率很高O(n)。缺点平均和最坏时间复杂度均为 O(n²)处理大规模数据时效率低下。实际工程中几乎不被采用仅作为教学或小规模数据排序。6. 示例代码#includestdio.h#includestdbool.h// 优化版冒泡排序voidbubbleSort(intarr[],intn){for(inti0;in-1;i){bool flagfalse;for(intj0;jn-1-i;j){if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;flagtrue;}}if(!flag)break;}}intmain(){intarr[]{5,8,6,3,9,2,1,7};intnsizeof(arr)/sizeof(arr[0]);bubbleSort(arr,n);for(inti0;in;i)printf(%d ,arr[i]);// 输出123456789return0;}