最近遇到排序算法比較多，首先是快排，V8實(shí)現(xiàn)了一份快排，大部分的瀏覽器也是用快排的，快排是不穩(wěn)定排序，而且最差的時(shí)間復(fù)雜度其實(shí)是o(n^2),好像歸并排序也有被其他瀏覽器實(shí)現(xiàn)。然后上次一個(gè)面試官問我基本有序數(shù)組用什么排序，我想了一下，其實(shí)我可以寫個(gè)提前終止的冒泡，嘿嘿。

1. 快速排序

快排的基礎(chǔ)就是選擇一個(gè)基準(zhǔn)的元素，然后根據(jù)這個(gè)元素來劃分?jǐn)?shù)組，分成大于和小于這個(gè)元素的兩部分,然后這個(gè)元素的位置就是確定的，然后再遞歸確定大于和小于這個(gè)元素的部分。
快排在基本有序的情況下，如果正序交換次數(shù)會(huì)比較少，但是感覺時(shí)間復(fù)雜度趨向于0(n^2)。
V8雖然是用快排，但是實(shí)現(xiàn)了插入排序，用來處理數(shù)組大小小于22的情況，

In-place QuickSort algorithm. For short (length <= 22) arrays, insertion sort is used for efficiency.

阮一峰實(shí)現(xiàn)了一份快排的代碼，但是個(gè)人覺得他沒有很好地利用快排空間復(fù)雜度的優(yōu)勢(shì)，甚至他用數(shù)組的函數(shù)的時(shí)候，其實(shí)也要考慮額外的復(fù)雜度，所以個(gè)人覺得時(shí)間復(fù)雜度也超了。所以我根據(jù)《算法導(dǎo)論》的思路實(shí)現(xiàn)了一份JavaScript版本，優(yōu)點(diǎn)嘛，基本實(shí)現(xiàn)了沒有額外空間復(fù)雜度，除了遞歸的O(log(n))。

function quick_sort(arr) {
    function swap(i,j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    function split(start,end) {
        var cmp = arr[end];
        var loc = start;
        for(var i=start;i<end;i++){
            if(arr[i]<cmp){
                swap(loc,i);
                loc++;
            }
        }
        swap(loc, end);
        return loc;
    }
    
    function helper(start,end) {
        if(start<end){  //記得判斷end要大于start
            var q = split(start,end);
            helper(start,q-1);
            helper(q+1,end);
        }
    }
    helper(0,arr.length-1);
    return arr;
}

2. 歸并排序

歸并排序的思想也比較簡(jiǎn)單，主要是實(shí)現(xiàn)二路歸并，但是歸并算法是無法無視額外的空間復(fù)雜度的，也就是二路歸并的時(shí)候，需要兩個(gè)子數(shù)組，以及一個(gè)歸并后的數(shù)組，他們是無法重合的。
上次面試官讓我不用遞歸和棧來寫一份歸并，其實(shí)就是用for循環(huán)模擬，第一次寫的時(shí)候，空間利用率并不是很高，現(xiàn)在給一份優(yōu)化的版本，主要是把兩個(gè)數(shù)組歸并后生成的新數(shù)組去掉，然后用原始數(shù)組來存儲(chǔ)新數(shù)組。

function merge_sort(arr) {
    function merge(arr1,arr2,loc) {
        var n1 = arr1.length;
        var n2 = arr2.length;
        var i=0,j=0;
        arr1.push(Number.POSITIVE_INFINITY);
        arr2.push(Number.POSITIVE_INFINITY);
        while(i+j<n1+n2){
            if(arr1[i]<arr2[j]){
                arr[loc] = arr1[i];
                i++;
            }else{
                arr[loc] = arr2[j];
                j++;
            }
            loc++;
        }
    }

    var nn = arr.length;
    var merge_length = 1;
    while(merge_length<nn) {
        for (var i = 0; i + 2 * merge_length < nn; i = i + 2 * merge_length) {
            merge(arr.slice(i,i+merge_length),arr.slice(i+merge_length,i+2*merge_length),i);
        }
        if(i+merge_length<nn){
            merge(arr.slice(i,i+merge_length),arr.slice(i+merge_length,nn),i);
        }
        merge_length *=2;
    }
    return arr;
}

還有一種是用遞歸來實(shí)現(xiàn)，不過感覺沒有嚴(yán)格按照遞歸的1，2，4這樣的順序進(jìn)行合并，不過思路是差不離的。

function merge_sort(arr) {
    function merge(arr1,arr2,loc) {
        var n1 = arr1.length;
        var n2 = arr2.length;
        var i=0,j=0;
        arr1.push(Number.POSITIVE_INFINITY);
        arr2.push(Number.POSITIVE_INFINITY);
        while(i+j<n1+n2){
            if(arr1[i]<arr2[j]){
                arr[loc] = arr1[i];
                i++;
            }else{
                arr[loc] = arr2[j];
                j++;
            }
            loc++;
        }
    }
    function helper(start,end) {
        if (start < end) {
            var mid = Math.floor((start + end) / 2);
            helper(start, mid);
            helper(mid + 1, end);
            merge(arr.slice(start, mid + 1), arr.slice(mid + 1, end+1), start);
        }
    }
    helper(0,arr.length-1);
    return arr;
}