企业官网建设流程全解析

冒泡排序（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)（原地排序）
• 适用场景：小规模数据、对稳定性有要求的简单场景

算法原理

1. 从数组第一个元素开始，依次比较相邻的两个元素（如arr[i]和arr[i+1]）；
2. 若arr[i] > arr[i+1]（升序），则交换两者位置；
3. 一轮遍历结束后，最大的元素会“冒泡”到数组末尾；
4. 重复上述过程，每轮遍历的终点向前收缩一位（已排序的末尾元素无需再比较）；
5. 若某一轮遍历中没有发生任何交换，说明数组已完全有序，可提前终止（优化）。

代码实现（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+" ");}}

关键优化点

1. 提前终止：通过swapped标志位，若某轮无交换则直接退出，避免无效遍历；
2. 收缩遍历范围：每轮遍历的终点为n-1-i，因为后i个元素已排序完成；
3. 双向冒泡（鸡尾酒排序）：针对“部分有序”的数组（如[1,3,2,4,5]），可从左到右、再从右到左交替遍历，减少遍历次数。

适用场景

• 数据量小（n < 1000），对性能要求不高；
• 需保证排序稳定性；
• 教学场景（易理解、易实现）。

不适用场景：大数据量（如n > 10000），此时应选择快速排序、归并排序等O(n log n)的算法。