Day19:[排序演算法]Bubble Sort - 气泡排序法

bubble sort的概念就是像泡泡一样，越大的数字会渐渐的往右边浮

比较相邻的元素，两两比大小，如果前面的数字大於後面的数字就交换顺序，一路把最大值往後塞。

跑完第1回合，该阵列的最後一个数字就会是最大的
跑完第2回合，该阵列的倒数第2个数字就会是第2大的
规律为执行完第n回合，第n大的数字就会出现在倒数第n个位置

函式内部实作为:

假设现在有一个阵列[29, 10, 14, 37, 14]要用气泡排序法来排序的话

29与10相比29较大，所以29与10交换，此时arr = [10, 29, 14, 37, 14]
29与14相比29较大，所以29与14交换，此时arr = [10, 14, 29, 37, 14]
29与37相比29较小，所以29不跟37交换，此时arr = [10, 14, 29, 37, 14]
37与14相比37较大，所以37与14交换，此时arr = [10, 14, 29,14, 37]

此时第一回合结束，可以发现最大的数字已经移动到最後面，依序执行n-1回合之後，就可以将全部的数字由小排到大了。

为甚麽是n-1回合?
假如今天有个阵列长度为5，当index1 ~ index4都是排序好的，那麽index0自然也会是最小的，就不需要再跑一次回合，所以只要跑 (n-1)，5–1=4回合即可。

连续的步骤会如下图所示

图档来源:https://visualgo.net/zh/

用js实作气泡排序法

const bubble = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
};
bubble([29, 10, 14, 37, 14])

第一个回圈的长度为arr.length-1，因为经过一轮的排列，直到最後一回合，剩下的那个值必定为最小值，就不需要比较，可以扣掉一次，那第二个回圈的长度为甚麽是arr.length-i-1 ?因为经过i回合後，倒数第i个数字都是经过排序的，那麽在跑回圈的时候就可以排除掉，不需要检查了。