Quick sort

quick sort 的原理是選一個基準，然後把小於基準的丟到數組左邊，大於基準的放到數組右邊，

再左邊右邊各自進行 quick sort，做到數組數為 1時就把數組排序完成了

所以重點在於如何將數丟到左邊和右邊

下面是 code 演示：

public void sortIntegers2(int[] A) {
    quickSort(A, 0, A.length - 1);
}

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

    //find pivot and swap
    int pivot = A[(start + end) / 2];
    int left = start;
    int right = end;
    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);
}

有幾個地方要注意一下：

left <= right

這邊要寫這樣才不會超時，用 [3, 2, 1, 4, 5] 這個例子去跑一遍就知道為什麼了

不讓 left <= right 在 size為 2的以排序子數組會 stack overflow

另一個地方是 A[left] > pivot ，這是要讓數組分布均勻一點

假設數組全都是 1，那麼如果是 A[left] >＝ pivot 會讓數組全部都搬到右邊，很沒效率

用 [3, 2, 1, 4, 5] 這個例子去多想想 quicksort 就不難了

複雜度為：