绝对记得住的各种排序算法(中)-一一网

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

前言

死磕算法，每天至少一道算法题

不知道绝对记得住的各种排序算法(上)大家学了有没有收货，有什么疑问都可以在评论区留言哦，看了文章，有疑问，多讨论才能有更多收货哦

今天我们开始将绝对记得住的各种排序算法(中)

归并排序
快速排序

归并排序

为什么叫归并呢，这个名字很拗口呀，我猜是递归+合并的意思，名字起的真是画龙点睛呀

思路

归并排序的思想源于分治思想，分治思想也就是将一个大问题分解为若干个子问题，然后子问题在分别求解，最后在合成为大问题的解

比如让你算从1加到100这个问题，怎么使用分治思想来解这道题目呢，我们可以分解成1+100，2+99，3+98，….50+51等50个解，然后在把子问题的解合成大问题的解，50个101相加，则为5050，这样子想问题就很容易得到答案了

分治思想的精髓，在于以下三步走

分解子问题
求解子问题
合并子问题的解，得出大问题的解

了解了分治思想以后，我们来看归并排序是如何根据分治思想一步一步实现的

分解子问题：将数组从中间分割为两半，然后在对每个子数组从中间切割，不断重复以上的操作，直至单个子数组只有一个元素位置
求解每个子问题：从粒度最小的子数组开始，两两合并，确保每次合并出来的数组都是有序的。当数组合并到原有规模的时候，就会得到一个有序的数组。

演示

我本来找的动画演示，但是我觉得动画演示不如手写的直观，所以还是手工的效果好，哈哈

给定一个数组

[2,10,9,8]
复制代码

从中间分解

[2,10]|[9,8]
复制代码

再次分解

[2]|[10]|[9]|[8]
复制代码

合并

[2,10]|[8,9]
复制代码

再次合并

[2,8,9,10]
复制代码

不断的分解再分解，这是重复的动作呀，那就用递归呀

其实这个不断分解的过程，不就是树形结构么，想到树形结构，我们立马想到递归

这个合并数组不就是我们以前做过的题目，合并两个有序数组，建议大家在复习一下

题解

const mergeArr = function (firstArr, secondArr) {
    // 定义两个指针
    let i = 0;
    let j = 0;
    // 定义一个结果
    let result = [];
    while (i < firstArr.length && j < secondArr.length) {
        if (firstArr[i] <secondArr[j]) {
            result.push(firstArr[i]);
            i++;
        } else {
            result.push(secondArr[j]);
            j++;
        }
    }
    // 看哪个数组没有遍历完全，就在合并一下
    if (i < firstArr.length) {
        return result.concat(firstArr.slice(i));
    } else {
        return result.concat(secondArr.slice(j));
    }
}
const mergeSort = function (nums) {
    let length = nums.length;
    // 边界问题一定要记得处理
    if (length<=1) {
        return nums;
    }
    // 取一个中间值
    let mid = Math.floor(length / 2);
    // 分解
    let left = mergeSort(nums.slice(0, mid));
    let right = mergeSort(nums.slice(mid));
    // 合并
    let arr = mergeArr(left, right);
    return arr;
}
复制代码

时间复杂度

归并排序的递归树，树种每层元元素的个数最多是n，也就代表着每层最多进行n次比较，而递归树最多只有log2n层，合在一起就是nlog2n了。

快速排序

思路

快速排序也用了分治的思想

也是需要不断分解在分解的，可是他不像归并排序一样从中间分解，而是每次都有一个基点，这个基点是数组中的一个元素，可以是最左边的，也可以是中间的，也可以是最右边的，所有的元素和这个基点进行对比然后分为两个子数组，每个子数组再以最右边的元素为基点，进行比对，然后分组，不断重复上面的操作，直至分解为一个

图解

题解

const quickSort = function (nums) {
    let length = nums.length;
    // 为什么这里这样写呢？因为最多分到数组中只有一个值，这个时候把这个值返回
    if (length <= 1) {
        return nums;
    }
    // 选取基点数
    const point = nums[length - 1];
    let left = [];
    let right = [];
    //数组中的每个数与基点数做对比
    // 因为我们是取的最右侧的数字，所以length-1，因为point不用拿出来进行比较
    for (let i = 0; i < length - 1; i++){
        if (nums[i] < point) {
            left.push(nums[i]);
        } else {
            right.push(nums[i]);
        }
    }
    let arr1 = quickSort(left);
    let arr2 = quickSort(right);
    return arr1.concat([point], arr2);
}
复制代码