在上一篇中再愈，回顧了一下針對(duì)選擇排序的優(yōu)化算法——堆排序。堆排序的時(shí)間復(fù)雜度為O(nlogn)馋艺，而快速排序的時(shí)間復(fù)雜度也是O(nlogn)侧纯。但是快速排序在同為O(n*logn)的排序算法中，效率也是相對(duì)較高的碍讨，而且快速排序使用了算法中一個(gè)十分經(jīng)典的思想——分治法治力；因此掌握快速排序還是很有必要的。
快速排序的基本思想如下：
- 在一組無序元素中勃黍，找到一個(gè)數(shù)作為基準(zhǔn)數(shù)宵统。
- 將大于它的數(shù)全部移動(dòng)到它的右側(cè)，小于它的全部移動(dòng)到右側(cè)覆获。
- 在分成的兩個(gè)區(qū)中马澈，再次重復(fù)1到2 的步驟，直到所有的數(shù)全部有序
下面還是來看一個(gè)例子
[3,6,1,2,8,4,7]
首先選取一個(gè)基準(zhǔn)數(shù)弄息，一般選擇序列最左側(cè)的數(shù)為基準(zhǔn)數(shù)痊班，也就是3，將小于3的數(shù)移動(dòng)到3的左邊摹量，大于3的移動(dòng)到3的右邊涤伐，得到如下的序列
[2,1,3,6,8,4,7]
接著針對(duì)左側(cè)的[2, 1] 這個(gè)序列和 [6, 8, ,4, 7]這兩個(gè)序列再次執(zhí)行這種操作，直到所有的數(shù)都變?yōu)橛行驗(yàn)橹埂?/p>
知道了具體的思路下面就是寫算法了缨称。
void QSort(int a[], int n)
{
int nIdx = adjust(a, 0, n -1);
//針對(duì)調(diào)整之后的數(shù)據(jù)左右兩側(cè)序列都再次進(jìn)行調(diào)整
if(nIdx != -1)
{
QSort(&a[0], nIdx);
QSort(&a[nIdx + 1], n - nIdx - 1);
}
}
這里定義了一個(gè)函數(shù)作為快速排序的函數(shù)凝果，函數(shù)需要傳入序列的首地址以及序列中間元素的長(zhǎng)度。在排序函數(shù)中只需要關(guān)注如何進(jìn)行調(diào)整即可睦尽。
這里進(jìn)行了一個(gè)判斷器净，當(dāng)調(diào)整函數(shù)返回-1時(shí)表示不需要調(diào)整，也就是說此時(shí)已經(jīng)都是有序的了骂删，這個(gè)時(shí)候就不需要調(diào)整了掌动。
程序的基本框架已經(jīng)完成了，剩下的就是如何編寫調(diào)整函數(shù)了宁玫。調(diào)整的算法如下:
-
首先定義兩個(gè)指針粗恢，指向最右側(cè)和最左側(cè)，最左側(cè)指針指向基準(zhǔn)數(shù)所在位置
-
先從右往左掃描欧瘪，當(dāng)發(fā)現(xiàn)右側(cè)數(shù)小于基準(zhǔn)值時(shí)眷射，將基準(zhǔn)值位置的數(shù)替換為該數(shù)，并且立刻從左往右掃描，直到找到一個(gè)數(shù)大于基準(zhǔn)值妖碉，再次進(jìn)行替換
-
接著再次從右往左掃描涌庭，直到找到小于基準(zhǔn)數(shù)的值；并再次改變掃描順序欧宜，直到調(diào)整完畢
最后直到兩個(gè)指針重合坐榆，此時(shí)重合的位置就是基準(zhǔn)值所在位置
根據(jù)這個(gè)思路，可以編寫如下代碼
int QuickSort(int a[], int nLow, int nHigh)
{
if (nLow >= nHigh)
{
return -1;
}
int tmp = a[nLow];
int i = nLow;
int j = nHigh;
while (i != j)
{
//先從右往左掃描冗茸，只到找到比基準(zhǔn)值小的數(shù)
//將該數(shù)放到基準(zhǔn)值的左側(cè)
while (a[j] > tmp && j > i)
{
j--;
}
if (a[j] < tmp)
{
a[i]= a[j];
i++;
}
//接著從左往右掃描席镀，直到找到比基準(zhǔn)值大的數(shù)
//將該數(shù)放入到基準(zhǔn)值的右側(cè)
while (a[i] < tmp && i < j)
{
i++;
}
if (a[i] > tmp)
{
a[j] = a[i];
j--;
}
}
a[i] = tmp;
return i;
}
到此已經(jīng)完成了快速排序的算法編寫了。
在有大量的數(shù)據(jù)需要進(jìn)行排序時(shí)快速排序的效果比較好夏漱，如果數(shù)據(jù)量小豪诲，或者排序的序列已經(jīng)是一個(gè)逆序的有序序列，它退化成O(n^2)挂绰。
快速排序是一個(gè)不穩(wěn)定的排序算法屎篱。
<hr />
