你所不知道的快速排序(js實(shí)現(xiàn))

注:本文是在看了兩篇大牛的博客后睹耐,通過整理供自己學(xué)習(xí)快速排序所做筆記惠窄,分享出來方便大家學(xué)習(xí)设塔。如需進(jìn)一步了解可以查看文中博客鏈接徘禁。

一. 快速排序是什么

快速排序是圖靈獎(jiǎng)得主C. A. R. Hoare(1934--)于1960時(shí)提出來的。

快速排序是對(duì)冒泡排序的一種改進(jìn)千贯。它的基本思想是:通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分屯仗,其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序搔谴,整個(gè)排序過程可以遞歸進(jìn)行魁袜,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

整個(gè)排序過程只需要三步:

(1)在數(shù)據(jù)集之中敦第,選擇一個(gè)元素作為"基準(zhǔn)"(pivot)峰弹。
(2)所有小于"基準(zhǔn)"的元素,都移到"基準(zhǔn)"的左邊芜果;所有大于"基準(zhǔn)"的元素鞠呈,都移到"基準(zhǔn)"的右邊。
(3)對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集右钾,不斷重復(fù)第一步和第二步蚁吝,直到所有子集只剩下一個(gè)元素為止旱爆。

二. 快速排序的時(shí)間復(fù)雜度

日本程序員norahiko,寫了一個(gè)排序算法的動(dòng)畫演示窘茁,可以直觀地將快排和其他排序方法的速度進(jìn)行對(duì)比怀伦。

三. 快速排序?yàn)槭裁茨敲纯?/h2>

根據(jù)劉偉鵬的數(shù)學(xué)之美番外篇:快排為什么那樣快一文所述,快排的本質(zhì)上是一種通過問問題來縮小結(jié)果的可能性區(qū)間的策略山林。

下面我們將從最基本的猜數(shù)字和稱小球講起房待,總結(jié)其中蘊(yùn)含的規(guī)律,然后一步步引申到排序問題上去驼抹。

1. 猜數(shù)字

假設(shè)有一個(gè)164之間的數(shù)桑孩,你來猜(你只能問答案是“是”或“否”的問題)。為了保證不論在什么情況下都能以盡量少的次數(shù)猜中框冀,你應(yīng)該采取什么策略呢流椒?很顯然,二分左驾。先是猜是不是位于132之間镣隶,排除掉一半可能性,然后對(duì)區(qū)間繼續(xù)二分诡右。這種策略能夠保證無論數(shù)字怎么跟你捉迷藏安岂,都能在log_2{n}次以內(nèi)猜中。用算法的術(shù)語來說就是它的下界是最好的帆吻。

為什么這種策略具有最優(yōu)下界域那?答案也很簡(jiǎn)單,這個(gè)策略是平衡的猜煮。反之如果策略不是平衡的次员,比如問是不是在110之間,那么一旦發(fā)現(xiàn)不是在110之間的話就會(huì)剩下比N/2更多的可能性需要去考察了王带。

這種策略的本質(zhì)可以概括成“讓未知世界無機(jī)可乘”淑蔚。它是沒有“弱點(diǎn)的”,答案的任何一個(gè)分支都是等概率的愕撰。反之刹衫,一旦某個(gè)分支蘊(yùn)含的可能性更多,當(dāng)情況落到那個(gè)分支上的時(shí)候你就郁悶了搞挣。比如猜數(shù)字游戲最糟糕的策略就是一個(gè)一個(gè)的猜:是1嗎带迟?是2嗎?… 因?yàn)檫@種猜法最差的情況下需要64次才能猜對(duì)囱桨,下界非常糟糕仓犬。二分搜索為什么好,就是因?yàn)樗看味紝⒖赡苄耘懦话氩⑶覠o論如何都能排除一半(它是最糟情況下表現(xiàn)最好的)舍肠。

2. 稱小球

12個(gè)小球搀继,其中有一個(gè)是壞球窘面。有一架天平。需要你用最少的稱次數(shù)來確定哪個(gè)小球是壞的并且它到底是輕還是重律歼。這個(gè)問題是一道流傳已久的智力題民镜。

