快速排序

算法分析

• 快速排序算法是基于分治策略的另一个排序算法，其基本思想是，对于输入的子数组a[l:r] ，按以下三个步骤进行排序。
  • 分解（Divide)：以a[r]为基准元素将a[l:r]划分成3段a[l:q-1], a[q]和a[q+1:r]，使a[l:q-1]中任何一个元素小于等于a[q]，而a[q+1]:r]中任何一个元素大于等于a[q]，下标q在划分过程中确定。
  • 递归求解（Conquer)：通过递归调用快速排序算法分别对a[l:q-1]和a[q+1:r]进行排序。
  • 合并（Merge)：由于对a[l:q-1]和a[q+1:r]的排序是就地进行的，所以在a[l:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[l:r]就已排好序。

代码实现

流程图

public class Solution {

    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 9, 7, 6};
        System.out.println("排序前：" + Arrays.toString(nums));
        new Solution().quickSort(nums, 0, nums.length - 1);
        System.out.println("排序后：" + Arrays.toString(nums));
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int p = randomPartition(nums, start, end);
            quickSort(nums, start, p - 1);
            quickSort(nums, p + 1, end);
        }
    }

    public int randomPartition(int[] nums, int start, int end) {
        Random random = new Random();
        int i = random.nextInt(end - start + 1) + start;
        swap(nums, end, i);
        return partition(nums, start, end);
    }

    public int partition(int[] nums, int start, int end) {
        int pivot = nums[end];
        int index = start;
        for (int i = start; i < end; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, index);
                index++;
            }
        }
        swap(nums, index, end);
        return index;
    }

    public void swap(int[] nums, int i1, int i2) {
        int temp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = temp;
    }
}

• quickSort(int[] nums,int l,int r)：对数组a[l:r]进行排序。
• int Partition(int[] nums, int l, int r)：对数组nums[l:r]，划分后返回一个数组元素下标q，使得该数组元素在本数组部分中属于数值大小中位，即小于nums[q]的元素在nums[q]的左边，大于nums[q]的元素在nums[q]的右边。

算法改进

• 容易看到，快速排序算法的性能取决于划分的对称性，通过修改函数Partition可以设计出采用随机选择策略的快速排序算法。
• 在快速排序算法的每一步中，当数组还没有被划分时，可以在a[l:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。

public int randomizedPartition(int[] nums, int l, int r) {
    int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为基准。
    swap(nums, r, i);
    return partition(nums, l, r);
}

• RandomizedPartition(int[] nums, int l, int r) ：与Partition(int[] nums, int l, int r)类似，但是会使用随机数使划分基准的选择是随机的。