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 ) ；退化为冒泡排序的情况
网友评论