当前位置：首页 > news >正文

排序算法：冒泡排序

news 2026/6/30 16:31:30

冒泡排序（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+" ");}}