冒泡排序（Bubble Sort）详解
冒泡排序是一种基础的交换排序算法，核心思想是：重复遍历待排序数组，每次比较相邻的两个元素，若顺序错误则交换它们，直到没有元素需要交换为止。
资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf
核心特点
- 稳定性：稳定（相等元素的相对位置不变）
- 时间复杂度：
- 最好情况（已排序）：O(n)（需优化标志位）
- 最坏情况（逆序）：O(n²)
- 平均情况：O(n²)
- 空间复杂度：O(1)（原地排序）
- 适用场景：小规模数据、对稳定性有要求的简单场景
算法原理
- 从数组第一个元素开始，依次比较相邻的两个元素（如
arr[i]和arr[i+1]）； - 若
arr[i] > arr[i+1]（升序），则交换两者位置； - 一轮遍历结束后，最大的元素会“冒泡”到数组末尾；
- 重复上述过程，每轮遍历的终点向前收缩一位（已排序的末尾元素无需再比较）；
- 若某一轮遍历中没有发生任何交换，说明数组已完全有序，可提前终止（优化）。
代码实现（Python）
defbubble_sort(arr):# 复制数组避免修改原数据arr_copy=arr.copy()n=len(arr_copy)# 外层循环：控制遍历轮数（最多n-1轮）foriinrange(n-1):# 标志位：标记本轮是否发生交换（优化）swapped=False# 内层循环：每轮比较到未排序的最后一位（n-1-i）forjinrange(n-1-i):# 升序：前一个元素大于后一个则交换ifarr_copy[j]>arr_copy[j+1]:arr_copy[j],arr_copy[j+1]=arr_copy[j+1],arr_copy[j]swapped=True# 若本轮无交换，说明数组已有序，提前退出ifnotswapped:breakreturnarr_copy# 测试示例if__name__=="__main__":# 无序数组unsorted_arr=[64,34,25,12,22,11,90]sorted_arr=bubble_sort(unsorted_arr)print("原始数组：",unsorted_arr)print("排序后数组：",sorted_arr)# 输出：[11, 12, 22, 25, 34, 64, 90]# 已排序数组（验证优化）sorted_test=[1,2,3,4,5]print(bubble_sort(sorted_test))# 仅1轮遍历即退出代码实现（Java）
publicclassBubbleSort{publicstaticint[]bubbleSort(int[]arr){// 复制数组避免修改原数据int[]arrCopy=Arrays.copyOf(arr,arr.length);intn=arrCopy.length;for(inti=0;i<n-1;i++){booleanswapped=false;// 交换标志位// 内层循环：每轮减少i次比较（末尾i个已排序）for(intj=0;j<n-1-i;j++){if(arrCopy[j]>arrCopy[j+1]){// 交换元素inttemp=arrCopy[j];arrCopy[j]=arrCopy[j+1];arrCopy[j+1]=temp;swapped=true;}}// 无交换则提前终止if(!swapped){break;}}returnarrCopy;}publicstaticvoidmain(String[]args){int[]unsortedArr={64,34,25,12,22,11,90};int[]sortedArr=bubbleSort(unsortedArr);System.out.print("原始数组：");for(intnum:unsortedArr)System.out.print(num+" ");System.out.print("\n排序后数组：");for(intnum:sortedArr)System.out.print(num+" ");}}关键优化点
- 提前终止：通过
swapped标志位，若某轮无交换则直接退出，避免无效遍历； - 收缩遍历范围：每轮遍历的终点为
n-1-i，因为后i个元素已排序完成； - 双向冒泡（鸡尾酒排序）：针对“部分有序”的数组（如
[1,3,2,4,5]），可从左到右、再从右到左交替遍历，减少遍历次数。
适用场景
- 数据量小（n < 1000），对性能要求不高；
- 需保证排序稳定性；
- 教学场景（易理解、易实现）。
不适用场景：大数据量（如n > 10000），此时应选择快速排序、归并排序等O(n log n)的算法。
