Java经典快排思想以及快排的改进讲解
一.经典快排思想
前提条件：给定一个无序数组arr
- 取这个数组最后一个数num作为标准，将前面部分的数分为两部分，使得<=num的部分在左边，>num的数在右边；
- 然后将最后一个数和>num部分的第一个数进行交换，就使得原本在数组最后位置的num找到了正确的位置，它的左边都是比它小的以及和它一样的数，右边都是比它大的数
- 回到1，进行递归或迭代，使得所有的数都找到正确的位
二.通过荷兰国旗问题改进快排
什么是荷兰国旗问题？
已知一个整形数组arr，和一个整数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
解决思路：
遍历数组
- 1.若比num小，当前位置和小于的最后一个位置+1的值交换，并当前位置++；
- 2.若比num大，当前位置和大于的第一个位置-1的值交换；
- 3.若等于num的值，当前位置++；
附上代码：
publicstaticvoidNetherlandsFlag(int[]arr,intL,intR,intnum){
inti=L;
intp1=L-1;
intp2=R+1;
//终止条件：当前数的位置在大于区的前一个
while(i
我们可以发现，荷兰国旗问题和经典快排不同的就只是将<=num改为了
三.在这基础上将其改为随机快排
随机快排改进的地方只是在选取数的时候，将每次都选取最后位置的数改为选取随机的一个数作为num，这样做的好处是什么呢？
1.选取最后一个数：如果是一个已经排好序的数组，每次找到位置之后，左边是要进行排序的部分，数组长度是原长度-1，它的时间复杂度就是O(N^2)；如果每次找到的数都是中间的位置，它的时间复杂度就只有O(logN)
2.然而以随机数作为选取的标准num的时候，因为是随机的，就只能通过数学期望去计算它的时间复杂度，时间复杂度是O(logN)
下面附上最终的快排代码及注释
/*
*swap(int[]arr,inti,intj);是将arr数组的i和j位置上的数交换的方法
*/
publicstaticvoidquickSort(int[]arr){
//如果为空或长度为1不需要排序，直接返回
if(arr==null||arr.length<2)
return;
else
quickSort(arr,0,arr.length-1);
}
//递归排序
publicstaticvoidquickSort(int[]arr,intL,intR){
if(Lnum){
swap(arr,curr,--more);
}else{
curr++;
}
}
//返回等于区的左右边界的下标，通过下标确定小于区和大于区递归时的参数
returnnewint[]{less+1,more-1};
}
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。