Javascript和快速排序

這里以遞歸為例，參考自慕課網(wǎng)劉波波老師的C++版本實現(xiàn)

普通快排

上過大學數(shù)據(jù)結(jié)構(gòu)課程的人都知道，快速排序的核心就是選定一個哨兵，然后把它作為標準，對數(shù)據(jù)進行操作，把小的放前面，把大的放后面。然后執(zhí)行這個過程若干次，就得到了最終的結(jié)果。
這個過程，實踐了算法中的分治法，即把復(fù)雜的模塊分成幾個簡單的模塊分而治之，達到事半功倍的效果。
在這里，我推薦一個算法可視化網(wǎng)站：http://zh.visualgo.net/zh/sorting
很多常見的算法可以在上面快速的理解處理過程。
代碼如下：

var quickSort = function (arr) {
    __quickSort(arr, 0, arr.length - 1);
    return arr;
}
var __quickSort = function (arr, start, end) {
    if (start > end) {
        return;
    }
    // p是哨兵排序完畢時的位置
    var p = partition(arr, start, end);
    __quickSort(arr, start, p - 1);
    __quickSort(arr, p + 1, end);
    return arr;
}

function partition(arr, start, end) {
    // v是哨兵
    var v = arr[start];
    // j是分界線
    var j = start;
    //從第二個元素開始比較
    for (var i = start + 1; i <= end; i++) {
        if (arr[i] < v) {
            //如果第i個元素比哨兵小，就和右邊的大數(shù)交換，j就往右移了一位
            [arr[j + 1], arr[i]] = [arr[i], arr[j + 1]];
            // var tmp = arr[start];
            // arr[start] = arr[j];
            // arr[j] = tmp;
            j++;
        }
    }
    //把哨兵放在本應(yīng)屬于他的位置。
    [arr[start], arr[j]] = [arr[j], arr[start]];
    // var tmp = arr[start];
    // arr[start] = arr[j];
    // arr[j] = tmp;
    return j;
}

快排性能測試

怎么知道我們算法的性能呢？我們可以新建一個模塊，自動生成測試用例進行測試并且打印出耗時。
test.js

/**
 * 
 * 自定義測試用例
 * @param {any} n 元素個數(shù)
 * @param {any} rangeL  范圍內(nèi)最小數(shù)，開區(qū)間 
 * @param {any} rangeH  范圍內(nèi)最大數(shù)，開區(qū)間
 * @returns arr 數(shù)組
 */
function genTest(n, rangeL, rangeH) {
    if (rangeH < rangeL) {
        return;
    }
    var arr = [];
    for (var i = 0; i < n; i++) {
        arr.push(Math.floor(Math.random() * (rangeH - rangeL)) + rangeL);
    }
    return arr;
}

/**
 * 
 * 耗時計算
 * @param {any} func 要測試的回調(diào)函數(shù)
 * @param {any} n 元素個數(shù)
 * @param {any} [m=n] 最大值，默認為n
 */
function dif(func,n,m=n) {
    console.time(`${func.name}算法耗時`);
    func(genTest(n, 0, m));
    console.timeEnd(`${func.name}算法耗時`);    
}

exports.genTest = genTest;
exports.dif = dif;

這里有一個genTest函數(shù)用于產(chǎn)生一個數(shù)組，還有一個dif函數(shù)用于打印耗時。
然后在之前寫的代碼里導(dǎo)入,測試一個100萬個數(shù)據(jù)的程序：

var test = require('./test');
...
test.dif(quickSort, 1000000)

解構(gòu)賦值交換法快排耗時

傳統(tǒng)交換變量快排耗時

優(yōu)化快排

快排常常有兩種邊界情況需要被考慮：
1.如果待排序的數(shù)組是有序的，復(fù)雜度會到O(n^2)。
2.數(shù)組元素重復(fù)個數(shù)過多也會造成性能上的損耗。
所以針對這兩種情況要進行優(yōu)化：哨兵要隨機選，針對重復(fù)的元素還要再加一個指針。