我們先回顧一下猜數(shù)字游戲啡专。為了保證任何情況下以最少次數(shù)猜中险毁,我們的策略是每次都排除恰好一半的可能性。類比到稱球問題上:壞球可能是12個(gè)球中的任意一個(gè)们童,這就是12種可能性畔况;而其中每種可能性下壞球可能輕也可能重。于是“壞球是哪個(gè)球慧库,是輕是重”這個(gè)問題的答案就有12×2=24種可能性□喂颍現(xiàn)在我們用天平來稱球,就等同于對(duì)這24種可能性發(fā)問齐板,由于天平的輸出結(jié)果有三種“平衡吵瞻、左傾、右傾”甘磨,這就相當(dāng)于我們的問題有三個(gè)答案橡羞,即可以將所有的可能性切成三份,根據(jù)猜數(shù)字游戲的啟發(fā)济舆,我們應(yīng)當(dāng)盡量讓這三個(gè)分支概率均等卿泽,即平均切分所有的可能性為三等份。如此一來的話一次稱量就可以將答案的可能性縮減為原來的1/3滋觉,三次就能縮減為1/27签夭。而總共才有24種可能性,所以理論上是完全可以3次稱出來的椎侠。

如何稱的指導(dǎo)原則有了第租,構(gòu)造一個(gè)稱的策略就不是什么太困難的事情了。首先不妨解釋一下為什么最直觀的稱法不是最優(yōu)的——6我纪、6稱:在6慎宾、6稱的時(shí)候,天平平衡的可能性是0宣羊,也就是說我們得到的信息量為零璧诵。剛才說了,最優(yōu)策略應(yīng)該使得天平三種狀態(tài)的概率均等仇冯,這樣才能三等分答案的所有可能性之宿。

只要記著這樣一個(gè)指導(dǎo)思想——你選擇的稱法必須使得當(dāng)天平平衡的時(shí)候答案剩下的可能性和天平左傾(右傾)的時(shí)候答案剩下的可能性一樣多。實(shí)際上苛坚,這等同于你得選擇一種稱法比被,使得天平輸出三種結(jié)果的概率是均等的色难,因?yàn)樘炱捷敵瞿硞€(gè)結(jié)果的概率就等同于所有支持這個(gè)結(jié)果(左傾、右傾等缀、平衡)的答案可能性的和枷莉,并且答案的每個(gè)可能性都是等概率的。

MacKay在他的書《Information Theory: Inference and Learning Algorithms》(作者開放免費(fèi)電子書)里面4.1節(jié)專門講了這個(gè)稱球問題尺迂,還畫了一張不錯(cuò)的圖:

圖中“1+”是指“1號(hào)小球?yàn)橹亍边@一可能性笤妙。一開始一共有24種可能性。4噪裕、4稱了之后不管哪種情況(分支)蹲盘,剩下來的可能性總是4種。這是一個(gè)完美的三分膳音。然后對(duì)每個(gè)分支構(gòu)造第二次稱法召衔,這里你只要稍加演算就可以發(fā)現(xiàn),分支1上的第二次稱法祭陷,即“1苍凛、2、6對(duì)3兵志、4醇蝴、5”這種稱法,天平輸出三種結(jié)果的可能性是均等的(嚴(yán)格來說是幾乎均等)毒姨。這就是為什么這個(gè)稱法能夠在最壞的情況下也能表現(xiàn)最好的原因哑蔫,沒有哪個(gè)分支是它的弱點(diǎn),它必然能將情況縮小到原來的1/3弧呐。

3. 排序(理想情況)

用前面的看問題視角闸迷,排序的本質(zhì)可以這樣來表述:一組未排序的N個(gè)數(shù)字,它們一共有N!種重排俘枫,其中只有一種排列是滿足題意的(譬如從大到小排列)腥沽。換句話說,排序問題的可能性一共有N!種鸠蚪。任何基于比較的排序的基本操作單元都是“比較a和b”今阳,這就相當(dāng)于猜數(shù)字游戲里面的一個(gè)問句,顯然這個(gè)問句的答案只能是“是”或“否”茅信,一個(gè)只有兩種輸出的問題最多只能將可能性空間切成兩半盾舌,根據(jù)上面的思路,最佳切法就是切成1/2和1/2蘸鲸。也就是說妖谴,我們希望在比較了a和b的大小關(guān)系之后,如果發(fā)現(xiàn)a<b的話剩下的排列可能性就變成N!/2,如果發(fā)現(xiàn)a>b也是剩下N!/2種可能性膝舅。由于假設(shè)每種排列的概率是均等的嗡载,所以這也就意味著支持a<b的排列一共有N!/2個(gè),支持a>b的也是N!/2個(gè)仍稀,換言之洼滚,a<b的概率等于a>b的概率。

