歸并排序和快速排序總結

1. 算法基本思路：分治

分治，字面上的解釋是“分而治之”，就是把一個複雜的問題分成多個同等結構的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合并。歸并排序和快速排序都采用了二分法思想。不同之處在于，歸并排序在“分”的問題上是簡單的一刀切，而将重點放在了如何“歸并”上。而快速排序則花了很大的功夫在如何“分”這個問題上，“歸并”則變得非常簡單。

2. 由歸并排序和快速排序衍生出來的問題

2.1 求數組中的逆序對

“逆序對”，顧名思義，即從數組中随意抽出兩個數，如果前一個數比後一個數大，則稱這兩個數為逆序對。數組中逆序對的數量可以衡量數組的有序程度。如果數組為完全升序的數組，那麼任意抽出一個數對都會是順序對；而如果數組為完全倒序的數組，則任意抽出一個數對都為逆序對。那麼，該如何利用歸并排序的思想更加快速的求解數組中的逆序對數量呢？

比如說對數組2，3，6，8和數組1，4，5，7進行歸并的時候，發現1比2小，則可以斷定，1比2之後的所有元素都要小，則此處一共有4個逆序數組。按照這種思路，能以nlogn的效率計算一個數組中的逆序對。

/**
 * 利用歸并排序的思路，計算數組中逆序對的個數
 * @param  {Array} arr   待計算的數組
 * @param  {Number} left  左邊界
 * @param  {Number} right 右邊界
 * @return {Number}       傳回逆序對的個數
 */
function countReverseOrder(arr,left,right){
    if (left >= right) {
        return ;
    }
    var mid = Math.floor((left + right)/);
    var countL = countReverseOrder(arr,left,mid,count);
    var countR = countReverseOrder(arr,mid+,right,count);

    //歸并
    var leftPart = arr.slice(left,mid+);
    var rightPart = arr.slice(mid+,right+);
    var l = ;
    var r = ;
    var count = countL + countR;
    for (var i = left; i <= right; i++) {
        if (l >= leftPart.length) {
            arr[i] = rightPart[r];
            r ++;
        } else if (r >= rightPart.length) {
            arr[i] = leftPart[l];
        } else if (leftPart[l] > rightPart[r]) {
            arr[i] = rightPart[r];
            r ++;
            count += leftPart.length - l;
        } else {
            arr[i] = leftPart[l];
            l ++;
        }
    }
    return count;
}

var arr = [,,,,,,,];
countReverseOrder(arr,,arr.length-,);//11
           

2.1 求數組中第N大的元素(O(n)複雜度）

利用快速排序的思路，可以很友善的求出數組中第N大的元素，其時間複雜度為O（n）。實質上，算法複雜度= n + n/2 + n/4 + n/8 +……+ 1 = O（2n）。

Array.prototype.changeData = function(indexOne,indexTwo){
    var temp = this[indexOne];
    this[indexOne] = this[indexTwo];
    this[indexTwo] = temp;
};

function findTopN(arr,lIndex,rIndex,n){
    arr.changeData(lIndex,Math.floor(Math.random()*(rIndex-lIndex+)+lIndex));
    var i = lIndex;
    // var j = lIndex + 1;
    var v = arr[lIndex];
    for (var j = lIndex + ; j <= rIndex; j++) {
        if (arr[j] < v) {
            arr.changeData(j,i+);
            i ++;
        }
    }
    arr.changeData(i,lIndex);
    if (i == n-) {
        return arr[i];
    } else if(i > n-){
        return findTopN(arr,lIndex,i-,n);
    } else {
        return findTopN(arr,i+,rIndex,n);
    }
}

var arr = [,,,,,,,];
findTopN(arr,,arr.length-,);