歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

算法學習之快速排序原理及實現

快速排序(Quicksort)是對冒泡排序的一種改進。

它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

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

算法是:1)設置兩個變量I、J,排序開始的時候:I=0,J=N-1;

2)以第一個數組元素作為關鍵數據,賦值給key,即 key=A[0];

3)從J開始向前搜索,即由後開始向前搜索(J=J-1),找到第一個小於key的值A[J],並與key交換;

4)從I開始向後搜索,即由前開始向後搜索(I=I+1),找到第一個大於key的A[I],與key交換;

5)重復第3、4、5步,直到 I=J; (3,4步是在程序中沒找到時候j=j-1,i=i+1,直至找到為止。

找到並交換的時候i, j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最後另循環結束。)   

例如:待排序的數組A的值分別是:(初始關鍵數據:X=49)

注意關鍵X永遠不變,永遠是和X進行比較,無論在什麼位子,最後的目的就是把X放在中間,小的放前面大的放後面。

49 38 65 97 76 13 27

進行第一次交換後:27 38 65 97 76 13 49 (按照算法的第三步從後面開始找)

進行第二次交換後:27 38 49 97 76 13 65 (按照算法的第四步從前面開始找>X的值,65>49,兩者交換,此時:I=3 )   

進行第三次交換後:27 38 13 97 76 49 65 (按照算法的第五步將又一次執行算法的第三步從後開始找   

進行第四次交換後:27 38 13 49 76 97 65 (按照算法的第四步從前面開始找大於X的值,97>49,兩者交換,此時:I=4,J=6 )

此時再執行第三步的時候就發現I=J,從而結束一趟快速排序,

經過一趟快速排序之後的結果是:27 38 13 49 76 97 65,即所有大於49的數全部在49的後面,所有小於49的數全部在49的前面。

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

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

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

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

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

Copyright © Linux教程網 All Rights Reserved