Day 25 : 经典气泡排序 Bubble Sort

接下来的五天我们会用不同的方式来解这题题目Sort an Array，一起来复习跟朝拜大师们想出来的排序法！
从前面开始有关input给了一个array的题目时，我们就很常看到sort，所以我们当然不能忽略sort的重要性。
今天来谈大家一定要听过的 Bubble Sort，虽然它不是最好的解法，但觉得不能被遗忘的经典。

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Bubble sort 其实就是从头到尾拜访每个元素，两个两个比较。两个数比较後，如果大的在前面就把大的往後移。
同理也可以说小的在後面不断把小的往前移。
以范例来说

[5,2,3,1]

1. 因为 5 > 2 , 所以 要交换位置 变成 [2 , 5 , 3, 1]
2. 因为 5 > 2 , 所以 要交换位置 变成 [2 , 3 , 5, 1]
3. 因为 5 > 1 , 所以 要交换位置 变成 [2 , 3 , 1, 5]

以上是第１回检查 我们总共交换了三组的比较

接着我们进行第2回

1. 因为 2 !> 3,不动
2. 因为 3 > 1 , 所以 要交换位置 变成 [2 , 1 , 3, 5]
3. 因为 3 !> 5, 不动

等等！想一下，第6个步骤我们有需要做吗？
观察第一回合的检查，我们其实就是把最大的数移到最右边了

也就是说，我们走完第一回合，也确定最後一个数会是最大的。
我们第二次的检查其实就可以少1次的比较，虽然少1次对我们时间复杂度的分析帮助不大。
因此跳过上面的6，继续来看第三回
而这一回合我们就知道只剩下 2 和１需要比较，最後可以得到[ 1, 2 ,３, 5]

那我们什麽时候要停止检查？
最简单的原则就是：如果这回合没有任何的交换 就代表array已经按照我们想要的顺序排列了！

时间复杂度的分析：最糟的情况 Ｏ(n^2)，像是遇到[5,4,3,2,1]这种
而最好的情况就是 Ｏ(n), 遇到 [1,2,3,4,5] ，检查一次就可以停止了。

空间复杂度，以上面例子，我们其实都在对同１个阵列做操作（交换）的行为，这种方式称作 in place, 不需要另外的空间来暂存结果，所以是O(1)。

原地演算法（in-place algorithm，也称「就地演算法」）是基本上不需要藉助额外的资料结构就能对输入的资料进行变换的演算法 - wiki

最後来看javascript的实作吧

const bubbleSort = (array) => {
  // 一开始array 没被sort
  let sorted = false;
  // counter来记录我们检查了几回
  let counter = 0;
  while (!sorted) {
    sorted = true;
    // 扣除counter因为我们已经确定每次检查最大数会在後面 可以省略检查
    for (let i = 0; i < array.length - 1 - counter; i++) {
      if (array[i] > array[i + 1]) {
        swap(i, i + 1, array);
        // 只要有交换的行为发生 sorted就要设为还没sorted完 才会再进入到while里检查
        sorted = false;
      }
    }
    counter++;
  }
  return array;
};

// 交换的function
const swap = (i, j, array) => {
  const tmp = array[j];
  array[j] = array[i];
  array[i] = tmp;
};

明天来实作 Insertion sort 和 Selection sort