冒泡排序(bubble sort)
基本思想
重复走访要排序的元素列，依次比较两个相邻的元素，如果顺序错误就交换。当没有相邻元素需要交换时，说明全部元素已经排序完毕。
## 过程模拟：
2 3 4 1 5（从小到大）
第一趟：2 3 1 4 **5** //找到序列中最大值5
第二趟：2 1 3 **4 5** //找到待排序序列 2 3 1 4 中最大值 4
第三趟：1 2 **3 4 5** //找到待排序序列 2 3 1 中最大值 3
第四趟：**1 2 3 4 5** //找到待排序序列 2 3 中最大值2
最终得到目标序列：1 2 3 4 5
代码过程
双重循环
1. 输入 $n$ 及数组
2. 外层for循环（第 $i$ 趟）：执行 1 到 $n$ - 1次
3. 内层for循环：执行 1 到 $n$ - $i$ 次。
4. if判断：如果顺序错误就交换（swap函数）
5. 输出排序之后的数组
代码：
~~~
//使用冒泡排序(buubleSort)实现将数组按从小到大的顺序排序
#include<iostream>
using namespace std;
//初始化变量及数组
int n;
int arr[1000];
//定义冒泡排序函数
void bubbleSort(int arr[],int n){
//外层循环执行n-1次
for(int i=1;i<=n-1;i++){
//内层循环执行n-i次
for(int j=1;j<=n-i;j++){
如果数组中前一个值比后一个值大，代表顺序错误，swap()函数进行交换
if(arr[j]>arr[j+1]){
swap(arr[j],arr[j+1]);
}
}
}
//结束函数
return;
}
//主函数
int main(){
//输入数据
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
//执行调用冒牌排序函数
bubbleSort(arr,n);
//输出排好序后的数组
for(int i=1;i<=n;i++){
cout<<arr[i]<<" ";
}
//结束程序
return 0;
}
~~~
其它
- 冒泡排序的**平均时间复杂度为$O(n^2)$**
- 冒泡排序的**最好情况下时间复杂度为$O(n)$**
- 冒泡排序的**最坏情况下时间复杂度为$O(n^2)$**
- 冒泡排序的**空间复杂度为$O(1)$**
- 冒泡排序需使用**关键字比较**进行排序，**不占用额外内存**
- 冒泡排序是**稳定**(排序后2个相等键值得顺序和排序之前它们的顺序相同)的排序算法
