# 快速排序(Quick Sort)
快速排序是對泡沫排序的一種改進。通過一輪排序將要排序的數據分割成獨立的兩部分，其中一部分的數據都比另外一部分的數據要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個數據變成有序。

## 基本思想

1. 先從陣列中取出一個數作為基準數。
2. 以基準數做分區，將比基準數大的數放到它的右邊，小於或等於它的數全放到它的左邊。
3. 再對左右區間重複第二步，直到各區間只有一個數。

快速排序法比較難用文字去理解，建議大家可以看這個動畫演示，一下子就能懂：
https://www.bilibili.com/video/BV1at411T75o

## 舉例說明
**一、設有一組數據 `[2,10,5,11,34,28,21]` 使用快速排序法由小到大排序**

其過程為：


上面的例子使用圖解，下面的例子用文字敘述。

**二、使用快速排序法將陣列 [19,97,9,17,1,8] 由小到大排序**

1. 首先我們需要有 i , j 兩個索引
2. 暫定陣列第一個值，也就是 19 為基準值
3. i 索引由 0 開始由左至右移動，j 索引由 陣列最末尾開始由右至左移動 [19(i), 97, 9, 17, 1, 8(j)]
4. 因為我們是將基準值設為左邊第一個，因此我們比較要從最末尾開始比較。
這個陣列的最末尾為 8，將之與基準值 19 做比較，如果比基準值小，放置於i位置，如果比基準值大則不動。8 < 19，因此 8 要放到 i 位置，此時 i+1 進行下一位數比較。
此時陣列為 [8, 97(i), 9, 17, 1, 19(j)]
5. 此時 i 指向的數為 97，與基準值比較 97 > 19，因此將 97放到 j 位置，此時 j-1，繼續下一位比較。此時陣列為 [8, 19(i), 9, 17, 1(j), 97]
6. 此時 j 指向 1，與基準值比較 1 < 19，因此要將 1 放到 i 位置，然後 i+1繼續進行下一個比較。此時陣列為 [8, 1, 9(i), 17, 19(j), 97]
7. 此時 i 指向 9，與基準值比較 9 < 19，因此9要放到左邊，但9本來就在左邊，所以不用動，但是要記得 i+1 指向下一個數比較。此時陣列還是 [8, 1, 9, 17(i), 19(j), 97]
8. 此時 i 指向 17，與基準值比較 17 < 19，因此依然不動，還是一樣 i+1 指向下一個位置，此時陣列還是 [8, 1, 9, 17, 19(i,j), 97]。
9. 直到此刻，i索引和j索引重疊，指向同一個位置，即將基準值 19 擺在重疊的位置，完成排序。

但是我們能發現 [8, 1, 9, 17, 19, 97] 其實還並沒有完成由小到大排序，我們需要再對基準值左右子序列再繼續以上步驟排序，這邊比基準值 19 小的左子序列為 [8, 1, 9, 17]，右子序列為[97]，只剩下一個數的序列已然排序，所以我們只需要再對左子序列進行以上步驟排序。

最終得到排序後的陣列為 [1, 8, 9, 17, 19, 97]。

## 程式碼實現

package Sort;

import java.util.Arrays;

public class QuickSort {
    static int []arr  = {19,4,5,21,19,4};
    public static void main(String[] args) {
        System.out.println("原序列為："+Arrays.toString(arr));
        quickSort(arr);
    }

    public static void quickSort(int [] arr) {
        sort(0,arr.length-1);
        System.out.println("排序後為："+Arrays.toString(arr));
    }

    /**
     * 
     * @param left => 設為基準值
     * @param right => arr.length - 1
     */
    public static void sort(int left,int right) {
        if(left < right) {
            int i = left; // 由左至右的索引
            int j = right + 1; // 由右至左的索引
            while(true) {
                while( i+1 < arr.length && arr[++i] < arr[left]); // 向右找, 直到找到比基準值大的數
                while( j-1 >= 0 && arr[--j] > arr[left]); // 向左找, 值到找到比基準值小的數
                if( i >= j) break; // 若i,j重疊或i超過j後則退出循環
                swap(i , j);
            }
            swap(left , j); // 基準點與 j 交換
            sort(left , j - 1); // 遞迴排序基準點左子序列
            sort(j + 1 , right); // 遞迴排序基準點右子序列
            
        }
    }

    public static void swap(int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

## 速度測試

public static void main(String[] args) {
    // System.out.println("原序列為："+Arrays.toString(arr));
    int arr[] = new int[80000];
    for(int i = 0; i < 80000; i++) {
        arr[i] = (int)(Math.random() * 80000);
    }
    Instant startTime = Instant.now();
    quickSort(arr);
    Instant endTime = Instant.now();
    System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}

output

共耗時：20 毫秒
共耗時：17 毫秒
共耗時：27 毫秒
共耗時：15 毫秒
共耗時：21 毫秒

八萬筆資料使用快速排序法平均排序需耗時 20 ms

## 時間複雜度
假設今天要對一陣列使用快速排序法由小到大排序。

### 最佳：O(nlogn)
第一個基準值的位置剛好是中位數，將資料平均分成兩等分。

### 平均：O(nlogn)

### 最差：O(n^5/4^)
當資料的順序恰好為由大到小或由小到大時，有分割與沒分割都一樣。