算法设计思想--分而治之(一文搞懂归并排序和快速排序)
一、学完这篇，你可以收获什么？
算法思想：分而治之
归并排序
快速排序
二、归并排序
在学习归并排序之前，我们先了解分而治之思想。
1、分而治之
分而治之是算法设计的一种思想。
它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。
典型例子：归并排序和快速排序
2、归并排序
由于归并排序性能不错，因此火狐浏览器sort方法使用的是归并排序算法。
我们可以从这个网站https://visualgo.net/zh/sorting形象看出归并排序是如何进行的。
归并排序是一种分而治之算法。思想是想将数组切割成两大半，然后先递归第1大半，继续将第1半切割成两半，直到将数组切成只有一个元素的数组，然后再合并，合并成较大数组；紧接着再递归第2大半，原理如上。最后，将两大半排序好的数组合并，即可完成递归。
如图所示：
按照以上思路，我们先将将数组丢进递归函数持续分成两半 → 接着比较队头大小，小的先出队，以此类推。
Array.prototype.mergeSort = function() {// 定义一个递归函数将数组转换const rec = (arr) => {// 第一部分，拆分数组// 如果传进来数组只有一个，或者递归只剩一个数组，那么直接返回arrif (arr.length === 1) return arr;// 1、解构获取arr长度→目的是将数组分成两半const { length } = arr;const mid = Math.floor(length / 2)// 2、将数组分成左右两部分const left = arr.slice(0, mid);const right = arr.slice(mid, arr.length);// 3、将左右数组继续丢进递归函数rec进行拆分。const orderLeft = rec(left);const orderRight = rec(right);// 4、新建一个空数组存储比较大小后的值const res = [];// 第二部分，比较大小// 左边和右边数组都有值情况下，不断比较大小while(orderLeft.length || orderRight.length){// 若左边数组有值，右边数组有值，那么此时我们要比较他们的队头，并把较小值出队if(orderLeft.length && orderRight.length) {// 队头下标为0就可以拿到。如果左边的队头小于右边队头，则左边队头出队，否则右边的队头出队。res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())}else if(orderLeft.length) {res.push(orderLeft.shift())}else if (orderRight.length) {res.push(orderRight.shift())}}return res}const res = rec(this)// forEach获取索引值和索引res.forEach((n, i) => { this[i] = n; });}const arr = Array(5,4,3,2,1)arr.mergeSort()console.log(arr)
从以上解题思路，我们看看归并排序是怎么进行分而治之的：
分：把数组从中间一分为二 → 解：递归地对两个子数组进行归并排序 →
合：合并有序子数组
三、快速排序
快速排序性能与归并排序性能是一样的，谷歌浏览器使用的sort方法是快速排序
同样的，我们可以从这个网站https://visualgo.net/zh/sorting形象看出归并排序是如何进行的。
我们截图进行分析：
第一步，将数组分成两半：
第二步，先搞左边数组，同上步操作：
按照如上思路，我们解题方法如下：
Array.prototype.quickSort = function() {// 核心递归逻辑const rec = (arr) => {// 终结递归，否则递归是没有尽头的;if(arr.length <= 1) return arr;console.log(arr.length)// 逻辑递归操作const left = [];const right = [];const mid = arr[0];for(let i = 1; i < arr.length; i += 1) {if(arr[i] < mid){left.push(arr[i]);}else {right.push(arr[i]);}}return [...rec(left), mid, ...rec(right)];};const res = rec(this);res.forEach((n, i) => { this[i] = n })}const arr = [4, 3, 2, 1, 8, 7, 6, 5]arr.quickSort()console.log(arr)