1. 冒泡排序

比较相邻2个元素，交换位置

• 升序-则比较完第一轮的时候，最后一个元素是最大的元素
• 数组有n项，就要比较n-1轮，这是固定的（例如2项就比1轮，3项就比2轮），每一轮找出最大的数，移动到后面
• 只是每一轮的比较次数在递减（第一轮比较n-1次，第二轮比较n-2次），因为不需要再比较上一轮中最后一个数了

image.png

// 冒泡排序
// 比较相邻2个元素，交换位置
// 升序-则比较完第一轮的时候，最后一个元素是最大的元素
// 数组有n项，就要比较n-1轮，这是固定的，例如2项就比1轮，3项就比2轮，每一轮找出最大的数，移动到后面
// 只是每一轮的比较次数在递减，第一轮比较n-1次，第二轮比较n-2次，因为不需要再比较上一轮中最后一个数了
function bubbleSort(arr) {
    if (!Array.isArray(arr) || arr.length <= 1) {
        return arr;
    }
    console.log('数组项数量：', arr.length);

    let loopCount = arr.length - 1; // 需要比较n-1轮
    let endI = arr.length - 2; // 第一轮的时候i只需要到达倒数第二个数
    while (loopCount > 0) {
        for (let i = 0; i <= endI; i++) {
            if (arr[i + 1] < arr[i]) { // 如果后面的更小，则交换
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
            }
        }
        endI--;
        loopCount--;
        console.log(loopCount, arr);
    }
    return arr;
}

时间复杂度：最好情况O(n)，最坏情况下O(n²)

2. 插入排序

顾名思义，依次拿出元素，在之前已经排好的顺序表中找到自己的位置

插入排序.gif

• 数组有n项，就要比较n-1轮，这是固定的（因为有n-1个数要来找自己的位置）
• 从第二位元素开始，在它之前的有序表中找到自己的位置（如何找到自己的位置？从它的前一位开始，往前比较，大于或者等于哪个就排在哪个后面）
• 注意：代码跟动图中不一样的实现是：代码中是在找到自己的位置后再移动，不是每次比较都交换位置

image.png

// 插入排序-升序
// 从第二位元素开始，在前面的有序表中找到自己的位置
// 拿出这位要找位置的元素，从它前面一位开始往前比较，它比谁大或者相等就插到谁后面
function insertionSort(arr) {
    if (!Array.isArray(arr) || arr.length <= 1) {
        return arr;
    }
    for (let curI = 1, lth = arr.length; curI < lth; curI++) {
        let leftI = curI - 1; // 从左边的第一个开始找
        while (leftI >= 0) {
            if (arr[leftI] <= arr[curI]) {
                let cur = arr.splice(curI, 1)[0]; // 先把自己移除
                arr.splice(leftI + 1, 0, cur); // 再插入已经找到的位置
                break; // 找到以后就不用再往前找了！！
            }
            leftI--;
        }
    }
    return arr;
}

3. 快速排序

任选一个基准值，将数组分为2边，左侧都小于基准值，右侧都大于等于基准值。
然后对左右两边的列表递归调用这种方式继续排序，直到2边只剩下1项或者没有，就结束排序

image.png

// 快速排序-升序
// 任选一个值作为基准值，把数组按基准值分成左右2边
// 方式：从前往后，将小于它的值移到它左边，那么一轮之后，它左侧都小于它，右侧都大于等于它
// 对它左侧和右侧的列表分别重复上一步排序方式
function quickSort(arr) {
    if (!Array.isArray(arr) || arr.length <= 1) {
        return arr;
    }
    const sort = function (arr, start, end) {
        // 仅对arr的start ~ end项进行排序
        let baseIndex = start;
        let base = arr[baseIndex]; // 选子串的第一项作基准值
        for (let i = start + 1; i <= end; i++) {
            if (arr[i] < base) { // 下一个值如果小于它就移到左边去
                let cur = arr.splice(i, 1)[0]; // 先删掉
                arr.splice(start, 0, cur); // 再插入到子串的头部
                baseIndex++; // 更新一下base当前的位置
            }
        }
        console.log(arr);

        // 一轮之后，arr已经被base分为2边，对左右两边都继续按这个方式排序
        if (baseIndex - start > 1) { sort(arr, start, baseIndex - 1); }  // 对base左边的排序
        if (end - baseIndex > 1) { sort(arr, baseIndex + 1, end); } // 对base右边的排序
    };
    sort(arr, 0, arr.length - 1);
    return arr;
}