淺析冒泡排序算法
冒泡排序（Bubble sort）是最經典的排序算法
一、算法描述
他的排序思想是這樣的，依次比較相鄰的數據，將小數據放在前，大數據放在後；即第一趟先比較第 1 個和第 2 個數，大數在後，小數在前，再比較第 2 個數與第 3 個數，大數在後，小數在前，以此類推第一趟將最大的數 "滾動" 到最後一個位置；第二趟則將次大的數滾動到倒數第二個位置...... 第 n-1(n 爲無序數據的個數) 趟即能完成排序。
例如：我們將 [5 9 3 6 1 4] 這些數字按照從小到大的順序排序。
步驟
兩兩比較相鄰的數字，左邊比右邊大就把這兩個數字進行交換。
- 比如一開始排序的時候我們拿 5 和 9 進行比較，因爲 5 比 9 小所以不做交換。
- 接下來我們對數字 9 和 3 做比較，因爲 9 大於 3 所以我們對他進行交換，變成 [5 3 9 6 1 4]
- 接下來我們對 9 和 6 進行比較，因爲 9 大於 6 所以我們對他進行交換，變成 [5 3 6 9 1 4]
- 接下來我們對 9 和 1 進行比較，因爲 9 大於 1 所以我們對他進行交換，變成 [5 3 6 1 9 4]
- 最後一次我們對剩下的 9 和 4 進行比較，因爲 9 大於 4 所以我們對他進行交換，變成 **[5 3 6 1 4 9] **
這就完成了一趟排序，一趟用就是把當前的最大值放在最後面，我們不能保證前面五位數的順序，但是能保證最大的數一定排在最後。
所以一趟排序我們能把最大數字放在最後。依次我們對前 5 個數字做排序，再對前 4 個數字做排序，一直這樣最後就可以對整個數組進行從小到大的順序排序。
二、算法實現
下面進行代碼：
#include <stdio.h>
void bubble(int arr[], int n){
int i;
int temp;
for (i=0; i<n-1; i++){
if (arr[i] > arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
void bubbleSort(int arr[], int n){
int i;
for (i=n; i>=1; i--){
bubble(arr,i);
}
}
int main(){
int arr[] = {5,9,3,6,1,4};
int i;
bubbleSort(arr,6);
for (i=0; i<6; i++){
printf("%d\n",arr[i]);
}
}輸出：
三、算法分析
平均時間複雜度：O(n2)
空間複雜度：O(1) (用於交換)
穩定性：穩定（在冒泡排序中，遇到相等的值，是不進行交換的，只有遇到不相等的值才進行交換，所以是穩定的排序方式）
四、適用場景
冒泡排序適用於數據量很小的排序場景，因爲冒泡的實現方式較爲簡單。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/pjo2Qj46XGfcFfYp_LV5Pw