摘要：快速排序在解決中方法問題時，筆者沒有考慮時間復(fù)雜度的問題，使用的排序算法進(jìn)行重寫，在實(shí)際產(chǎn)品環(huán)境中引發(fā)不小的性能問題。中方法的兼容問題筆者發(fā)現(xiàn)或者中方法不生效不同瀏覽器實(shí)現(xiàn)機(jī)制差異，故判斷后進(jìn)行該方法的重寫處理，代碼如下

在解決 Sarafi 中 sort 方法問題時，筆者沒有考慮時間復(fù)雜度的問題，使用 O(n2) 的排序算法進(jìn)行重寫，在實(shí)際產(chǎn)品環(huán)境中引發(fā)不小的性能問題。

閱讀 v8 array.js 源碼（Array.js）后發(fā)現(xiàn)，Chrome 在實(shí)現(xiàn) sort 方法時對小數(shù)組（length <= 10）進(jìn)行插入排序，對大數(shù)組進(jìn)行快速排序 O(nlogn)，來降低該方法的時間復(fù)雜度。

快速排序的核心是不斷把原數(shù)組做切割，切割成小數(shù)組后再對小數(shù)組進(jìn)行相同的處理，這是一種典型的分治的算法設(shè)計(jì)思路，選取數(shù)組中第一個元素作為基準(zhǔn)，可對其進(jìn)行簡單實(shí)現(xiàn)如下：

function QuickSort(arr, func) {
    if (!arr || !arr.length) return [];
    if (arr.length === 1) return arr;
    
    var pivot = arr[0];
    var smallSet = [];
    var bigSet = [];
    for (var i = 1; i < arr.length; i++) {
        if (func(arr[i], pivot) < 0) {
            smallSet.push(arr[i]);
        } else {
            bigSet.push(arr[i]);
        }
    }
    
    return basicSort(smallSet, func).concat([pivot]).concat(basicSort(bigSet, func));
}

上面的算法創(chuàng)建一個新的數(shù)組作為計(jì)算結(jié)果，從空間使用的角度看是不經(jīng)濟(jì)的，Javascript 的快速排序算法中并沒有像上面的代碼那樣創(chuàng)建一個新的數(shù)組，而是在原數(shù)組的基礎(chǔ)上，通過交換元素位置實(shí)現(xiàn)排序，故而類似于 push、 pop、 splice 這幾個方法，sort 方法也是會修改原數(shù)組對象的。

function swap(arr, from, to) {
    if (from === to) return;

    let temp = arr[from];
    arr[from] = arr[to];
    arr[to] = temp;
}
 
function QuickSortWithPartition(arr, fn, from, to) {
    from = from === void 0 ? 0 : from;
    to = to === void 0 ? arr.length : to;

    if (from >= to - 1) {
        return arr;
    }

    let pivot = arr[from];
    let smallIndex = from;
    let bigIndex = from + 1;

    for (; bigIndex < to; bigIndex++) {
        if (fn(arr[bigIndex], pivot) < 0) {
            smallIndex++;
            swap(arr, smallIndex, bigIndex);
        }
    }

    swap(arr, smallIndex, from);

    QuickSortWithPartition(arr, fn, from, smallIndex - 1);
    QuickSortWithPartition(arr, fn, smallIndex + 1, to);

    return arr;
}

其中，from 是起始索引，to 是終止索引，如果這兩個參數(shù)缺失，則表示處理整個數(shù)組。

因?yàn)樯厦娴姆謪^(qū)過程中，大數(shù)分區(qū)和小數(shù)分區(qū)都是從左向右增長，其實(shí)我們可以考慮從兩側(cè)向中間遍歷，這樣能有效地減少交換元素的次數(shù)。舉個例子，假如我們有一個數(shù)組 [2, 1, 3, 1, 3, 1, 3]，采用上面的分區(qū)算法一共會碰到三次比基準(zhǔn)元素小的情況，所以會發(fā)生三次交換；而如果我們換個思路，把從右往左找到小于基準(zhǔn)的元素，和從左往右找到大于基準(zhǔn)的元素交換，這個數(shù)組只需要交換一次即可完成排序（把第一個3和最后一個1交換）。

