Quick Sort

快排主要逻辑：将数组用partition函数分为左右两部分，分别进行排序。

public void quickSort(int[] nums, int l, int r) {
    if (l >= r) return; // 记得加上=，否则每次相等的时候都要再进行一次没必要的递归。
    int mid = partition(nums, l, r);
    quickSort(nums, l, mid - 1);
    quickSort(nums, mid + 1, r);
}

partition函数的逻辑是选定一个pivot作为基准，比它小的元素放在左边，大的放在右边。partition可以有多种方法

1.填坑法

public int partition1(int[] nums, int l, int r) {
    int pivot = nums[l];
    while (l < r) {
        while (l < r && nums[r] >= pivot) r--; // 从末尾开始寻找一个小于pivot的元素赋值到l指针
        nums[l] = nums[r];
        while (l < r && nums[l] < pivot) l++; // 从开头寻找一个大于等于pivot的元素赋值到r指针
        nums[r] = nums[l];
    }
    nums[l] = pivot;
    return l;
}

public void sort(int[] nums, int l, int r) {
    if (l >= r) return;
    int pivot = nums[l];
    int start = l, end = r;
    while (l < r) {
        while (l < r && nums[r] >= pivot) r--;
        nums[l] = nums[r];
        while (l < r && nums[l] < pivot) l++;
        nums[r] = nums[l];
    }
    nums[l] = pivot;

    sort(nums, start, l - 1);
    sort(nums, l + 1, end);
}

由于上面那段代码在元素相等时会有不必要的交换，所以while循环中也可以加上相等就不交换的条件。

while (l < r) {
    while (l < r && nums[r] >= pivot) r--;
    if (l < r) {
        nums[l] = nums[r];
        l++;
    }
    while (l < r && nums[l] < pivot) l++;
    if (l < r) {
        nums[r] = nums[l];
        r--;
    }
}

2.交换法

public int partition2(int[] nums, int l, int r) {
    int pivot = nums[l];
    while (l < r) {
        while (l < r && nums[r] >= pivot) r--;
        swap(nums, l, r);
        while (l < r && nums[l] < pivot) l++;
        swap(nums, l, r);
    }
    return l;
}

另一种交换法

// swap 2
public int partition2_1(int[] nums, int l, int r) {
    int pivot = nums[l];
    int lt = l + 1, gt = r;
    while (lt <= gt) {
        while (nums[lt] < pivot && lt <= gt) lt++;
        while (nums[gt] >= pivot && lt <= gt) gt--;
        if (lt < gt) {
            swap(nums, lt, gt);
        }
    }
    swap(nums, l, gt);
    return gt;
}

下面这个代码某些地方也叫双路快排..

public void sort2(int[] nums, int l, int r) {
    if (l >= r) return;
    int pivot = nums[l];
    int lt = l + 1, gt = r;
    while (true) {
        while (lt < r && nums[lt] < pivot) lt++;
        while (gt > l + 1 && nums[gt] > pivot) gt--;
        if (lt >= gt) break;
        swap(nums, lt, gt);
        lt++;
        gt--;
    }
    swap(nums, l, gt);
    sort2(nums, l, gt - 1);
    sort2(nums, gt + 1, r);
}

3.pindex法(在某些地方也叫普通快排): 循环中的数字依次和pivot比较，如果小于pivot，就和pIndex中的数字进行交换，保证pIndex前面的数字都是小于等于pivot的。最后将pindex中的数字和pivot交换。

public int partition3(int[] nums, int l, int r) {
    int pivot = nums[r];
    int pIndex = l;
    for (int i = l; i < r; i++) {
        if (nums[i] <= pivot) {
            swap(nums, i, pIndex);
            pIndex += 1;
        }
    }
    swap(nums, r, pIndex);
    return pIndex;
}

swap函数：

private void swap(int[] nums, int l, int r) {
    int tmp = nums[l];
    nums[l] = nums[r];
    nums[r] = tmp;
}

填坑法过程如下：

pIndex法:

优化

快排复杂度O(nlogn)，最坏复杂度O(n^2)出现在递归次数接近数组长度/partition极度不均匀的时候（本来的O(logn)变成了O(n)），如数组有序的情况下。

1.选择合适的pivot

随机化: 随机化选择一个index和最左边数字交换

public int rand(int[] nums, int l, int r) {
    Random random = new Random();
    int randomIndex = random.nextInt(r - l + 1) + l;
    swap(nums, l, randomIndex);
    return nums[l];
}
// int pivot = rand(nums, l, r);

三数取中: 使用数组中左边，中间，右边的三个数字进行排序，选择其中的中位数（将中位数放在数组的最开始）

public int middleOfThree(int[] nums, int l, int r) {
    int mid = l + (r - l) / 2;

    if (nums[l] > nums[r]) swap(nums, l, r);     // l < r
    if (nums[mid] > nums[r]) swap(nums, mid, r); // mid < r
    if (nums[mid] > nums[l]) swap(nums, mid, l); // mid < l < r

    return nums[l];
}
// int pivot = middleOfThree(nums, l, r);

这两种方法对数组重复，如{10, 10, 10, 10, 10, 10, 10, 10, 10, 10}没什么改进。

2.考虑数组大小

小数组选用插入排序

public void quickSort(int[] nums, int l, int r) {
    if (l - r <= 10) {
        insertionSort(nums);
    }
    if (l >= r) return;
    int mid = partition(nums, l, r);
    quickSort(nums, l, mid - 1);
    quickSort(nums, mid + 1, r);
}

3.处理重复元素

三路快排: 将所有元素分为3个区域，将重复元素聚集到中间部分(lt, gt)，不再对这些元素进行递归操作。

public void sort3(int[] nums, int l, int r) {
    if (l >= r) return;
    int lt = l, i = l + 1, gt = r;
    int pivot = nums[l];
    while (i <= gt) {            // gt边界的数字和pivot还需要再比较一次
        if (nums[i] < pivot) {
            swap(nums, lt++, i++); // lt和i交换完之后同时右移
        } else if (nums[i] > pivot) {
            swap(nums, i, gt--); // 后面的数字交换过来之后还要再比一次
        } else {
            i++;
        }
    }
    // 只需要再次递归lt左边和gt右边的部分
    sort3(nums, l, lt - 1);  
    sort3(nums, gt + 1, r);
}