const arr = [5, 4, 3, 2, 1];
/**
 * 外循环控制比较的轮数
 * 内循环控制每轮比较的次数
*/
function bubble(arr) {
    // 轮数(需要arr.length - 1轮)
    // 这里数组中一共有5个数，只需要把数组中最大的4个数依次放到数组末尾即可。
    for (let i = 0; i < arr.length - 1; i++) {
        // 每轮比较的次数
        // 减去1的原因：每一轮都不需要和自己比
        // 减去i的原因：比如说第二轮的话，i等于1，因为在第一轮的时候已经把数组中最大的元素放到了数组末尾，因此不需要再跟最后一个元素比较，因此需要减去i。以此类推，第三轮和第四轮也是同理。
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // let temp = arr[j];
                // arr[j] = arr[j+1];
                // arr[j+1] = temp;
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}
console.log(bubble(arr)); // [1, 2, 3, 4, 5]

const arr = [12, 6, 23, 4, 36, 18];

function insert(arr) {
    const res = []; // 结果数组
    res.push(arr[0]); // 默认将第一项先放到结果数组中
    // 从第二项开始依次插入
    for (let i = 1; i < arr.length; i++) {
        // currentEle是当前要插入的元素
        const currentEle = arr[i];
        // 从后往前比
        for (let j = res.length - 1; j >= 0; j--) {
            if (currentEle > res[j]) {
                // 如果currentEle比res[j]大，则将currentEle插入到res[j]的前面
                // 所以这里splice方法的第一个参数是j+1，而不是j
                res.splice(j + 1, 0, currentEle);
                break;
            }
            // 上面的if语句会一直从后向前比较，直到和res中的第一项比较完
            if (j === 0) {
                // 走到这里说明，currentEle比res中的第一项还要小，直接插入到数组最前面即可
                res.unshift(currentEle);
            }
        }
    }
    return res;
}
console.log(insert(arr));

const arr = [12, 6, 23, 4, 36, 18];

function quick(arr) {
    // 第四步：结束递归(当arr中小于等于一项，则不用继续递归处理)
    if (arr.length <= 1) {
        return arr;
    }
    // 第一步：找到数组的中间项，并在原数组中将其移除
    const middleIndex = Math.floor(arr.length / 2); // 向下取整
    const [middleValue] = arr.splice(middleIndex, 1);
    // 第二步：准备左右两个数组，循环数组中剩余的项，比中间项小的放到左数组中，反之放到右数组中
    const leftArr = [];
    const rightArr = [];
    for (let i = 0; i < arr.length; i++) {
        const item = arr[i];
        item < middleValue ? leftArr.push(item) : rightArr.push(item);
    }
    // 第三步：采用递归让左右两边的数组继续这样处理，直到左右两边都排好序
    return quick(leftArr).concat(middleValue, quick(rightArr));
}

console.log(quick(arr));

const arr = [12, 6, 23, 4, 36, 18, 16];

function quick(arr) {
    // 第四步：结束递归(当arr中小于等于一项，则不用继续递归处理)
    if (arr.length <= 1) {
        return arr;
    }
    // 第一步：直接将数组第一项作为中间项
    // 第二步：准备左右两个数组，循环数组中剩余的项，比中间项小的放到左数组中，反之放到右数组中
    const leftArr = [];
    const rightArr = [];
    const firstValue = arr[0];
    // 从第二项开始循环处理。
    for (let i = 1; i < arr.length; i++) {
        const item = arr[i];
        item < firstValue ? leftArr.push(item) : rightArr.push(item);
    }
    // 第三步：采用递归让左右两边的数组继续这样处理，直到左右两边都排好序
    return quick(leftArr).concat(firstValue, quick(rightArr));
}

console.log(quick(arr));