public int Partition(int[] nums, int left, int right) {
    int pivot = nums[left];

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

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

    nums[left] = pivot;

    return left;
}
返回的left就是pivot的index

Quick Sort

Complexity

average O(nlog(n)), best O(nlog(n)), worst O(n^2)

模板

这个 模板仅适用于没有重复元素的数组，有重复元素的数组，参见quick partition的模板

left <= right not left < right

A[left] < pivot not A[left] <= pivot

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

public void quickSort(int[] A, int start, int end) {
    if (start >= end) {
        return;
    }
    int index = partition(A, 0, A.length - 1);
}

private int partition(int[] A, int left, int right) {
    int pivot = A[(left + right) / 2];
    while (left <= right) {
        while (A[left] < pivot) {
            left++;
        }
        while (A[right] > pivot) {
            right--;
        }
        if (left <= right) {
            swap(A, left, right);
            left++;
            right--;
        }
        return left;
        // 这个left=pivot的index+1或者A.length（如果pivot的index是A.length - 1）
    }
}

private swap(int[] A, int left, int right) {
    int temp = A[left];
    A[left] = A[right];
    A[right] = temp;
}