冒泡排序算法

原理

图

算法步骤

• 原则：邻居俩俩比，大的往后换。
  • 要进行n-1回合
  • 每【回合】 进行 (n-回合)[次]比较

• 例：源数据 [3, 7, 2, 1]，n为4（元素数量），加粗代表本回合本次比较过后的结果。

• 【第一回合】[n-1次比较]
  • [3, 7, 2, 1]
  • [3,2, 7, 1]
  • [3, 2,1, 7]
• 【第二回合】[n-2次比较]
  • [2, 3, 1, 7]
  • [2,1, 3, 7]
• 【第三回合】[n-3次比较]
  • [1, 2, 3, 7]
• 比较&&交换完毕！最终升序结果为：[1, 2, 3, 7]

实现

#include<iostream>usingnamespacestd;voidbubbleSort(intarr[],intn){// 外层：n-1回合（每回合需要将一个最大的放到正确的位置for(inti=0;i<n-1;i++){//内层：n-1-i次（减i是因为随着回合的增加，排好的数量也在逐渐递增，排好的不用再排所以减去）for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){// 前比后大就需要交换inttempPre=arr[j];arr[j]=arr[j+1]arr[j+1]=tempPre;}}}}intmain(){intarr[]={3,7,2,1};intn=sizeof(arr)/sizeof(arr[0]);bubbleSort(arr,n);for(inti=0;i<n;i++){cout<<arr[i]<<" ";}return0;}

优化

voidbubbleSortBetter(intarr[],intn){for(inti=0;i<n-1;i++){boolswapped=false;// 标记这一轮有没有交换for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){swap(arr[j],arr[j+1]);// C++ 自带交换函数swapped=true;}}if(!swapped)break;// 没交换，已经有序，提前下班}}

应用场景

• 教学场景
• 小数据量/小内存（传感器、单片机
• 数据基本有序了（比如实时接收的数据流，偶尔有一两个错位），冒泡加上“提前结束”的优化后，跑得飞快，几乎扫一遍就完事。
• 不适合的场景：
  • 数据量上到几千几万 → 太慢，用快速排序
  • 数据范围很小且是整数 → 用计数排序，闪电快
  • 对性能有要求 → 用标准库的 sort()，别自己造轮子