【算法与数据结构复习】| 快速排序

        今天刷力扣215.数组中第K个最大元素，题目要求用时间复杂度O(n)。因此跟着左程云算法课23复习了随机快速排序。

        随机快速排序的核心思想就是在数组中随机选一个值x，把<=x的值移到左边，>x的值移动到右边。x这个值必须在左边区间的最左边，也就是确定了x的位置就是这里，然后再分别递归调用对左右两边进行排序。

一、经典随机快速排序

        经典的随机快速排序，在QuickSort中先选定随机数x，然后partition返回x所在的位置下标。在partition过程中，设置一个a表示左边界，xi表示x的位置，最后要和a-1进行交换。下标<a的区间是<=x的区间，最后返回a-1。

    public void QuickSort1(int[] nums,int l,int r){if(l>=r){return;}int x=nums[l+ran.nextInt(r-l+1)];int mid=partition1(nums,l,r,x);QuickSort1(nums,l,mid-1);QuickSort1(nums,mid+1,r);}public int partition1(int[] nums,int l,int r,int x){int a=l;int xi=-1;for(int i=l;i<=r;i++){if(nums[i]<=x){swap(nums,a,i);if(nums[a]==x){xi=a;}a++;}}if(xi!=-1){swap(nums,a-1,xi);}return a-1;}

二、荷兰问题优化的随机快速排序

        在经典的随机快速排序中，有个不好的点就是如果一个数组中右多个相同的值x，那一次排序后只能确定一个x的位置，其他x还要继续参与排序。荷兰问题优化的思路在于，在partition的时候，将整个数组分成三部分，左边<x，中间=x，右边>x。那就需要设置两个边界值a和b，a表示左区间的越界值，b表示右区间的越界值。

    public static Random ran=new Random();public static int left;public static int right;public void QuickSort2(int[] nums,int l,int r){if(l>=r){return;}int x=nums[l+ran.nextInt(r-l+1)];partition2(nums,l,r,x);int left1=left;int right1=right;QuickSort2(nums,l,left1-1);QuickSort2(nums,right1+1,r);}public void partition2(int[] nums,int l,int r,int x){int a=l;int b=r;int i=l;while(i<=b){if(nums[i]<x){swap(nums,a,i);a++;i++;}else if(nums[i]==x){i++;}else{swap(nums,b,i);b--;}}left=a;right=b;}