快速排序

1.將隨便一個數字設定為 pivot，通常設為第一個

2.左大右小，取最左邊和最右邊的數，左邊 > pivot；右邊 < pivot

先判斷右邊，如果沒有 < pivot，就再往左

再判斷左邊，如果沒有 > pivot，就再往右

都符合條件就左右互換

3.持續做 2 一直到左右的 index 一樣，此時將 pivot 和此值做交換，這時結果為左邊都 < pivot；右邊都 > pivot

4.pivot 的左邊和右邊又有兩個未排序好的(不包括 pivot 這個值)，再重覆 1~4

例：

右：23 比 35 小

左：42 比 35 大

交換

右：18 比 35 小

左：79 比 35 大

交換

右：12 比 35 小

左：往右時和右指針 index 一樣

pivot 和 index 的值交換

此時會分成綠色和藍色兩邊，這兩邊再重覆去做即可

public static void main(String[] args) {

    int[] arr = new int[]{5, 4, 8, 6, 3, 9, 0, 1, 7, 2};

    quickSort(arr, 0, arr.length - 1); // 減1是因為 index 從 0 開始

    Arrays.stream(arr).forEach(System.out::print);

}

public static void quickSort(int[] arr, int leftIndex, int rightIndex) {

if (arr == null || arr.length <= 1) return; // 無法再排序

if (leftIndex >= rightIndex) return;

int pivot = arr[leftIndex];

int left = leftIndex;

int right = rightIndex;

while (left != right) { // index 一樣就離開

while (arr[right] >= pivot && left < right) right--; // 右邊要找 < pivot，< 的相反就是 >=

while (arr[left] <= pivot && left < right) left++; // 左邊要找 > pivot，> 的相反就是 <=

if (left < right) { // 左右交換

arr[left] = arr[left] ^ arr[right];

arr[right] = arr[left] ^ arr[right];

arr[left] = arr[left] ^ arr[right];

}

}

        // pivot 和 index 的值交換

arr[leftIndex] = arr[left];

arr[left] = pivot;

quickSort(arr, leftIndex, left - 1); // 綠色

quickSort(arr, left + 1, rightIndex); // 藍色

}