排序【1】— 冒泡排序

冒泡排序实现原理： 相邻元素两两比较，将更大（更小）的元素和另一比较元素交换位置，这样每循环一轮，就能将最大（最小）的元素移动到最后（最前）。

每次都将更大的元素往后移

<!-- 基础功能实现 -->
<script>
    let arr = [3, 4, 1, 2];
    //外层循环表示比较的次数（倒数第二个元素比较完最后一个元素，最后一个元素无需再比较，所以是 n-1 次
    for (let i = 0; i < arr.length - 1; i++) {
        //内层循环将当前数组最大元素不断移动至最后
        for (let j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    console.log(arr);
</script>

思考一下优化方案，每次比较一轮之后，都可以将最大的元素排序至最后，这样考虑一下我们就能确定，内层循环并不用比较 arr.length-1 次。因为第一次时候，内层循环比较 arr.length-1 次，但第二次的时候因为第一次已经将最大的元素排至最后，内层循环就可以少比较一次。即外层第 i 次循环的时候，内层只需要比较第 (arr.length-1) - i 次。

<!-- 基础实现的内层循环优化 -->
<script>
    let arr = [3, 4, 1, 2];
    for (let i = 0; i < arr.length - 1; i++) {
        //外层第 i 次的时候就表明已经有第 i 个元素已经排列好了，则后面第 i 个不需要再比较
        for (let  j = 0; j < (arr.length - 1) - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    console.log(arr);
</script>

如果需要我们排序的数组是 [1, 2, 4, 3] 这样的结构，实际上代码外层循环只需要执行一次这整个数组就排序完了。根据这个逻辑，我们加一个判断，判断当前内层循环执行过程中是否有元素交换，如果有就表示还没排序完，如果没有元素交换则表明已经排序完成了。

<!-- 基础实现的内层循环优化 ，同时外层判断是否跳出-->
<script>
    // let arr = [3, 4, 1, 2];
    let arr = [1, 2, 4, 3];
    let flag;
    for (let i = 0; i < arr.length - 1; i++) {
        flag = true;   //每次排序前外层循环初始化一下判断标识
        for (let j = 0; j < (arr.length - 1) - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
                flag = false;  //有元素在交换，则排序还未完成
            }
        }
        // 如果 flag 为 false，则排序还未完成，如果 flag 为 true 则排序已经完成可以跳出了
        if(flag) {
            break;
        }
    }
    console.log(arr);
</script>