还记得以前学数据结构与算法课程的时候，开篇就有些句话”程序=算法+ 数据结构“
现在慢慢的发现算法是一名程序员必不可少的技能，之前我和大多数前端er一样，觉得算法在前端使用的非常少，没必要学习算法，如果我们只局限现于前端，那么们的目光也太短浅了。

快速排序

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：选准一个基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程以递归进行，以此达到整个数据变成有序

 function quicksort(a,left,right){
     if(left>right){ //一定要有这个判断，因为有递归left和i-1，若没有这个判断条件，该函数会进入无限死错位递归
       return;
   }
  
     var i=left,
     j=right,
     jizhun=a[left]; //基准总是取序列开头的元素
  
   while(i!=j){ //该while的功能为每一趟进行的多次比较和交换最终找到位置k。当i==j时意味着找到k位置了
       while(a[j]>=jizhun&&i<j){j--} //只要大于等于基准数，j指针向左移动直到小于基准数才不进入该while。i<j的限制条件也是很重要，不然一直在i!=j这个循环里，j也会越界
       while(a[i]<=jizhun&&i<j){i++} //只要小于等于基准数，i指针向右移动直到大于基准数才不进入该while。等于条件也是必要的，举例[4,7,6,4,3]验证一下是两个4交换
       if(i<j){  //如果i==j跳出外层while
         t=a[i];
         a[i]=a[j];
         a[j]=t 
       } 
    } 
 
   a[left]=a[i];//交换基准数和k位置上的数
   a[i]=jizhun;
 
   quicksort(a,left,i-1);
   quicksort(a,i+1,right);
 }
 
 var array=[4,7,2,8,3,9,12];
 quicksort(array,0,array.length-1);//排完序后再看array是[2, 3, 4, 7, 8, 9, 12]

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表

function mergeSort(arr) {
    const length = arr.length;
    if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1
        return arr;
    }
    const mid = Math.floor(length / 2);
   
    const left = arr.slice(0,  mid);
    const right = arr.slice(mid, length);
  
    return merge(mergeSort(left), mergeSort(right)); //要将原始数组分割直至只有一个元素时，才开始归并
}

function merge(left, right) {
    const result = [];
    let il = 0;
    let ir = 0;

    //left, right本身肯定都是从小到大排好序的
    while( il < left.length && ir < right.length) {
        if (left[il] < right[ir]) {
            result.push(left[il]);
            il++;
        } else {
            result.push(right[ir]);
            ir++;
        }
        
    }

    //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
    while (il < left.length) { 
        result.push(left[il]);
        il++;
    }
    while(ir < right.length) {
        result.push(right[ir]);
        ir++;
    }
    return result;
}
console.log(mergeSort([2,9,1,8,3,]))