想学好前端，先练好内功，只有内功深厚者，前端之路才会走得更远。
笔者写的JavaScript数据结构与算法之美系列用的语言是JavaScript，旨在入门数据结构与算法和方便以后复习。
请大家带着问题：快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢来阅读下文。
思想
排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序采用的是分治思想。
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
实现
constmergeSort=arr=>{//采用自上而下的递归方法constlen=arr.length;if(len<2){returnarr;}//length>>1和Math.floor(len/2)等价letmiddle=Math.floor(len/2),left=arr.slice(0,middle),right=arr.slice(middle);//拆分为两个子数组returnmerge(mergeSort(left),mergeSort(right));};constmerge=(left,right)=>{constresult=[];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());returnresult;};测试
//测试constarr=[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]，保证了值相同的元素，在合并前后的先后顺序不变。归并排序是一种稳定的排序方法。
动画
快速排序的特点就是快，而且效率高！它是处理大数据最快的排序算法之一。
特点：快速，常用。
方法一：
constquickSort1=arr=>{if(arr.length<=1){returnarr;}//取基准点constmidIndex=Math.floor(arr.length/2);//取基准点的值，splice(index,1)则返回的是含有被删除的元素的数组。constvalArr=arr.splice(midIndex,1);constmidIndexVal=valArr[0];constleft=[];//存放比基准点小的数组constright=[];//存放比基准点大的数组//遍历数组，进行判断分配for(leti=0;i //快速排序constquickSort=(arr,left,right)=>{letlen=arr.length,partitionIndex;left=typeofleft!='number'0:left;right=typeofright!='number'len-1:right;if(left //测试constarray=[5,4,3,2,1];console.log('原始array:',array);constnewArr=quickSort(array);console.log('newArr:',newArr);//原始array:[5,4,3,2,1]//newArr:[1,4,3,2,5]分析 因为partition()函数进行分区时，不需要很多额外的内存空间，所以快排是原地排序算法。 和选择排序相似，快速排序每次交换的元素都有可能不是相邻的，因此它有可能打破原来值为相同的元素之间的顺序。因此，快速排序并不稳定。 解答开篇问题 快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？ 可以发现： 过程 constshellSort=arr=>{letlen=arr.length,temp,gap=1;console.time('希尔排序耗时');while(gap //测试constarray=[35,33,42,10,14,19,27,44];console.log('原始array:',array);constnewArr=shellSort(array);console.log('newArr:',newArr);//原始array:[35,33,42,10,14,19,27,44]//arr:[14,33,42,10,35,19,27,44]//arr:[14,19,42,10,35,33,27,44]//arr:[14,19,27,10,35,33,42,44]//arr:[14,19,27,10,35,33,42,44]//arr:[14,19,27,10,35,33,42,44]//arr:[14,19,27,10,35,33,42,44]//arr:[10,14,19,27,35,33,42,44]//arr:[10,14,19,27,35,33,42,44]//arr:[10,14,19,27,33,35,42,44]//arr:[10,14,19,27,33,35,42,44]//arr:[10,14,19,27,33,35,42,44]//希尔排序耗时:3.592041015625ms//newArr:[10,14,19,27,33,35,42,44]分析 希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为O(1)。所以，希尔排序是原地排序算法。 我们知道，单次直接插入排序是稳定的，它不会改变相同元素之间的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，可能导致相同元素相对顺序发生变化。因此，希尔排序不稳定。 最佳情况：T(n)=O(nlogn)。最差情况：T(n)=O(n(log(n))2)。平均情况：T(n)=取决于间隙序列。 堆的定义 堆其实是一种特殊的树。只要满足这两点，它就是一个堆。 完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。 也可以说：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。 对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大顶堆。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小顶堆。 其中图1和图2是大顶堆，图3是小顶堆，图4不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。 constarray=[4,6,8,5,9,1,2,5,3,2];console.log('原始array:',array);constnewArr=heapSort(array);console.log('newArr:',newArr);//原始array:[4,6,8,5,9,1,2,5,3,2]//堆排序耗时:0.15087890625ms//newArr:[1,2,2,3,4,5,5,6,8,9]分析 整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。 因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。所以，堆排序是不稳定的排序算法。 复杂性对比 算法可视化工具 效果如下图。 旨在通过交互式可视化的执行来揭示算法背后的机制。 变量和操作的可视化表示增强了控制流和实际源代码。您可以快速前进和后退执行，以密切观察算法的工作方式。