[排序介紹] 氣泡排序 Bubble Sort

氣泡排序法（Bubble Sort）好像是大部分人會接觸的第一個排序法？名字也相當可愛，顧名思義數字會像泡泡一樣滾來滾去最終慢慢浮出水面。

想法

基本概念就是重複來回跑要排序的數列，從頭開始，過程中一次比較兩個元素，如果順序錯了，兩個就互換。一直重複這個操作，直到不需要交換任何元素，表示排序完成。

從上面的敘述就可以知道概念上很簡單，時間執行上會很可怕XD

Best
空間複雜度：\(O(1)\)
時間複雜度：\(O(n)\)

Average
空間複雜度：\(O(1)\)
時間複雜度：\(O(n^2)\)

Worst
空間複雜度：\(O(1)\)
時間複雜度：\(O(n^2)\)

實際操作

突然發現寫起來有點麻煩XDD 從頭開始，要排序的數列是 array = [5, 8, 2, 9, 5, 6, 3]。

isSorted 預設為 true，若數列有變動過順序則值就會轉變為 false，沒有被變動過表示已經沒有元素互相比較了，也就是說已經排序完成。

i = 0
array[0] < array[1]，不用動，i 移往下一個元素。
array = [5, 8, 2, 9, 5, 6, 3]

i = 1
array[1] > array[2]，array[0] 和 array[1] 互相交換。因為動過了，isSorted 改為 false。
array = [5, 2, 8, 9, 5, 6, 3]

i = 2
array[2] < array[3]，不用動，i 移往下一個元素。
array = [5, 2, 8, 9, 5, 6, 3]

i = 3
array[3] > array[4]，array[3] 和 array[4] 互相交換。
array = [5, 2, 8, 5, 9, 6, 3]

i = 4
array[4] > array[5]，array[4] 和 array[5] 互相交換。
array = [5, 2, 8, 5, 6, 9, 3]

i = 5
array[5] > array[6]，array[5] 和 array[6] 互相交換。
array = [5, 2, 8, 5, 6, 3, 9]

OK，已經跑過一輪後，因為 isSorted 是 false，所以我們要再重複上述步驟一遍又一遍，直到 isSorted 的值為 true。

#include <vector>
using namespace std;

vector<int> bubbleSort(vector<int> array) {
  bool isSorted = false;

  while (!isSorted){
    isSorted = true;
    for (int i = 0; i < array.size() - 1; i++){
      if (array[i] > array[i + 1]){
        swap(array[i], array[i + 1]);
        isSorted = false;
      }
    }
  }
  return array;
}