快速排序算法（快速排序）

大家好，我是小夏，我來為大家解答以上問題。快速排序算法，快速排序很多人還不知道，現在讓我們一起來看看吧！

1、設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它小的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一趟快速排序。一趟快速排序的算法是：

2、　　1）設置兩個變量I、J，排序開始的時候：I=0，J=N-1；

3、　　2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]；

4、　　3）從J開始向前搜索，即由后開始向前搜索（J=J-1），找到第一個小于key的值A[J]，并與A[I]交換；

5、　　4）從I開始向后搜索，即由前開始向后搜索（I=I+1），找到第一個大于key的A[I]，與A[J]交換；

6、　　5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到并交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j+完成的最后另循環結束)

7、　　例如：待排序的數組A的值分別是：（初始關鍵數據：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什么位子，最后的目的就是把X放在中間，小的放前面大的放后面。

8、　　A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：

9、　　49 38 65 97 76 13 27

10、　　進行第一次交換后： 27 38 65 97 76 13 49

11、　　( 按照算法的第三步從后面開始找)

12、　　進行第二次交換后： 27 38 49 97 76 13 65

13、　　( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )

14、　　進行第三次交換后： 27 38 13 97 76 49 65

15、　　( 按照算法的第五步將又一次執行算法的第三步從后開始找

16、　　進行第四次交換后： 27 38 13 49 76 97 65

17、　　( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時：I=4,J=6 )

18、　　此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那么經過一趟快速排序之后的結果是：27 38 13 49 76 97 65，即所以大于49的數全部在49的后面，所以小于49的數全部在49的前面。

19、　　快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最后把此數據序列變成一個有序的序列，根據這種思想對于上述數組A的快速排序的全過程如圖6所示：

20、　　初始狀態 {49 38 65 97 76 13 27}

21、　　進行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}

22、　　分別對前后兩部分進行快速排序 {27 38 13} 經第三步和第四步交換后變成 {13 27 38} 完成排序。

23、　　{76 97 65} 經第三步和第四步交換后變成 {65 76 97} 完成排序。

本文到此講解完畢了，希望對大家有幫助。