我們希望每次在比較a和b的時(shí)候技潘,a<b和a>b的概率是均等的遥巴,這樣我們就能保證無論如何都能將可能性縮小為原來的一半了!最優(yōu)下界崭篡。

一個(gè)直接的推論是挪哄,如果每次都像上面這樣的完美比較吧秕,那么N個(gè)元素的N!種可能排列只需要log_2{N!}就排查玩了琉闪,而log_2{N!}近似于NlogN。這正是快排的復(fù)雜度砸彬。

4. 排序(實(shí)際情況)

我們考慮快排的過程:隨機(jī)選擇一個(gè)元素做“軸元素”颠毙,將所有大于軸元素的移到左邊,其余移到右邊砂碉。根據(jù)這個(gè)過程蛀蜜,快排的第一次比較就是將一個(gè)元素和軸元素比較,這個(gè)時(shí)候顯而易見的是增蹭,“大于”和“小于”的可能性各占一半滴某。這是一次漂亮的比較。

然而滋迈,快排的第二次比較就不那么高明了:我們不妨令軸元素為pivot霎奢,第一次比較結(jié)果是a1<pivot,那么可以證明第二次比較a2也小于pivot的可能性是2/3饼灿!這容易證明:如果a2>pivot的話幕侠,那么a1,a2碍彭,pivot這三個(gè)元素之間的關(guān)系就完全確定了——a1<pivot<a2晤硕,剩下來的元素排列的可能性我們不妨記為P(不需要具體算出來)。而如果a2<pivot呢庇忌?那么a1和a2的關(guān)系就仍然是不確定的舞箍,也就是說,這個(gè)分支里面含有兩種情況:a1<a2<pivot皆疹,以及a2<a1<pivot疏橄。對(duì)于其中任一種情況,剩下的元素排列的可能性都是P墙基,于是這個(gè)分支里面剩下的排列可能性就是2P软族。所以當(dāng)a2<pivot的時(shí)候刷喜,還剩下2/3的可能性需要排查。

再進(jìn)一步立砸,如果第二步比較果真發(fā)現(xiàn)a2<pivot的話掖疮,第三步比較就更不妙了,模仿上面的推理颗祝,a3<pivot的概率將會(huì)是3/4浊闪!

這就是快排也不那么快的原因,因?yàn)樗矝]有做到每次比較都能將剩下的可能性砍掉一半螺戳。

5. 小節(jié)

將排序問題看成和猜數(shù)字一樣搁宾,是通過問問題來縮小/排除(narrow down)結(jié)果的可能性區(qū)間,這樣一來倔幼,就會(huì)發(fā)現(xiàn)盖腿,“最好的問題”就是那些能夠均分所有可能性的問題,因?yàn)槟菢拥脑挷还軉栴}的答案如何损同,都能排除掉k-1/k(k為問題的答案有多少種輸出——猜數(shù)字里面是2翩腐,稱球里面是3)種可能性,而不均衡的問題總會(huì)有一個(gè)或一些答案分支排除掉的可能性要小于k-1/k膏燃。于是策略的下界就被拖累了茂卦。

四. 快速排序的具體實(shí)現(xiàn)

知道了快排的思想與原理,下面我們就用javascript來具體實(shí)現(xiàn)一下快排组哩。

首先等龙,定義一個(gè)quickSort函數(shù),它的參數(shù)是一個(gè)數(shù)組伶贰。

var quickSort = function(arr) {
};

然后蛛砰,檢查數(shù)組的元素個(gè)數(shù),如果小于等于1幕袱,就返回暴备。

var quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
};

接著,選擇"基準(zhǔn)"(pivot)们豌,并將其與原數(shù)組分離涯捻,再定義兩個(gè)空數(shù)組,用來存放一左一右的兩個(gè)子集望迎。

var quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2) ;
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
};

然后障癌,開始遍歷數(shù)組,小于"基準(zhǔn)"的元素放入左邊的子集辩尊,大于基準(zhǔn)的元素放入右邊的子集涛浙。

var quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2) ;
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
};

最后,使用遞歸不斷重復(fù)這個(gè)過程,就可以得到排序后的數(shù)組轿亮。

var quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

使用的時(shí)候疮薇,直接調(diào)用quickSort()就行了。

參考來源:阮一峰我注、劉未鵬

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末按咒,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子但骨,更是在濱河造成了極大的恐慌励七,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,402評(píng)論 6 499
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件奔缠,死亡現(xiàn)場(chǎng)離奇詭異掠抬,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)校哎,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,377評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門两波,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人贬蛙,你說我怎么就攤上這事雨女。” “怎么了阳准?”我有些...
    開封第一講書人閱讀 162,483評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)馏臭。 經(jīng)常有香客問我野蝇,道長(zhǎng),這世上最難降的妖魔是什么括儒? 我笑而不...
    開封第一講書人閱讀 58,165評(píng)論 1 292
  • 正文 為了忘掉前任绕沈,我火速辦了婚禮,結(jié)果婚禮上帮寻,老公的妹妹穿的比我還像新娘乍狐。我一直安慰自己,他們只是感情好固逗,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,176評(píng)論 6 388
  • 文/花漫 我一把揭開白布浅蚪。 她就那樣靜靜地躺著,像睡著了一般烫罩。 火紅的嫁衣襯著肌膚如雪惜傲。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,146評(píng)論 1 297
  • 那天贝攒,我揣著相機(jī)與錄音盗誊,去河邊找鬼。 笑死,一個(gè)胖子當(dāng)著我的面吹牛哈踱,可吹牛的內(nèi)容都是我干的荒适。 我是一名探鬼主播,決...
    沈念sama閱讀 40,032評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼开镣,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼吻贿!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起哑子,我...
    開封第一講書人閱讀 38,896評(píng)論 0 274
  • 序言:老撾萬榮一對(duì)情侶失蹤舅列,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后卧蜓,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體帐要,經(jīng)...
    沈念sama閱讀 45,311評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,536評(píng)論 2 332
  • 正文 我和宋清朗相戀三年弥奸,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了榨惠。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,696評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡盛霎,死狀恐怖赠橙,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情愤炸,我是刑警寧澤期揪,帶...
    沈念sama閱讀 35,413評(píng)論 5 343
  • 正文 年R本政府宣布,位于F島的核電站规个,受9級(jí)特大地震影響凤薛,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜诞仓,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,008評(píng)論 3 325
  • 文/蒙蒙 一缤苫、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧墅拭,春花似錦活玲、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至屡萤,卻和暖如春珍剑,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背死陆。 一陣腳步聲響...
    開封第一講書人閱讀 32,815評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工招拙, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留唧瘾,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,698評(píng)論 2 368
  • 正文 我出身青樓别凤,卻偏偏與公主長(zhǎng)得像饰序,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子规哪,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,592評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容

  • 概述 排序有內(nèi)部排序和外部排序求豫,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序,而外部排序是因排序的數(shù)據(jù)很大诉稍,一次不能容納全部...
    蟻前閱讀 5,183評(píng)論 0 52
  • 1.背景介紹 什么是算法 算法(Algorithm)是指解題方案的準(zhǔn)確而完整的描述,是一系列解決問題的清晰指令服爷,算...
    遠(yuǎn)望的云閱讀 681評(píng)論 0 1
  • 概述:排序有內(nèi)部排序和外部排序杜恰,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序,而外部排序是因排序的數(shù)據(jù)很大仍源,一次不能容納全部...
    每天刷兩次牙閱讀 3,730評(píng)論 0 15
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 將一個(gè)記錄插入到已排序好...
    依依玖玥閱讀 1,253評(píng)論 0 2
  • 創(chuàng)作你的創(chuàng)作 免費(fèi)下載 2017-10-05 半生緣_ab19 作者 2017.09.10 16:28 打開App...
    半生緣_ab19閱讀 200評(píng)論 0 0