1,数组的parition过程

parition(分割)

例题1

调整有序数组arr,调整arr使得这个数组的左半部分有序且不重复,但右不一定有序

//两个变量,cur一直向前移动,pre一直被比较
public static int partition1(int[] arr)
    {
        int pre=0;
        int cur=0;
        while(cur!=arr.length)
        {
            if(arr[cur]!=arr[pre])
            {
                swap(arr,++pre,cur++);
            }
            else
            {
                cur++;
            }
        }
        System.out.println(Arrays.toString(arr));
        return 0;
    }

优化之后的代码

public static void partition2(int[] arr)
    {
        if(arr==null||arr.length<2)
        {
            return ;
        }
        int u=0;//pre
        int i=1;//cur
        while(i!=arr.length)
        {
            if(arr[i++]!=arr[i])
            {
                swap(arr,i-1,u++);
            }
        }
    }

例题2

荷兰国旗问题

public static int partition(int[] arr,int pivot)
    {
        int less=-1;
        int more=arr.length;
        int cur=0;
        while(cur<more)
        {
            if(arr[cur]>pivot)
            {
                swap(arr,cur,--more);
            }else if(arr[cur]<pivot)
            {
                swap(arr,cur++,++less);
            }else 
            {
                cur++;
            }
        }
        System.out.println(Arrays.toString(arr));
        System.out.println(cur+" "+more+" "+less);
        return cur;
    }

注意开始时的三个变量,cur,less,more,其含义为
cur表示一直在移动的下标,less表示最小区,开始时,没有一个元素在最小区,所以为-1,more和less恰好相反,表示最大区开始值为arr.length
我们来看一下运行的结果:

运行结果

我们看到less区为0到7,more区为9到最后,而且我们发现cur等于more,这是恰好是循环跳出的条件
我们在回过头来看一下核心逻辑

 while(cur<more)
        {
            if(arr[cur]>pivot)//如果当前的值大于比较的值
            {
                swap(arr,cur,--more);//将more区的前一个元素和当前的元素进行交换
            }else if(arr[cur]<pivot)
            {
                swap(arr,cur++,++less);//将less区的前一个元素和当前的元素进行交换
            }else 
            {
                cur++;
            }
        }

这里有一个问题,为什么和++less位置交换时,可以cur++,而和--more区域的交换时,cur不会++

cur++的原因

2,修改parition方法的参数

在上面使用的时候开始的区域默认是0,结束的区域默认是arr.length-1,这时候我们将开始的下标和结束的下标都改成不确定的值,然后将返回值设置为一个数组,其含义是arr[0]表示less的区域,arr[1]表示more的区域

public static int[] parition(int[] arr,int l,int r,int pivot)
    {
        int less=l-1;
        int more=r+1;
        int cur=0;
        while(cur<more)
        {
            if(arr[cur]>pivot)
            {
                swap(arr,cur,--more);
            }else if(arr[cur]<pivot)
            {
                swap(arr,cur++,++less);
            }else 
            {
                cur++;
            }
        }
        return new int[]{less+1,more-1};
    }

这时候我们就开始学习快速排序了

3,快速排序

public static void quickSort(int[] arr)
    {
        if(arr==null||arr.length==0)
        {
            return ;
        }
        quickSort(arr,0,arr.length-1);
    }
    
    public static void quickSort(int[] arr,int l,int r)
    {
        if(l<r)
        {
            int[] p=parition(arr, l, r, arr[r]);
            quickSort(arr,l,p[0]-1);
            quickSort(arr,p[1]+1,r);
        }
    }
    
    public static int[] parition(int[] arr,int l,int r,int pivot)
    {
        int less=l-1;
        int more=r+1;
        int cur=l;
        while(cur<more)
        {
            if(arr[cur]<pivot)
            {
                swap(arr,++less,cur++); 
            }
            else if(arr[cur]>pivot)
            {
                swap(arr,--more,cur);   
            }
            else
            {
                cur++;
            }
        }
        return new int[]{less+1,more-1};
    }

快速排序需要注意的是,边界问题,less,more什么时候加1,什么时候减1
parition返回的是less区域的后一个值,more区域的前一个值,所以在递归调用的时候p[0]-1,p[1]+1.
然后我们注意到,每一个的parition的过程我们都是使用arr[r]作为划分值的,即当前子数组的最后一个元素.

4,快速排序的优化以及代码的简化

当快速排序的数组本身是倒叙的,那么我们每次都取子数组的最后一个元素,这时候就是O(n^2)的时间复杂度,为了简化它,我们可以在数组中选择一个随机的元素作为划分值
从减少代码量的角度我们可以减少一个变量,pivot,即每一次都默认使用最后一个元素,而不用传入

public static void quickSort(int[] arr)
    {
        if(arr==null||arr.length==0)
        {
            return ;
        }
        quickSort(arr,0,arr.length-1);
    }
    
    public static void quickSort(int[] arr,int l,int r)
    {
        if(l<r)
        {
            swap(arr,l+(int)(Math.random()*(r-l+1)),r);//我们将数组中随意一个元素和结尾的元素交换
            int[] p=parition(arr, l, r);
            quickSort(arr,l,p[0]-1);
            quickSort(arr,p[1]+1,r);
        }
    }
    
    public static int[] parition(int[] arr,int l,int r)
    {
        int less=l-1;
        int more=r;//arr[r]作为划分的元素
        int cur=l;
        while(cur<more)
        {
            if(arr[cur]<arr[r])
            {
                swap(arr,++less,cur++); 
            }
            else if(arr[cur]>arr[r])
            {
                swap(arr,--more,cur);   
            }
            else
            {
                cur++;
            }
        }
        swap(arr,r,more);//最后交换即可
        return new int[]{less+1,more};//注意到这是的边界条件
    }
    

5,快速排序的分析

快速排序的分析

快速排序的空间复杂度来自于递归要保留现场
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况