function QuickSortWithPartitionOp(arr, fn, from, to) {
    from = from === void 0 ? 0 : from;
    to = to === void 0 ? arr.length : to;

    if (from >= to - 1) {
        return arr;
    }

    let pivot = arr[from];
    let smallEnd = from;
    let bigBegin = to - 1;

    while (smallEnd < bigBegin) {
        while (fn(arr[bigBegin], pivot) >= 0 && smallEnd < bigBegin) {
            bigBegin--;
        }

        while (fn(arr[smallEnd], pivot) <= 0 && smallEnd < bigBegin) {
            smallEnd++;
        }

        if (smallEnd < bigBegin) {
            swap(arr, smallEnd, bigBegin);
        }
    }

    swap(arr, smallEnd, from);

    QuickSortWithPartitionOp(arr, fn, from, smallEnd - 1);
    QuickSortWithPartitionOp(arr, fn, smallEnd + 1, to);

    return arr;
}

快速排序算法平均時間復(fù)雜度是 O(nlogn)，但它的最差情況下時間復(fù)雜度會增大到 O(n2)，其性能好壞的關(guān)鍵就在于分區(qū)是否合理：如果每次都能平均分成相等的兩個分區(qū)，那么只需要 logn 層遞歸；而如果每次分區(qū)都不合理，總有一個分區(qū)是空的，則需要 n 層迭代。

對于一個內(nèi)容隨機(jī)的數(shù)組而言，不太可能出現(xiàn)最差情況，但日常處理的數(shù)組往往并不是內(nèi)容隨機(jī)的，一種很容易的解決方案是不要選取固定位置的元素作為基準(zhǔn)元素，而是隨機(jī)從數(shù)組里挑出一個元素作為基準(zhǔn)元素，這樣可以極大概率地避免最差情況，然而這并不等于避免最差情況，特別是在數(shù)組很大的時候，更要求我們更謹(jǐn)慎地選取基準(zhǔn)元素。

三數(shù)取中法是挑選基準(zhǔn)元素的一種常用方法：即挑選基準(zhǔn)元素時，先把第一個元素、最后一個元素和中間一個元素挑出來，這三個元素中大小在中間的那個元素就被認(rèn)為是基準(zhǔn)元素。

function getPivot(arr, fn, from, to) {
    let mid = (from + to) >> 1;

    if (fn(arr[from], arr[mid]) < 0) {
        swap(arr, from, mid);
    }

    if (fn(arr[from], arr[to]) > 0) {
        swap(arr, from, to);
    }

    if (fn(arr[to], arr[mid]) < 0) {
        swap(arr, to, mid);
    }

    return arr[from];
}

其他比較典型的取中值手段包括：

一種是平均間隔取一個元素，多個元素取中位數(shù)（即多取幾個，增加可靠性）

一種是對三數(shù)取中進(jìn)行遞歸運(yùn)算，先把大數(shù)組平均分成三塊，對每一塊進(jìn)行三數(shù)取中，會得到三個中值，再對這三個中值取中位數(shù)

v8 源碼中的基準(zhǔn)元素選取更為復(fù)雜：如果數(shù)組長度不超過1000，則進(jìn)行基本的三數(shù)取中；如果數(shù)組長度超過1000，那么 v8 的處理是除去首尾的元素，對剩下的元素每隔200左右挑出一個元素，對這些元素排序，找出中間的那個，并用這個元素跟原數(shù)組首尾兩個元素一起進(jìn)行三數(shù)取中。

設(shè)想一下，一個數(shù)組里如果所有元素都相等，基準(zhǔn)元素不管怎么選都是一樣的，那么在分區(qū)的時候，必然出現(xiàn)除基準(zhǔn)元素外的其他元素都被分到同一個分區(qū)的情況，進(jìn)入最差性能的 case。

