1.快速排序的由來
快速排序是一種二分的排序算法，這種算法的誕生來自于對有序數(shù)組的觀察涛浙。我們假設(shè)有以下數(shù)組：
1康辑，2，3轿亮，4疮薇，5我注，6按咒，7但骨，8，9
這是一個已經(jīng)按照從小到大排序完畢的有序數(shù)組奔缠。觀察以上數(shù)組掠抬，取其中間數(shù)5，我們可以發(fā)現(xiàn)5以左的數(shù)1两波，2闷哆，3雨女，4均比5小，5以右的數(shù)6阳准，7，8馏臭，9均比5大。我們以5為分界線將數(shù)組分為兩部分：
1括儒，2，3乍狐，4
6固逗，7藕帜，8惜傲，9
分別取中間數(shù)3和8，我們可以得到同樣的結(jié)論：左邊的數(shù)總小于中間數(shù)盗誊，右邊的數(shù)總大于中間數(shù)。由此可見荒适，一個有序數(shù)列的每一個二分子數(shù)列總滿足中間數(shù)以左的數(shù)小于中間數(shù)开镣，中間數(shù)以右的數(shù)大于中間數(shù)。
快速排序的基本思想就是：
- 使完整數(shù)組滿足
段所有數(shù)小于
段所有數(shù)舅列，但A段與B段內(nèi)部不一定有序卧蜓。
| 3,2,1,4 | 7,9,6,8 |
- 使
段所有數(shù)小于
段所有數(shù)，
段所有數(shù)小于
段所有數(shù)榨惠，但每一小段內(nèi)不一定有序盛霎。
| 1,2 | 3,4 | 7,6 | 9,8 |
- 以此類推二分?jǐn)?shù)組，直到每個數(shù)組內(nèi)都只有一個元素時期揪，整個數(shù)組便變得有序了规个。
可見快速排序是一個典型的二分算法，且可以使用遞歸的方式實現(xiàn)诞仓。
2.快速排序的基本方法
我們以剛才舉例的數(shù)組的逆序列為例：
9，8活玲，7，6舒憾，5珍剑，4，3招拙，2，1
假如我們采用單向迭代的方法來完成快速排序饰序，取中間數(shù)為9规哪，之后掃描后面8個數(shù)字求豫。由于8個數(shù)字均小于9诉稍，我們只需要將9插到隊伍的最后。
8杯巨，7，6杜恰，5仍源，4，3笼踩，2，1掘而，9
再取中間數(shù)為8匾旭，掃描后面8個數(shù)字圃郊，發(fā)現(xiàn)只需要把8插到9的前面就行。以此類推色瘩，在數(shù)據(jù)規(guī)模為的情況下，需要
次插入居兆。
但是，這是在我們事先已經(jīng)知道有成塊的子串中所有的數(shù)均小于中間數(shù)的情況下得出的結(jié)論簇宽。實際情況下吧享，在我們考慮單獨的數(shù)時，這個數(shù)小于中間數(shù)并不意味著下一個數(shù)小于中間數(shù)钞它。所以我們每次選取中間數(shù)后需要維護(hù)兩個序列殊鞭，一個儲存比中間數(shù)小的數(shù)，一個儲存比中間數(shù)大的數(shù)操灿。每次掃描數(shù)，都要與中間數(shù)比較后卵酪，加入兩個序列中的一個當(dāng)中谤碳。每一次選取中間數(shù)溃卡，復(fù)制數(shù)都需要次操作蜒简，總共選取
個中間數(shù)的話搓茬，這趟快速排序的時間復(fù)雜度就是
。因此卷仑，我們必須保證所有數(shù)據(jù)位置的變換都在原數(shù)組內(nèi)部進(jìn)行。
我們又知道粘昨，假如有一排積木緊密排在一起，要將其中的一塊移到另一塊積木處张肾，就必須得把原來在該位置的積木拿開吞瞪。
令積木大小不同，如果我們要實現(xiàn)積木從左到右由小到大的排序芍秆，可以想象我們一開始將最左邊積木拿開，再從右往左找螟碎，如果見到了比拿開的積木更小的積木迹栓，就拿到最左邊的空位。這時右邊就空出來了一個積木的空位酥郭，我們再從左往右找愿吹，找到一塊比拿開的積木大的積木，放到右邊的空位……
直到空位出現(xiàn)在隊伍中間時犁跪，左邊的積木，盡管還不是從小到大排列的寝优，但至少都拿開的積木枫耳，也小于右邊的積木。我們再把拿開的積木放回空位钻心，就完成了第一次排序铅协。接著再對右邊的積木和左邊的積木重復(fù)同樣的操作，最終整個數(shù)組就會變成有序的狐史。
拿開的積木就是我們的基準(zhǔn)數(shù)坯钦，積木的大小就是數(shù)組中數(shù)字的大小，上面積木排序的過程其實就是數(shù)組快速排序的過程吟温。這樣的操作時間復(fù)雜度是多少呢？由于我們二分地選擇基準(zhǔn)數(shù)潘悼，基準(zhǔn)數(shù)的選擇是次爬橡，考慮最壞的情況，每一段數(shù)列中除了基準(zhǔn)數(shù)外的數(shù)中宾添，有一半的數(shù)需要移動柜裸，對于完整數(shù)列即
次，隨著數(shù)列二分疙挺，數(shù)據(jù)規(guī)模以
為公比縮小铐然，根據(jù)等比數(shù)列求和公式，得：
時，單邊總共移動次數(shù)為
呵萨，加上我們需要選擇
次基準(zhǔn)數(shù)叫倍，總的時間復(fù)雜度就是
。
3.快速排序的實現(xiàn)
static void quickSort(int s, int e)
{
if (s >= e)
return;
int mid = numbers[s],start = s,end=e;
while (s < e)
{
while (s < e)
{
if (numbers[e] > mid)
{
numbers[s++] = numbers[e];
break;
}
e--;
}
while (s < e)
{
if (numbers[s] < mid)
{
numbers[e--] = numbers[s];
break;
}
s++;
}
}
numbers[s] = mid;
quickSort(start, s - 1);
quickSort(s + 1, end);
}
