Quick sort

老題目了，要做到快狠準！

基本想法就是找一個 pivot，讓比 pivot 小的數往左邊去，比 pivot 大的往右邊去，

然後再進行左右的 quick sort，就可以完成排序，

quick sort 的重點是 pivot 的選擇，如果選到最大數，那複雜度會變為 O(n^2)，因為等於每個數都要掃一遍

簡易的方法是找中點即可，其餘還有找頭、中、尾的中位數的方法

public quickSort(int[] A, int start, int end) {
    if (start >= end)
        return;

    int left = start, right = end;
    int pivot = A[(start+end)/2];

    while (left <= right) {
        while (left <= right && A[left] < pivot) {
            left++;
        }
        while (left <= right && A[right] > pivot) {
            right--;
        }

        if (left <= right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left++;
            right--;
        }
    }

    quickSort(A, start, right);
    quickSort(A, left, end);
}

從左邊找到第一個比 pivotv 大的數是

while (left <= right && A[left] < pivot) {
    left++;
}

從右邊找到第一個比 pivotv 小的數是

while (left <= right && A[right] > pivot) {
    right--;
}

而為何都要是 left <= right 呢？

因為我們要讓 left, right 在每次做完時都錯開，避免 stack overflow

為何 left 會大於 right？ 因為交換到最後必定是某一邊找不到然後讓 left++, right-- 了