三路快排

這種快排通常被人叫做三路快排，因為它的代碼中有三個指針，分別標識著小于哨兵的部分/等于哨兵的部分/大于哨兵的部分。

代碼如下：

var test = require('./test');

//更加先進的：三路快排,可能是交換性能消耗大
var quickSortThreeWays = function (arr) {
    var len = arr.length;
    __quickSortThreeWays(arr, 0, len - 1);
    return arr;
}

function __quickSortThreeWays(arr, start, end) {
    if (start > end) {
        return;
    }
    var rand = Math.round(Math.random() * (end - start));
    //partition
    [arr[start], arr[rand + start]] = [arr[rand + start], arr[start]];
    var v = arr[start];

    var lt = start; //arr[start+1...lt]<v
    var gt = end + 1; //arr[gt...end]>v
    var i = start + 1;
    while (i < gt) {
        if (arr[i] < v) {
            [arr[i], arr[lt + 1]] = [arr[lt + 1], arr[i]];
            lt++;
            i++;
        } else if (arr[i] > v) {
            [arr[i], arr[gt - 1]] = [arr[gt - 1], arr[i]];
            gt--;
        } else { //arr[i]==v
            i++;
        }
    }
    [arr[start], arr[lt]] = [arr[lt], arr[start]];
    __quickSortThreeWays(arr, start, lt - 1);
    __quickSortThreeWays(arr, gt, end);
}

可以看到lt——i之間是小于哨兵的、i——gt之間是等于哨兵的，gt——end是大于哨兵的。

//測試三路快排性能
test.dif(quickSortThreeWays, 1000000)

三路快排耗時.png

由于我這里大量使用了解構(gòu)賦值交換元素，所以也造成了性能上的損耗，再加上js本身不太適合實現(xiàn)底層算法，所以看上去還沒有普通快排快，不過在C++寫法中是絕對快出一籌的。

特殊情況

大量重復(fù)元素

我們把數(shù)組限定在0~10的整數(shù)范圍內(nèi)，同樣生成一百萬個。

三路快排重復(fù)元素耗時.png

快排重復(fù)元素耗時.png

快排解構(gòu)賦值交換元素耗時.png

test.dif(quickSort, 1000000,100)
test.dif(quickSortThreeWays, 1000000,100)

可以看出這時候三路快排已經(jīng)比快排快了，而且還是沒用解構(gòu)賦值的快排，如果用解構(gòu)賦值普通快排會溢出。
至于近乎有序的數(shù)組大家可以自己嘗試寫一個測試用例生成來測試~

其他寫法

阮一峰前輩的博客里也有相關(guān)的實現(xiàn)，因為用的js原生api比較多，所以我稱它為js寫法，其實還有很多寫法，這里就不一一列舉了

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

可以看出，阮前輩使用了splice、concat等眾多js本身的api，不過語義上好理解一些，那性能如何呢？我們來看看：

JS快排.png

可以看出，這種寫法的性能是比較低的。那兩種特殊情況同理。

JS的sort()函數(shù)

不過實際上，JS早已幫我們內(nèi)置好了排序函數(shù)，那就是sort()函數(shù)。關(guān)于sort()函數(shù)的實現(xiàn)，chrome是在元素大于10個時使用快排，小于10個的時候使用插入排序，其他的瀏覽器有用歸并排序的，有用選擇排序的...
那sort函數(shù)的性能如何呢？
我們來看看：

var jsSort = function (arr) {
    return arr.sort((a, b) => { return a - b; });
}

test.dif(jsSort, 1000000);

sort函數(shù)耗時.png

這是node環(huán)境下的sort，可以看出，性能也不咋地，有興趣的朋友可以去各個瀏覽器跑一下看看測試結(jié)果~~~
總之，快排雖然在jser們手下不需要手動實現(xiàn)，但是了解其中蘊含的算法思想是極為重要的。