Quick Sort

• average O(n log n) - best: partition splits the array evenly O(n log n) - worst: sorted or reverse sorted O(n^2)

• not stable & in-place

public static void quickSort(int[] a, int start, int end) {
    if (a == null || a.length <= 1) {
        return;
    }
    while (start < end) {
        int pivot = partition(a, start, end);
        quickSort(a, start, pivot - 1);
        quickSort(a, pivot + 1, end);
    }
}
// put nums that are <= pivot to the left
// put nums that are  > pivot to the right
public static int partition(int[] a, start, end) {
    int pivot = a[start];
    int k = start;
    for (int i = k + 1; i <= end; i++) {
        if (a[i] < pivot) {
            k++;
            //swap a[i] <-> a[k]
            int temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }
    a[start] = a[k];
    a[k] = pivot;
    return k;
}

九章的版本：

Randomized the pivot index can help improve the worst running time.

import java.util.Random;

public class Solution {
    public Random rand;

    public void sortIntegers(int[] A) {
        rand = new Random();
        quickSort(A, 0, A.length - 1);
    }

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

        int index = rand.nextInt(end - start + 1) + start;
        int pivot = A[index];

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