前言

快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實實用，因此也是大公司面試的首選。

介紹

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。

該方法的基本思想是：

1．先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。
2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。

雖然快速排序稱為分治法，但分治法這三個字顯然無法很好的概括快速排序的全部步驟。因此本篇對此做了新說明：挖坑填數(shù)+分治法：

內(nèi)容

??（例子）
以一個數(shù)組作為示例，取區(qū)間第一個數(shù)為基準(zhǔn)數(shù)。

初始時，i = 0; j = 9; X = a[i] = 72

由于已經(jīng)將a[0]中的數(shù)保存到X中，可以理解成在數(shù)組a[0]上挖了個坑，可以將其它數(shù)據(jù)填充到這來。

從j開始向前找一個比X小或等于X的數(shù)。當(dāng)j=8，符合條件，將a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++; 這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎么辦了？簡單，再找數(shù)字來填a[8]這個坑。這次從i開始向后找一個大于X的數(shù)，當(dāng)i=3，符合條件，將a[3]挖出再填到上一個坑中a[8]=a[3]; j--;

數(shù)組變?yōu)椋?/p>

i = 3; j = 7; X=72

再重復(fù)上面的步驟，先從后向前找，再從前向后找。

從j開始向前找，當(dāng)j=5，符合條件，將a[5]挖出填到上一個坑中，a[3] = a[5]; i++;

從i開始向后找，當(dāng)i=5時，由于i==j退出。

此時，i = j = 5，而a[5]剛好又是上次挖的坑，因此將X填入a[5]。

數(shù)組變?yōu)椋?/p>

可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它。因此再對a[0…4]和a[6…9]這二個子區(qū)間重復(fù)上述步驟就可以了。

對挖坑填數(shù)進(jìn)行總結(jié)

1．i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個坑a[i]。

2．j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個坑a[i]中。

3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中。

4．再重復(fù)執(zhí)行2，3二步，直到i==j，將基準(zhǔn)數(shù)填入a[i]中。

照著這個總結(jié)很容易實現(xiàn)挖坑填數(shù)的代碼：

int AdjustArray(int s[], int l, int r) //返回調(diào)整后基準(zhǔn)數(shù)的位置
{
    int i = l, j = r;
    int x = s[l]; //s[l]即s[i]就是第一個坑
    while (i < j)
    {
        // 從右向左找小于x的數(shù)來填s[i]
        while(i < j && s[j] >= x) 
            j--;  
        if(i < j) 
        {
            s[i] = s[j]; //將s[j]填到s[i]中，s[j]就形成了一個新的坑
            i++;
        }

        // 從左向右找大于或等于x的數(shù)來填s[j]
        while(i < j && s[i] < x)
            i++;  
        if(i < j) 
        {
            s[j] = s[i]; //將s[i]填到s[j]中，s[i]就形成了一個新的坑
            j--;
        }
    }
    //退出時，i等于j。將x填到這個坑中。
    s[i] = x;

    return i;
}

再寫分治法的代碼：

void quick_sort1(int s[], int l, int r)
{
    if (l < r)
    {
        int i = AdjustArray(s, l, r);//先成挖坑填數(shù)法調(diào)整s[]
        quick_sort1(s, l, i - 1); // 遞歸調(diào)用 
        quick_sort1(s, i + 1, r);
    }
}

這樣的代碼顯然不夠簡潔，對其組合整理下：

//快速排序
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); //將中間的這個數(shù)和第一個數(shù)交換 參見注1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 從右向左找第一個小于x的數(shù)
                j--;  
            if(i < j) 
                s[i++] = s[j];
            
            while(i < j && s[i] < x) // 從左向右找第一個大于等于x的數(shù)
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 遞歸調(diào)用 
        quick_sort(s, i + 1, r);
    }
}

注1，有的書上是以中間的數(shù)作為基準(zhǔn)數(shù)的，要實現(xiàn)這個方便非常方便，直接將中間的數(shù)和第一個數(shù)進(jìn)行交換就可以了。

以上原文地址：http://blog.csdn.net/morewindows/article/details/6684558

補(bǔ)充：

快速排序算法有三種選擇基準(zhǔn)的方法：

1. 取序列中的第一個或最后一個元素作為基準(zhǔn)
2. 取序列中任意一個元素作為基準(zhǔn)
3. 取序列中中間元素作為基準(zhǔn)

第1種 （上文介紹是就是第一種)

