前言
快速排序是一種很實(shí)用的排序算法。今天在網(wǎng)上看到有網(wǎng)友談?wù)摽焖倥判蚴鞘裁捶鬯健Ｏ胂胱约河浀靡膊皇呛芮宄耍餍跃蛯懸黄∮浵补模瑥?fù)習(xí)一下。
1 簡(jiǎn)介
快速排序是對(duì)冒泡排序的一種改進(jìn)衔肢。
它的核心思想是：通過一趟排序?qū)⒁判虻臄?shù)列分成兩個(gè)獨(dú)立的新數(shù)列庄岖，其中一個(gè)新數(shù)列的每個(gè)元素都比另一個(gè)新數(shù)列的任何一個(gè)元素要小。之后角骤，對(duì)這兩個(gè)數(shù)列再次進(jìn)行快速排序隅忿。
2 算法性質(zhì)
內(nèi)部排序
快速排序是一種內(nèi)部排序算法。即參與快速排序的對(duì)象都是存儲(chǔ)在內(nèi)存中的启搂。（了解一下 外部排序 ）
不穩(wěn)定性
在排序算法中硼控，假設(shè)待排序數(shù)列中有兩個(gè)元素a刘陶、b胳赌，其中a.key == b.key，若排序算法不能保證a和b在數(shù)列中的相對(duì)位置匙隔，則稱排序算法是不穩(wěn)定的疑苫。
例如：有數(shù)列 'yabx'，其中 y.key > a.key == b.key > x.key纷责。經(jīng)排序捍掺，得到數(shù)列 'xbay'。此時(shí)再膳，數(shù)列為升序挺勿，是有序的。但a和b的相對(duì)位置想比較于排序前喂柒，發(fā)生了顛倒不瓶，我們稱這種排序就是不穩(wěn)定的禾嫉，它可能改變?cè)氐南鄬?duì)排列順序。
原地排序
原地排序意味著排序算法隨問題規(guī)模增大蚊丐，對(duì)額外內(nèi)存空間的需求是常數(shù)級(jí)的（S(1)）熙参。所以，在內(nèi)存受限的系統(tǒng)中麦备，快速排序也能很好地工作孽椰。
3 算法描述
為了便于理解。這里給出一個(gè)待排序的數(shù)列： 6, 2, 3, 7, 1, 5, 4, 8, 9
第一趟排序
step1凛篙，選取待排序數(shù)列（以下稱 '數(shù)列'）中索引為 '0' 的元素（記為 pivot）作為本趟排序的主軸黍匾，記 pivot 當(dāng)前索引位置為 pre_pos 。 （pivot.key == 6呛梆， pre_pos == 0膀捷，此時(shí)數(shù)列為原始數(shù)列： 6, 2, 3, 7, 1, 5, 8, 4, 9 ）
step2，從數(shù)列末尾對(duì)數(shù)列遍歷（為便于理解削彬，以下稱 '從右到左遍歷'）全庸，找到第一個(gè)比 pivot.key 小的元素（記為 rear），rear 的索引記為 rear_pos融痛。將 pivot 與 rear 交換位置（即交換 '4' 和 '6'）壶笼。 （pivot.key == 6， pre_pos == 0雁刷， rear_pos == 7覆劈，交換后數(shù)列為： 4, 2, 3, 7, 1, 5, 8, 6, 9 ）
step3，現(xiàn)在沛励，從數(shù)列頭部開始责语，找到索引為 pre+1 的元素，以索引為 pre+1 的元素為起點(diǎn)目派，向數(shù)列尾部方向做遍歷（為方便理解坤候，以下稱 '從左到右遍歷'）。直到找到比 pivot 大的元素（記為 pre）企蹭，更新 p_pos 的值為 pre 當(dāng)前的索引位置白筹，交換 pre 與 pivot 的位置（即交換 '6' 和 '7'）。（pivot.key == 6谅摄， pre_pos == 3徒河， rear_pos == 7，交換后數(shù)列為： 4, 2, 3, 6, 1, 5, 8, 7, 9 ）
到這里送漠，我們發(fā)現(xiàn)顽照，經(jīng)過兩次交換， pre （pre.key == 6）左側(cè)的元素都比 pivot 小闽寡，rear （rear.key == 7）右側(cè)的元素都比 pivot 大代兵。
重復(fù) step2 和 step3纵穿，完成第一趟排序，得到數(shù)列 4, 2, 3, 5, 1, 6, 8, 7, 9 奢人。
經(jīng)過第一趟排序谓媒，我們得到了兩個(gè)新的數(shù)列 4, 2, 3, 5, 1（記為 數(shù)列 a） 和 8, 7, 9 （記為 數(shù)列 b）。顯然何乎，數(shù)列 a 中的元素都小于 pivot（pivot.key == 6）句惯，而數(shù)列 b 中的元素都大于 piovt。
這時(shí)候支救，我們分別以數(shù)列 a抢野、 數(shù)列 b 為待排序數(shù)列，對(duì)它們進(jìn)行快速排序的第一趟排序各墨。
數(shù)列 a 經(jīng)過第一趟排序指孤，結(jié)果為 1, 2, 3, 4, 5，已經(jīng)有序贬堵；數(shù)列 b 經(jīng)過第一趟排序恃轩，結(jié)果為 7, 8, 9。
這時(shí)候黎做，原始的待排序數(shù)列中的所有元素已經(jīng)是有序排列的了叉跛。即 1, 2, 3, 4, 5 + 6 + 7, 8, 9。
此時(shí)蒸殿，快速排序已完成筷厘。
