排序

基础排序算法：
- 冒泡排序
- 插入排序
- 选择排序
进阶排序算法
- 归并排序
- 快速排序

冒泡

我们分最好、最坏和平均来看：

最好时间复杂度：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 O(n)
最坏时间复杂度：它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n^2)
平均时间复杂度：这个东西比较难搞，它涉及到一些概率论的知识。实际面试的时候也不会有面试官摁着你让你算这个，这里记住平均时间复杂度是 O(n^2) 即可

对于每一种排序算法的时间复杂度，大家对计算依据有了解即可，重点在于记忆。面试的时候不要靠现场推导，要靠直觉+条件反射。

//最佳情况，即已是顺序，时间复杂度为O（n）
let arr = [5, 3, 2, 4, 1];

function betterBubbleSort(arr) {
    length = arr.length;
    for (let i = 0; i < length - 1; i++) {
        let flag = false;
        for (let j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
            }
        }
        if (!flag) {
            return arr
        }
    }
    return arr
}

console.log(
    betterBubbleSort(arr)
);

选择

时间复杂度：都是要走内层循环作比较的。因此选择排序的三个时间复杂度都对应两层循环消耗的时间量级： O(n^2)

核心思想: 选择排序的关键字是“最小值”：循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止

let arr = [5, 3, 2, 4, 1];

function selectSort(arr) {
    const len = arr.length;
    //注意i < len - 1，前四个排序完成，后一个不需要再比较
    for (let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for (let j = i; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr
}
console.log(
    selectSort(arr)
);

插入

时间复杂度：都是要走内层循环作比较的。因此选择排序的三个时间复杂度都对应两层循环消耗的时间量级： O(n^2)

核心思想: 找到元素在它前面那个序列中的正确位置

当前元素前面的那个序列是有序的
“正确的位置”如何定义——所有在当前元素前面的数都不大于它，所有在当前元素后面的数都不小于它
在有序序列里定位元素位置的时候，是从后往前定位的。只要发现一个比当前元素大的值，就需要为当前元素腾出一个新的坑位。

let arr = [5, 3, 2, 4, 1];

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

    return arr
}
console.log(
    insertSort(arr)
);

归并

时间复杂度:

总时间复杂度=（创建常量+判断）+ 分割合并

分割时间复杂度：

分割规模为 n 的数组，需要分割x次，即2^x = n => x=log n，时间复杂度为O（log n）

合并时间复杂度：

单次合并的时间复杂度为 O(n)。O(n) 和 O(1) 完全不在一个复杂度量级上，因此本着“抓主要矛盾”的原则，我们可以认为：决定归并排序时间复杂度的操作就是合并操作。

总时间复杂度=O(1)+O(nlogn) =O(nlogn)

归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：

分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组

图片说明

//第一部分：求解+合并
let arr=[8, 7, 6, 5, 4, 3, 2, 1]
let merge = function (num1, num2) {
    let i = 0,
        j = 0,
        len1 = num1.length,
        len2 = num2.length;
    let res = [];
    while (i < len1 && j < len2) {
        if (num1[i] > num2[j]) {
            res.push(num2[j])
            j++;
        } else {
            res.push(num1[i])
            i++;
        }
    }

//    while (j < len2) {
//        res.push(num2[j])
//        j++;
//    }
//    while (i < len1) {
//        res.push(num1[i])
 //       i++;
//    }
    // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
    if(i<len1) {
        return res.concat(arr1.slice(i))
    } else {
        return res.concat(arr2.slice(j))
    }
    return res
};

//第二部分：分解问题
let sliceSort = function (arr) {
    const len = arr.length;

    if (len <= 1) {
        return arr;
    }

    let mid = Math.floor(len / 2);
    let leftArr = sliceSort(arr.slice(0, mid));
    let rightArr = sliceSort(arr.slice(mid, len));

    let res = merge(leftArr, rightArr);
    return res;
}
console.log(
    sliceSort(arr)
);

快排

右指针所指的值不大于基准，左指针所指的值不小于基准，故两个指针都不再移动。

此时我们会发现，对于基准来说，它左边的所有数字都比它小，右边的所有数字都比它大（这里注意也可能存在相等的情况）。由此我们就能够以左指针为轴心，划分出一左一右、一小一大两个子数组

时间复杂度

最好时间复杂度：它对应的是这种情况——我们每次选择基准值，都刚好是当前子数组的中间数。这时，可以确保每一次分割都能将数组分为两半，进而只需要递归 log(n) 次。这时，快速排序的时间复杂度分析思路和归并排序相似，最后结果也是 O(nlog(n))。
最坏时间复杂度：每次划分取到的都是当前数组中的最大值/最小值。大家可以尝试把这种情况代入快排的思路中，你会发现此时快排已经退化为了冒泡排序，对应的时间复杂度是 O(n^2)。
平均时间复杂度： O(nlog(n))

图片说明

let arr = [2, 7, 5, 6, 3, 4, 9, 1, -2];
let quickSort = function (arr, left = 0, right = arr.length - 1) {
    // 递归
    const lineIndex = partition(arr, left, right);
    if (left < lineIndex - 1) {
        quickSort(arr, left, lineIndex - 1);
    }
    if (right > lineIndex) {
        quickSort(arr, lineIndex, right);
    }

    return arr;


    // 以基准值为轴心，划分左右子数组
    function partition(arr, left, right) {
        const pivotValue = arr[Math.floor(left + (right - left) / 2)];
        let i = left,
            j = right;
        while (i <= j) {
            while (arr[i] < pivotValue) {
                i++;
            }
            while (arr[j] > pivotValue) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        return i;
    }

    // swap交换
    function swap(arr, i, j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }

}


console.log(quickSort(arr).toString());

算法 - 排序 - 快排不快？

排序

冒泡

选择

插入

归并

快排