算法为王。
想学好前端，先练好内功，只有内功深厚者，前端之路才会走得更远。
笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。
之所以把归并排序、快速排序、希尔排序、堆排序放在一起比较，是因为它们的平均时间复杂度都为 O(nlogn)。
请大家带着问题：快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢 ? 来阅读下文。
2. 归并排序（Merge Sort）思想
排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序采用的是分治思想。
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
注：x >> 1 是位运算中的右移运算，表示右移一位，等同于 x 除以 2 再取整，即 x >> 1 === Math.floor(x / 2) 。
实现
const mergeSort = arr => { //采用自上而下的递归方法 const len = arr.length; if (len < 2) { return arr; } // length >> 1 和 Math.floor(len / 2) 等价 let middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); // 拆分为两个子数组 return merge(mergeSort(left), mergeSort(right)); }; const merge = (left, right) => { const result = []; while (left.length && right.length) { // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定. if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; };测试
// 测试 const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]; console.time('归并排序耗时'); console.log('arr :', mergeSort(arr)); console.timeEnd('归并排序耗时'); // arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] // 归并排序耗时: 0.739990234375ms分析
第一，归并排序是原地排序算法吗 ？
这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。
实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
所以，归并排序不是原地排序算法。
第二，归并排序是稳定的排序算法吗 ？
merge 方法里面的 left[0] <= right[0] ，保证了值相同的元素，在合并前后的先后顺序不变。归并排序是一种稳定的排序方法。
第三，归并排序的时间复杂度是多少 ？
从效率上看，归并排序可算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步, 又每步都是一个普通的合并子数组的过程，时间复杂度为 O(n)，故其综合时间复杂度为 O(nlogn)。
最佳情况：T(n) = O(nlogn)。
最差情况：T(n) = O(nlogn)。
平均情况：T(n) = O(nlogn)。
动画
快速排序的特点就是快，而且效率高！它是处理大数据最快的排序算法之一。
思想
先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。
左右分别用一个空数组去存储比较后的数据。
最后递归执行上述操作，直到数组长度 <= 1;
特点：快速，常用。
缺点：需要另外声明两个数组，浪费了内存空间资源。
实现
方法一：
const quickSort1 = arr => { if (arr.length <= 1) { return arr; } //取基准点 const midIndex = Math.floor(arr.length / 2); //取基准点的值，splice(index,1) 则返回的是含有被删除的元素的数组。 const valArr = arr.splice(midIndex, 1); const midIndexVal = valArr[0]; const left = []; //存放比基准点小的数组 const right = []; //存放比基准点大的数组 //遍历数组，进行判断分配 for (let i = 0; i < arr.length; i++) { if (arr[i] < midIndexVal) { left.push(arr[i]); //比基准点小的放在左边数组 } else { right.push(arr[i]); //比基准点大的放在右边数组 } } //递归执行以上操作，对左右两个数组进行操作，直到数组长度为 <= 1 return quickSort1(left).concat(midIndexVal, quickSort1(right)); }; const array2 = [5, 4, 3, 2, 1]; console.log('quickSort1 ', quickSort1(array2)); // quickSort1: [1, 2, 3, 4, 5]