?

?冒泡排序(bubble sort)

?

?基本思想

重復(fù)走訪要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序錯(cuò)誤就交換。當(dāng)沒有相鄰元素需要交換時(shí)，說明全部元素已經(jīng)排序完畢。

## 過程模擬：
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

最終得到目標(biāo)序列：1 2 3 4 5

?

代碼過程
雙重循環(huán)

1. 輸入 $n$ 及數(shù)組
2. 外層for循環(huán)（第 $i$ 趟）：執(zhí)行 1 到 $n$ - 1次
3. 內(nèi)層for循環(huán)：執(zhí)行 1 到 $n$ - $i$ 次。
4. if判斷：如果順序錯(cuò)誤就交換（swap函數(shù)）
5. 輸出排序之后的數(shù)組

?

?代碼：
~~~
//使用冒泡排序(buubleSort)實(shí)現(xiàn)將數(shù)組按從小到大的順序排序
#include<iostream>
using namespace std;

//初始化變量及數(shù)組
int n;
int arr[1000];

//定義冒泡排序函數(shù)
void bubbleSort(int arr[],int n){
?? ?//外層循環(huán)執(zhí)行n-1次
?? ?for(int i=1;i<=n-1;i++){
?? ??? ?//內(nèi)層循環(huán)執(zhí)行n-i次
?? ??? ?for(int j=1;j<=n-i;j++){
?? ??? ??? ?如果數(shù)組中前一個(gè)值比后一個(gè)值大，代表順序錯(cuò)誤，swap()函數(shù)進(jìn)行交換
?? ??? ??? ?if(arr[j]>arr[j+1]){
?? ??? ??? ??? ?swap(arr[j],arr[j+1]);
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?//結(jié)束函數(shù)
?? ?return;
}

//主函數(shù)
int main(){
?? ?//輸入數(shù)據(jù)
?? ?cin>>n;
?? ?for(int i=1;i<=n;i++){
?? ??? ?cin>>arr[i];
?? ?}
? ??
?? ?//執(zhí)行調(diào)用冒牌排序函數(shù)
?? ?bubbleSort(arr,n);
? ??
?? ?//輸出排好序后的數(shù)組
?? ?for(int i=1;i<=n;i++){
?? ??? ?cout<<arr[i]<<" ";
?? ?}
? ??
?? ?//結(jié)束程序
?? ?return 0;
}
~~~

?

其它
- 冒泡排序的**平均時(shí)間復(fù)雜度為$O(n^2)$**
- 冒泡排序的**最好情況下時(shí)間復(fù)雜度為$O(n)$**
- 冒泡排序的**最壞情況下時(shí)間復(fù)雜度為$O(n^2)$**
- 冒泡排序的**空間復(fù)雜度為$O(1)$**
- 冒泡排序需使用**關(guān)鍵字比較**進(jìn)行排序，**不占用額外內(nèi)存**
- 冒泡排序是**穩(wěn)定**(排序后2個(gè)相等鍵值得順序和排序之前它們的順序相同)的排序算法

總結(jié)

以上是生活随笔為你收集整理的冒泡排序 BubbleSort的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。