Java快速排序模板（多种pivot选取方法）

Java快速排序模板

快速排序模板，简洁、好记。

partition函数中的左右指针最后总是相等，因而鲁棒性强，可扩展性好，可在很多算法中复用。

同时，给出可以随意更换pivot的选取方法的模板，只要改写findPivot()函数就可以随意更换不同的pivot的选取方法，具有很好的可扩展性。

用最左元素作 pivot

partition函数中pivot的取法有很多，不同的取法在不同的情况下可能有不同的排序效率。

首先是最简单的pivot取法，即直接取最左边一个元素为pivot。
该方法最易于实现，但是在某些极端环境下可能会使得排序效率较低（比如当数组原本就有序时）。

private void quickSort(int[] nums, int i, int j) {
    if (i < j) {
        int mid = partition(nums, i, j);
        quickSort(nums, i, mid - 1);
        quickSort(nums, mid + 1, j);
    }
}

private int partition(int[] nums, int i, int j) {
    int left = i, right = j, pivot = nums[i];
    while (left < right) {
        while (left < right && nums[right] >= pivot) right--;
        while (left < right && nums[left] <= pivot) left++;
        if (left != right) swap(nums, left, right);
    }
    swap(nums, i, left);  // 将第 i 个元素与 left 或 r 位置的元素调换都可以，因为 left 总是与 r 相等
    return left;  // 返回 left 还是 r 都可以，因为 left 总是与 r 相等
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

更复杂的 pivot 选择方法

pivot的选取方法是快速排序算法的一个关键优化点，不同的pivot的选取方法在不同的情况下的排序效率可能天差地别！

因此，存在着五花八门的pivot的选取方法，这些方法各有各的特点，各有优劣之处。

为了能够使快速排序模板可以简单的切换不同的pivot的选取方法，这里将选取pivot的方法抽取出来，写成一个findPivot()函数，只要更换findPivot()函数的内容，即可更该模板中换选取pivot的方法，而无需改动其他代码。

需要注意的是，在取到pivot后要先将最左元素与pivot元素交换位置，从而保证循环开始时pivot元素位于最左边。

private void quickSort(int[] nums, int i, int j) {
    if (i < j) {
        int mid = partition(nums, i, j);
        quickSort(nums, i, mid - 1);
        quickSort(nums, mid + 1, j);
    }
}

private int partition(int[] nums, int i, int j) {
    int left = i, right = j;
    int pivotIndex = findPivot(nums, i, j);  // 选取 pivot
    int pivot = nums[pivotIndex];
    swap(nums, i, pivotIndex);  // 交换 pivot 与最左元素，以保证循环开始时 pivot 位于最左边
    while (left < right) {
        while (left < right && nums[right] >= pivot) right--;
        while (left < right && nums[left] <= pivot) left++;
        if (left != right) swap(nums, left, right);
    }
    swap(nums, i, left);  // 将第 i 个元素与 left 或 right 位置的元素调换都可以，因为在这里 left 总是与 right 相等
    return left;  // 返回 left 还是 right 都可以，因为在这里 left 总是与 right 相等
}

private int findPivot(int[] nums, int i, int j) {
    return i;  // 这里的 pivot 选取方法可以任意更换
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

用随机元素作 pivot

随机取一个元素作为pivot是一种很中庸的方法，因为随机的取法在任何情况下都有着一样的期望效率，不会很快，也不会很慢。

private final Random random = new Random();

private int findPivot(int[] nums, int i, int j) {
    return random.nextInt(j - i + 1) + i;
}

用最左两个不同元素中的较大者作 pivot

这也是一种效率较高的pivot选取方法，从选取范围的最左边开始找，找到两个不同的元素，并返回其中较大者的下标。
但是这也是一种不能很好适应极端情况的方法，比如当数组中所有元素都相同时，该方法的效率就会很差。

private int findPivot(int[] nums, int i, int j) {
    int k = i + 1;
    while (k <= j) {
        if (nums[i] != nums[k]) return nums[i] > nums[k] ? i : k;
        else k++;
    }
    return i;
}