演算法：快速排序

作者對文章內容原創性負責，但僅為作者思考過程，不保證正確性，歡迎指教，感謝！

關於快速排序的思想，參考 阮一峰 老師的博客快速排序（Quicksort）的Javascript實現，這篇博客把快排講的很清楚，但是阮老師是 Js 系的，裡面很多對數組的操作都是使用 Js 封裝的方法，所以在這裡按照阮老師的思路改成 Java 版本的。

我們先搭建幾個測試用例，這裡為了在控制台直觀的看到排序效果，就列印到控制台，而沒有使用 assert 語句：

import org.junit.Test;public class MainTest { @Test public void quickSort() { int[][] numbers = {{3,8,5,1,2}, {1,5,2,3,2,4,8,9,2,1,4,5,2,3,6,1,2}, {5,2,1,8,5,2,3,1,4,2,3,6,9,5,2,1,2,3}}; Main main = new Main(); for (int i = 0; i < numbers.length; i++){ main.quickSort(numbers[i]); } for (int i = 0; i < numbers.length; i++){ for (int j = 0; j < numbers[i].length; j++){ System.out.printf("%d ",numbers[i][j]); } System.out.printf("
"); } }}

然後在 Main 類當中把排序的方法入口寫出來

/** * @author hanyuxiao */public class Main{ public void quickSort(int[] numbers){ }}

快速排序的思是選取一個參考點，然後把大於參考點的數值放在數組的一邊，把小於參考點的數值放在數組的另外一邊，所以我們需要選取一個參考點位置

int pivotIndex = (0 + numbers.length) / 2;

但是這樣是不行，因為快速排序還有一個重要特點，就是分區，也就是逐漸的縮小排序的範圍，從大致有序，到局部有序，變成全局有序，所以用遞歸的方式比較好理解，重新修改方法入口

/** * @author hanyuxiao */public class Main { public void quickSort(int[] numbers){ quickSort(numbers, 0, numbers.length - 1); } public void quickSort(int[] numbers, int start, int end){ }}

大概就是這樣，然後考慮什麼條件下，不需要對數組進行排序：

2. 數組長度為 0 或者 1

/** * @author hanyuxiao */public class Main { public void quickSort(int[] numbers){ quickSort(numbers, 0, numbers.length - 1); } public void quickSort(int[] numbers, int start, int end){ if (numbers == null || start >= end) { return; } }}

選取參考點，和阮老師一樣，選取中心點做參考點

/** * @author hanyuxiao */public class Main { public void quickSort(int[] numbers){ quickSort(numbers, 0, numbers.length - 1); } public void quickSort(int[] numbers, int start, int end){ if (numbers == null || start >= end) { return; } int pivotIndex = (start + end) / 2; int pivot = numbers[pivotIndex]; }}

參考點選取完畢後，就要想辦法，把大於參考點的數放到右邊，把小於參考點的數放在左邊，一個很簡單的辦法是，從 start 處開始往參考點找大於參考點的數值然後停下，另一邊從 end 處往參考點找小於參考點的數值然後停下。大概就是這個樣子：

/** * @author hanyuxiao */public class Main { public void quickSort(int[] numbers){ quickSort(numbers, 0, numbers.length - 1); } public void quickSort(int[] numbers, int start, int end){ if (numbers == null || start >= end) { return; } int pivotIndex = (start + end) / 2; int pivot = numbers[pivotIndex]; int left = start; int right = end; // 如果，參考點的左邊全部都是小一點的數，右邊都是大一點的數 // 那麼 left 會比 right 大一點或者碰到一起了 while (left <= right) { // 如果數值比參考點小的話，那麼就往後面找 while (numbers[left] < pivot) { left ++; } // 如果數值比參考點大的話，那麼往前面找 while (numbers[right] > pivot) { right --; } // 到這裡就找到了，但是有一個特殊的情況 // 就是左邊的指針和右邊的指針直到了一起 // 這個時候，兩個指向的數值是一樣的，錯開一下就好了 if (left < right) { // 正常情況，也就是兩個指針沒有碰到一起 int temp = numbers[left]; numbers[left] = numbers[right]; numbers[right] = temp; left ++; right --; } //兩個指針直到了一起，錯開他們倆 else if (left == right){ left ++; } } quickSort(numbers,start,right); quickSort(numbers,left,end); }}

推薦閱讀：