快速排序

基本思想
快速排序也采用了分治的思想。

实现
随机把一个数作为基准（一般使用第一个数），把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

步骤分解

Java代码

public void quickSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    // 找出基准分割界点
    int middle = helper(nums, left, right);
    // 左边继续排序
    quickSort(nums,left, middle-1);
    // 右边继续排序
    quickSort(nums, middle+1,right);
}

private int helper(int[] nums, int left, int right) {
    // 以val为基准，把比val大的数放一边，比val小的数放一边
    int val = nums[left];
    while (left < right) {
        while (val <= nums[right] && left < right) {
            right--;
        }
        nums[left] = nums[right];
        while (val >= nums[left] && left < right) {
            left++;
        }
        nums[right] = nums[left];
    }
    nums[left] = val;
    return left;
}

时间复杂度

• 最优情况：被选出来的基准值都是当前子数组的中间数。
  这样的分割，能保证对于一个规模大小为 n 的问题，能被均匀分解成两个规模大小为 n/2 的子问题（归并排序也采用了相同的划分方法），时间复杂度就是：T(n) = 2×T(n/2) + O(n)。
  把规模大小为 n 的问题分解成 n/2 的两个子问题时，和基准值进行了 n-1 次比较，复杂度就是 O(n)。很显然，在最优情况下，快速排序的复杂度也是 O(nlogn)。

• 最坏情况：基准值选择了子数组里的最大或者最小值
  每次都把子数组分成了两个更小的子数组，其中一个的长度为 1，另外一个的长度只比原子数组少 1。算法复杂度为 O(n2)。

END!