一些算法题

一、插入排序
插入排序的思路是，从数组的第二个数开始，向前遍历数组arr，找到arr[i] <= item < arr[i +1]。将该数插入到i +1的位置即可。可以看出来，前面那一段数组永远是排好序的，只要找到合适的位置插入数据即可。
之后思路后，就是用代码将其实现即可。

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const item = arr[i];
        let j;
        for (j = i; j > 0 && item < arr[j - 1]; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = item;
    }
    return arr;
}

二、冒泡排序
循环数组，每次将最大的值冒泡到数组的最后一位，依次遍历。

function popSort(arr) {
    for (let i = 0; i < arr.length; 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;
}

三、快速排序
先在数组中找一个基准数字，然后将小于该数的都放在左边，大于的放在右边。不停重复这个操作，直到排序结束。

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const leftArr = [];
    const rightArr = [];
    const p = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] <= p) {
            leftArr.push(arr[i]);
        } else {
            rightArr.push(arr[i]);
        }
    }
    return quickSort(leftArr).concat([p], quickSort(rightArr))
}