還記得以前學(xué)數(shù)據(jù)結(jié)構(gòu)與算法課程的時候，開篇就有些句話”程序=算法+ 數(shù)據(jù)結(jié)構(gòu)“
現(xiàn)在慢慢的發(fā)現(xiàn)算法是一名程序員必不可少的技能，之前我和大多數(shù)前端er一樣，覺得算法在前端使用的非常少，沒必要學(xué)習(xí)算法，如果我們只局限現(xiàn)于前端，那么們的目光也太短淺了。

快速排序

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：選準(zhǔn)一個基數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序

 function quicksort(a,left,right){
     if(left>right){ //一定要有這個判斷，因?yàn)橛羞f歸left和i-1，若沒有這個判斷條件，該函數(shù)會進(jìn)入無限死錯位遞歸
       return;
   }
  
     var i=left,
     j=right,
     jizhun=a[left]; //基準(zhǔn)總是取序列開頭的元素
  
   while(i!=j){ //該while的功能為每一趟進(jìn)行的多次比較和交換最終找到位置k。當(dāng)i==j時意味著找到k位置了
       while(a[j]>=jizhun&&i<j){j--} //只要大于等于基準(zhǔn)數(shù)，j指針向左移動直到小于基準(zhǔn)數(shù)才不進(jìn)入該while。i<j的限制條件也是很重要，不然一直在i!=j這個循環(huán)里，j也會越界
       while(a[i]<=jizhun&&i<j){i++} //只要小于等于基準(zhǔn)數(shù)，i指針向右移動直到大于基準(zhǔn)數(shù)才不進(jìn)入該while。等于條件也是必要的，舉例[4,7,6,4,3]驗(yàn)證一下是兩個4交換
       if(i<j){  //如果i==j跳出外層while
         t=a[i];
         a[i]=a[j];
         a[j]=t 
       } 
    } 
 
   a[left]=a[i];//交換基準(zhǔn)數(shù)和k位置上的數(shù)
   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）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表

function mergeSort(arr) {
    const length = arr.length;
    if (length === 1) { //遞歸算法的停止條件，即為判斷數(shù)組長度是否為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)); //要將原始數(shù)組分割直至只有一個元素時，才開始?xì)w并
}

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都有剩余項(xiàng)的情況, 要么left要么right有剩余項(xiàng), 把剩余項(xiàng)加進(jìn)來即可
    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,]))