Java實現快速排序（快排）

速排3號提前幾個小時打

快速排序是氣泡排序的改進版，也是最好的一種內排序，在很多面試題中都會出現，也是作為程式設計師必須掌握的一種排序方法。

快速排序由C。 A。 R。 Hoare在1962年提出。它的基本思想是：透過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個資料變成有序序列。

下面我們用圖解來說明一下這個排序演算法

假設使用者輸入瞭如下陣列：

下標

0

1

2

3

4

5

資料

6

2

7

3

8

9

建立變數i=0（指向第一個資料）， j=5（指向最後一個數據）， k=6（賦值為第一個資料的值）。

我們要把所有比k小的數移動到k的左面，所以我們可以開始尋找比6小的數，從j開始，從右往左找，不斷遞減變數j的值，我們找到第一個下標3的資料比6小，於是把資料3移到下標0的位置，把下標0的資料6移到下標3，完成第一次比較：

下標

0

1

2

34

5

資料

3

2

7

6

8

9

i=0 j=3 k=6

接著，開始第二次比較，這次要變成找比k大的了，而且要從前往後找了。遞加變數i，發現下標2的資料是第一個比k大的，於是用下標2的資料7和j指向的下標3的資料的6做交換，資料狀態變成下表：

下標

0

1

2

3

4

5

資料

3

2

6

7

8

9

i=2 j=3 k=6

稱上面兩次比較為一個迴圈。

接著，再遞減變數j，不斷重複進行上面的迴圈比較。

在本例中，我們進行一次迴圈，就發現i和j“碰頭”了：他們都指向了下標2。於是，第一遍比較結束。得到結果如下，凡是k（=6）左邊的數都比它小，凡是k右邊的數都比它大：

下標

0

1

2

3

4

5

資料

3

2

6

7

8

9

如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反覆，不斷迴圈。注意判斷和尋找是同時進行的。

然後，對k兩邊的資料，再分組分別進行上述的過程，直到不能再分組為止。

注意：

第一遍快速排序不會直接得到最終結果，只會把比k大和比k小的數分到k的兩邊。為了得到最後結果，需要再次對下標2兩邊的陣列分別執行此步驟，然後再分解陣列，直到陣列不能再分解為止（只有一個數據），才能得到正確結果。

下面，我們用一個動圖，請大家耐心看完

接下來我們用程式碼實現

package quickSort； public class QuickSort { private static int count； /** * 測試 * @param args */ public static void main（String［］ args） { int［］ num = {3，45，78，64，52，11，64，55，99，11，18}； System。out。println（arrayToString（num，“未排序”））； QuickSort（num，0，num。length-1）； System。out。println（arrayToString（num，“排序”））； System。out。println（“陣列個數：”+num。length）； System。out。println（“迴圈次數：”+count）； } /** * 快速排序 * @param num 排序的陣列 * @param left 陣列的前針 * @param right 陣列後針 */ private static void QuickSort（int［］ num， int left， int right） { //如果left等於right，即陣列只有一個元素，直接返回 if（left>=right） { return； } //設定最左邊的元素為基準值 int key=num［left］； //陣列中比key小的放在左邊，比key大的放在右邊，key值下標為i int i=left； int j=right； while（i=key && i

輸出結果為：

陣列為（未排序）：3 45 78 64 52 11 64 55 99 11 18 陣列為（排序）：3 11 11 18 45 52 55 64 64 78 99 陣列個數：11迴圈次數：8