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

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

基本思想：

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

下面看圖：這是一個(gè)待排序的序列

第一步，選擇基數(shù)，一般選擇序列的首個(gè)元素為基數(shù)，這里選擇首個(gè)元素5為基數(shù)，并記錄在臨時(shí)變量中，記錄此時(shí)序列的起始位置下標(biāo)i=0，結(jié)束位置下標(biāo)j=8；

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

第三步，從位置i開(kāi)始向右找，每移動(dòng)一個(gè)位置i++，當(dāng)找出一個(gè)大于或等于基數(shù)的元素時(shí)把該元素放入位置j，同時(shí)j--；如下圖：

第四步，重復(fù)執(zhí)行第二、第三步直至i==j時(shí)結(jié)束，然后把基數(shù)放入位置i；最后如下圖：

第五步，將基數(shù)左右兩邊的序列重復(fù)執(zhí)行第一、二、三、四、五步直至最后分解的所有序列中元素?cái)?shù)量都為1則排序結(jié)束序列有序。

有了上面的分析過(guò)程下面看代碼實(shí)現(xiàn)：

/// <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的數(shù)來(lái)填intArray[i]            while (i < j && intArray[j] >= x)            {                j--;            }            if (i < j)            {                intArray[i] = intArray[j];                i++;            }            //從左向右找大于或等于x的數(shù)來(lái)填intArray[j]            while (i < j && intArray[i] < x)            {                i++;            }            if (i < j)            {                intArray[j] = intArray[i];                j--;            }        }//退出循環(huán)時(shí) i==j        intArray[i] = x;        QuickSort(intArray, left, i - 1);        QuickSort(intArray, i + 1, right);    }}
當(dāng)調(diào)用時(shí)left傳入序列開(kāi)始的下標(biāo)即0，right傳入序列結(jié)束的下標(biāo)即（長(zhǎng)度-1）；
以上就是快速排序的實(shí)現(xiàn)。