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 |
- 使
段內(nèi)
段所有數(shù)小于
段所有數(shù),
段內(nèi)
段所有數(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);
}