如果輸入序列（上文中的數(shù)組）是隨機(jī)的，處理時間可以接受的。如果數(shù)組已經(jīng)有序時，此時的分割就是一個非常不好的分割。因為每次劃分只能使待排序序列減一，此時為最壞情況，快速排序淪為起泡排序，時間復(fù)雜度為Θ(n^2)。而且，輸入的數(shù)據(jù)是有序或部分有序的情況是相當(dāng)常見的。因此，使用第一個元素作為樞紐元是非常糟糕的，為了避免這個情況，就引入了下面兩個獲取基準(zhǔn)的方法。

第2種 隨機(jī)選取基準(zhǔn)

/*隨機(jī)選擇樞軸的位置，區(qū)間在low和high之間*/
int SelectPivotRandom(int arr[],int low,int high)
{
    //產(chǎn)生樞軸的位置
    srand((unsigned)time(NULL));
    int pivotPos = rand()%(high - low) + low;

    //把樞軸位置的元素和low位置元素互換，此時可以和普通的快排一樣調(diào)用劃分函數(shù)
    swap(arr[pivotPos],arr[low]);
    return arr[low];
}

測試數(shù)據(jù)分析：:這是一種相對安全的策略。由于樞軸的位置是隨機(jī)的，那么產(chǎn)生的分割也不會總是會出現(xiàn)劣質(zhì)的分割。在整個數(shù)組數(shù)字全相等時，仍然是最壞情況，時間復(fù)雜度是O(n^{2）。實際上，隨機(jī)化快速排序得到理論最壞情況的可能性僅為1/(2}n）。所以隨機(jī)化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達(dá)到O(nlogn）的期望時間復(fù)雜度。一位前輩做出了一個精辟的總結(jié)：“隨機(jī)化快速排序可以滿足一個人一輩子的人品需求?！?/p>

第3種 選取左，中，右三個元素的 “中值” 為基準(zhǔn)

分析：最佳的劃分是將待排序的序列分成等長的子序列，最佳的狀態(tài)我們可以使用序列的中間的值，也就是第N/2個數(shù)?？墒?，這很難算出來，并且會明顯減慢快速排序的速度。這樣的中值的估計可以通過隨機(jī)選取三個元素并用它們的中值作為樞紐元而得到。事實上，隨機(jī)性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數(shù)中值分割法消除了預(yù)排序輸入的不好情形，并且減少快排大約14%的比較次數(shù)

??（例子）：待排序序列為：8 1 4 9 6 3 5 2 7 9

左邊為：8，右邊為9，中間為6.

我們這里取三個數(shù)排序后，中值那個數(shù)作為樞軸，則樞軸為8

注意：

在選取中軸值時，可以從由左中右三個中選取擴(kuò)大到五個元素中或者更多元素中選取，一般的，會有（2t＋1）平均分區(qū)法（median-of-(2t+1)，三平均分區(qū)法英文為median-of-three）。

// 從序列的左，中，右三個元素中取出中值，然后放到最左側(cè)。
// 更科學(xué)的選擇主元，提高了快速排序的效率
 void median3(int arr[], int l, int r)
 {
     // 選擇排序的思路找出最大值
     int max = r;
     int mid = (l + r) / 2;
     if (arr[mid] > arr[max])
     {
         max = mid;
     }
     if (arr[l] > arr[max])
     {
         max = l;
     }
     if (max != r)
     {
         int temp = arr[max];
         arr[max] = arr[r];
         arr[r] = temp;
     }
     // 以上代碼：確定出三個中的最大值，然后放到最右側(cè)
     // 下面再比較max和l位置的元素，找出三個中的中值
     if (max != r && arr[max] > arr[l])
     {
         // 將中值放到最左側(cè)
         int temp = arr[max];
         arr[max] = arr[l];
         arr[l] = temp;
     }else
     {
         // 在次分支內(nèi)，最左側(cè)本來就是中值
     }
 }
 // 一趟劃分，采用三者取中值作主元，剩下操作按前面的（第1種）方式進(jìn)行排序了

三種方法總結(jié)：

測試數(shù)據(jù)

測試數(shù)據(jù)分析：針對隨機(jī)數(shù)組，使用三數(shù)取中選擇樞軸+插排，效率還是可以提高一點，真是針對已排序的數(shù)組，是沒有任何用處的。因為待排序序列是已經(jīng)有序的，那么每次劃分只能使待排序序列減一。此時，插排是發(fā)揮不了作用的。所以這里看不到時間的減少。

備注：

后半部分轉(zhuǎn)自：http://blog.csdn.net/insistgogo/article/details/7785038

最后

看了很多關(guān)于快速排序算法的介紹，都看的稀里糊涂的，直到看到前半部分的博客，通俗易懂，瞬間理解，本想自己寫心得，由于最近事多先在此分享給大家，后續(xù)有時間在總結(jié)自己的心得