快速排序是對(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ù)變成有序序列。
假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一躺快速排序。一躺快速排序的算法是：
1）、設(shè)置兩個(gè)變量I、J，排序開始的時(shí)候I：=1，J：=N；
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個(gè)小于X的值，兩者交換；
4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個(gè)大于X的值，兩者交換；
5）、重復(fù)第3、4步，直到I=J；
例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
進(jìn)行第一次交換后： 27 38 65 97 76 13 49
( 按照算法的第三步從后面開始找
進(jìn)行第二次交換后： 27 38 49 97 76 13 65
( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時(shí)I：=3 )
進(jìn)行第三次交換后： 27 38 13 97 76 49 65
( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找
進(jìn)行第四次交換后： 27 38 13 49 76 97 65
( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時(shí)J：=4 )
此時(shí)再執(zhí)行第三不的時(shí)候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過一躺快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。
快速排序就是遞歸調(diào)用此過程——在以49為中點(diǎn)分割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部分進(jìn)行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的序列，根據(jù)這種思想對(duì)于上述數(shù)組A的快速排序的全過程如圖6所示：
初始狀態(tài) {49 38 65 97 76 13 27}
進(jìn)行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}
分別對(duì)前后兩部分進(jìn)行快速排序 {13} 27 {38}
結(jié)束 結(jié)束 49 {65} 76 {97}
圖6 快速排序全過程
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1529686
