原文地址http://www.cnblogs.com/liukemng/p/3721066.html

快速排序是基于分治思想的一種排序算法，就像該方法的名字一樣，速度比較快，所以叫做快速排序；它的平均時間復雜度為O(N*logN)，最壞時間復雜度為O(n2)。快速排序也有很多優化的版本，比如在排序時基數的選擇等等…下面就說一下一般的快速排序的實現。

基本思想：

快速排序的基本思想就是，先從待排序的序列中任選一個元素作為基數，然后將序列中的其他小于基數的元素放在基數的左邊，大于或等于基數的元素放在基數的右邊，第一次的時候雖然序列中的左半部分中的元素都小于基數，序列中右半部分中的元素都大于或等于基數，但這兩部分內部元素并不一定是有序的，不要緊，只要我們把左右兩半部分序列分別繼續執行第一步，這樣不斷的把序列分解然后排序，直到分到最后所分解的序列中元素的數量都為1，則排序完成序列有序。

下面看圖：這是一個待排序的序列

第一步，選擇基數，一般選擇序列的首個元素為基數，這里選擇首個元素5為基數，并記錄在臨時變量中，記錄此時序列的起始位置下標i=0，結束位置下標j=8；

第二步，從位置j開始向左找，每移動一個位置j--，當找出一個小于基數的元素時把該元素放入剛才選擇基數的位置即（i=0），同時使i++；如下圖：

第三步，從位置i開始向右找，每移動一個位置i++，當找出一個大于或等于基數的元素時把該元素放入位置j，同時j--；如下圖：

第四步，重復執行第二、第三步直至i==j時結束，然后把基數放入位置i；最后如下圖：

第五步，將基數左右兩邊的序列重復執行第一、二、三、四、五步直至最后分解的所有序列中元素數量都為1則排序結束序列有序。

有了上面的分析過程下面看代碼實現：

/// <summary>/// 快速排序/// </summary>/// <param name="intArray"></param>/// <param name="left"></param>/// <param name="right"></param>public static void QuickSort(int[] intArray, int left, int right){    if (left < right)    {        int i = left, j = right, x = intArray[left];        while (i < j)        {            //從右向左找小于x的數來填intArray[i]            while (i < j && intArray[j] >= x)            {                j--;            }            if (i < j)            {                intArray[i] = intArray[j];                i++;            }            //從左向右找大于或等于x的數來填intArray[j]            while (i < j && intArray[i] < x)            {                i++;            }            if (i < j)            {                intArray[j] = intArray[i];                j--;            }        }//退出循環時 i==j        intArray[i] = x;        QuickSort(intArray, left, i - 1);        QuickSort(intArray, i + 1, right);    }}
當調用時left傳入序列開始的下標即0，right傳入序列結束的下標即（長度-1）；
以上就是快速排序的實現。