快排，快忘光了，一直因?yàn)樘α藳]有復(fù)習(xí)，導(dǎo)致的后果就是今天阿里打了電話一面，問了快排，我就只能說：emmm，選一個(gè)基準(zhǔn)值，然后遍歷數(shù)組，把小的換到前面，把大的換到后面，然后遞歸……
面試官說：沒關(guān)系，了解原理就好。
???謝謝面試官的安慰。

廢話少說，開始吧。
ps：用JS寫的代碼。

快速排序（quicksort）的主要思想就是：選擇一個(gè)基準(zhǔn)元素，把小于基準(zhǔn)的元素全部移到左邊，大于基準(zhǔn)的元素移到右邊。然后對(duì)左邊和右邊的元素分別再進(jìn)行排序，如此循環(huán)到每個(gè)小分組只剩下一個(gè)元素為止。

對(duì)元素的劃分有兩種算法。一個(gè)是Lomuto算法。

function LomutoPartition(a,left,right){
    var p=a[left];
    var s=left;
    //交換函數(shù)，交換數(shù)組兩個(gè)元素
    function swap(a,x,y){
        var temp=a[x];
        a[x]=a[y];
        a[y]=temp;
    }
   //開始遍歷數(shù)組
    for(var i=left+1;i<=right;i++){
        if(a[i]<p){
            s++;
            swap(a,s,i);
        }
    }
    swap(a,s,left); // 基準(zhǔn)值放中間
    return s;
}

把第一個(gè)元素作為基準(zhǔn)元素。從第二個(gè)開始遍歷余下的元素，a[i]>=p則繼續(xù)往前走，當(dāng)遇到一個(gè)小于p的元素時(shí)，就停下來，將s增加1，再交換a[s]，a[i]的元素。這樣就保證比p小的元素永遠(yuǎn)在s左邊，比p大的元素永遠(yuǎn)在s右邊。

循環(huán)結(jié)束后，再交換a[s]和a[left]的值。使基準(zhǔn)元素成為分界點(diǎn)。

另一個(gè)算法是Hoare算法。Hoare就是提出快速排序思想的人，圖靈獎(jiǎng)得主。

function HoarePartition(a,left,right){
    if(left<right){
        var key=a[left];
        var i=left+1;//跟蹤比基準(zhǔn)小的元素，從左到右遍歷
        var j=right;//跟蹤比基準(zhǔn)大的元素，從右到左遍歷
       //判斷i是否溢出（注意上面i=left+1，有溢出可能）
        if(i<=right){
            while(i<=j){
                while(a[i]<key&&i<right) i++;//依舊檢查i是否會(huì)溢出
                while(a[j]>key) j--;
                a[j]={x:a[i],y:(a[i]=a[j])}.x;//此交換語句相當(dāng)于上文的swap函數(shù)
            }
            a[j]={x:a[i],y:(a[i]=a[j])}.x;//此時(shí)j<=i，所以應(yīng)取消最后一次交換
            a[left]={x:a[j],y:(a[j]=a[left])}.x;
        }
    }
}

變量i跟蹤小于基準(zhǔn)的元素，從左到右遍歷，遇到大于等于基準(zhǔn)的元素就停下來。j跟蹤大于基準(zhǔn)的元素，從右到左遍歷，遇到小于基準(zhǔn)的元素就停下來，然后交換a[i]和a[j]。直到i，j相遇。再把基準(zhǔn)元素和a[j]交換。比較麻煩的就是每次都要判斷i是否溢出。

兩個(gè)劃分算法效率是一樣的，個(gè)人認(rèn)為Lomuto算法比較容易理解。

有了劃分算法之后，要寫快速排序就容易多了。

下面是用js寫的原地排序（in-place）：

function quickSort(a){
    //交換函數(shù)，交換數(shù)組兩個(gè)元素
    function swap(a,x,y){
        var temp=a[x];
        a[x]=a[y];
        a[y]=temp;
    }
    //劃分算法
    function LomutoPartition(a,left,right){
        var p=a[left];
        var s=left;
        for(var i=left+1;i<=right;i++){
            if(a[i]<p){
                s++;
                swap(a,s,i);
            }
        }
        swap(a,s,left);
        return s;
    }
    //遞歸邏輯
    function sort(a,left,right){
        if(left>=right) return;
        var s=LomutoPartition(a,left,right);
        sort(a,left,s-1);
        sort(a,s+1,right);
    }
    sort(a,0,a.length-1);
}

還有另一種比較有js特色的快速排序?qū)崿F(xiàn)，代碼如下：

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];//把基準(zhǔn)元素切出來
　　var left = [];//存放小于基準(zhǔn)的元素
　　var right = [];//存放大于等于基準(zhǔn)的元素
　　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));//把切開后的數(shù)組連接起來
};

不過這種實(shí)現(xiàn)有一個(gè)很大的缺點(diǎn)，就是很耗內(nèi)存，對(duì)一個(gè)有n個(gè)元素的數(shù)組進(jìn)行排序，每一次遞歸都要新建兩個(gè)數(shù)組來存放兩邊的元素，最好情況下遞歸循環(huán)log n次，每次需要n個(gè)元素的空間，因此需要額外n(log n)的空間，加上創(chuàng)建數(shù)組需要一些額外開銷。因此這種方法對(duì)于大數(shù)組而言就不合適了。

關(guān)于快速排序的效率：

1. 最好情況下，每次都剛好平均分為兩個(gè)相同長度的分組，遞歸循環(huán) log n 次， 鍵值比較次數(shù)為C(n)=2*C(n/2)+n,C(1)=0
2. 最壞情況下，每次數(shù)組都會(huì)分成一邊長度為0，一邊長度為n-1的兩個(gè)分組，遞歸循環(huán) n-1次，鍵值比較次數(shù)為 n+(n-1)+(n-2)+……+1
3. 平均情況下，鍵值比較次數(shù)約等于 1.39nlog n

所以它們的效率分別是：

快排效率

關(guān)于快速排序的優(yōu)化：

1. 更好的基準(zhǔn)元素選擇方法。比較有名的是三平均劃分法（median-of-three method），以數(shù)組最左邊，最右邊，以及最中間元素的中位數(shù)作為基準(zhǔn)元素。上文提過平均情況下快速選擇的效率大約是1.39nlog n，根據(jù)維基百科，使用三平均劃分法能使效率達(dá)到1.188nlog n 左右。
2. 當(dāng)數(shù)組足夠小的時(shí)候（5-15），改用插入排序方法?；蛘咴诳焖倥判蜻f歸至每個(gè)分組都足夠小的時(shí)候，停止遞歸，然后對(duì)整個(gè)近乎有序的數(shù)組實(shí)行插入排序。
3. 先遞歸比較小的分組，然后對(duì)大的另一個(gè)分組使用尾遞歸，減少堆棧。