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