那么對于重復(fù)元素應(yīng)該怎么處理呢？
從性能的角度，如果發(fā)現(xiàn)一個元素與基準(zhǔn)元素相同，那么它應(yīng)該被記錄下來，避免后續(xù)再進(jìn)行不必要的比較。

function QuickSortWithPartitionDump(arr, fn, from, to) {
    from = from === void 0 ? 0 : from;
    to = to === void 0 ? arr.length - 1 : to;

    if (from >= to) {
        return arr;
    }

    let pivot = getPivot(arr, fn, from, to);
    let smallEnd = from;
    let bigBegin = to;
    let i = from + 1;

    while (i <= bigBegin) {
        let r = fn(arr[i], pivot);
        if (r < 0) {
            swap(arr, smallEnd++, i++);
        } else if (r > 0) {
            swap(arr, i, bigBegin--);
        } else {
            i += 1;
        }
    }

    QuickSortWithPartitionDump(arr, fn, from, smallEnd - 1);
    QuickSortWithPartitionDump(arr, fn, bigBegin + 1, to);

    return arr;
}

對于小數(shù)組，可能使用快速排序的速度還不如平均復(fù)雜度更高的插入排序，故而出于減少遞歸深度的考慮，數(shù)組長度較小時，使用插入排序算法。

function insertSort(arr, fn, from, to) {
    for (let i = from; i < to; i++) {
        for (let j = i + 1; j < to; j++) {
            let t = fn(arr[i], arr[j]);
            let r = (typeof t === "number" ? t : t ? 1 : 0) > 0;
            if (r) {
                let tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }

    return arr;
}

快速排序如果遞歸太深的話很可以出現(xiàn)“爆棧”，上面提到的對小數(shù)組采用插入排序算法，以及采用內(nèi)省排序算法都可以減少遞歸深度，不過 v8 引擎中還做了一些不太常見的優(yōu)化：每次分區(qū)后，v8 引擎會選擇元素少的分區(qū)進(jìn)行遞歸，而將元素多的分區(qū)直接通過循環(huán)處理，無疑可以大大減小遞歸深度。

由于快速排序時間復(fù)雜度的不穩(wěn)定性，David Musser 于1997設(shè)計(jì)了內(nèi)省排序法（Introsort），這個算法在快速排序的基礎(chǔ)上，監(jiān)控遞歸的深度：一旦長度為 n 的數(shù)組經(jīng)過 logn 層遞歸（快速排序算法最佳情況下的遞歸層數(shù)）還沒有結(jié)束的話，就認(rèn)為這次快速排序的效率可能不理想，轉(zhuǎn)而將剩余部分換用其他排序算法，通常使用堆排序算法（Heapsort，最差時間復(fù)雜度和最優(yōu)時間復(fù)雜度均為 O(nlogn)）。

筆者發(fā)現(xiàn) Safari 或者 iPhone 中 sort 方法不生效（不同瀏覽器實(shí)現(xiàn)機(jī)制差異），故判斷后進(jìn)行該方法的重寫處理，代碼如下：

;(function(w){
    if(/msie|applewebkit.+safari/i.test(w.navigator.userAgent)){
        var _sort = Array.prototype.sort;
        Array.prototype.sort = function(fn){
            if(!!fn && typeof fn === "function"){
                if(this.length < 2) return this;
                var i = 0, j = i + 1, l = this.length, tmp, r = false, t = 0;
                for(; i < l; i++){
                    for(j = i + 1; j < l; j++){
                        t = fn.call(this, this[i], this[j]);
                        r = (typeof t === "number" ? t : !!t ? 1 : 0) > 0 ? true : false;
                        if(r){
                            tmp = this[i];
                            this[i] = this[j];
                            this[j] = tmp;
                        }
                    }
                }
                return this;
            } else {
                return _sort.call(this);
            }
        };
    }
})(window);