详解Java双轴快速排序算法
作者:bigsai 发布时间:2023-10-05 15:50:14
一、前言
首选,双轴快排也是一种快排的优化方案,在JDK的Arrays.sort()中被主要使用。所以,掌握快排已经不能够满足我们的需求,我们还要学会双轴快排的原理和实现才行。
二、回顾单轴快排
单轴快排也就是我们常说的普通快速排序,对于快速排序我想大家应该都很熟悉:基于递归和分治的,时间复杂度最坏而O(n2),最好和平均情况为O(nlogn).
而快排的具体思路也很简单,每次在待排序序列中找一个数(通常最左侧多一点),然后在这个序列中将比他小的放它左侧,比它大的放它右侧。
如果运气肯不好遇到O(n)平方的,那确实就很被啦:
实现起来也很容易,这里直接贴代码啦:
private static void quicksort(int [] a,int left,int right)
{
int low=left;
int high=right;
//下面两句的顺序一定不能混,否则会产生数组越界!!!very important!!!
if(low>high)//作为判断是否截止条件
return;
int k=a[low];//额外空间k,取最左侧的一个作为衡量,最后要求左侧都比它小,右侧都比它大。
while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
{
while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
{
high--;
}
//这样就找到第一个比它小的了
a[low]=a[high];//放到low位置
while(low<high&&a[low]<=k)//在low往右找到第一个大于k的,放到右侧a[high]位置
{
low++;
}
a[high]=a[low];
}
a[low]=k;//赋值然后左右递归分治求之
quicksort(a, left, low-1);
quicksort(a, low+1, right);
}
三、双轴快排分析
咱们今天的主题是双轴快排,双轴和单轴的区别你也可以知道,多一个轴,前面讲了快排很多时候选最左侧元素以这个元素为轴将数据划分为两个区域,递归分治的去进行排序。但单轴很多时候可能会遇到较差的情况就是当前元素可能是最大的或者最小的,这样子元素就没有被划分区间,快排的递推T(n)=T(n-1)+O(n)从而为O(n2).
双轴就是选取两个主元素理想将区间划为3部分,这样不仅每次能够确定元素个数增多为2个,划分的区间由原来的两个变成三个,最坏最坏的情况就是左右同大小并且都是最大或者最小,但这样的概率相比一个最大或者最小还是低很多很多,所以双轴快排的优化力度还是挺大的。
3.1、总体情况分析
至于双轴快排具体是如何工作的呢?其实也不难理解,这里通过一系列图讲解双轴快排的执行流程。
首先在初始的情况我们是选取待排序区间内最左侧、最右侧的两个数值作为pivot1
和pivot2
.作为两个轴的存在。同时我们会提前处理数组最左侧和最右侧的数据会比较将最小的放在左侧。所以pivot1<pivot2.
而当前这一轮的最终目标是,比privot1小的在privot1左侧,比privot2大的在privot2右侧,在privot1和privot2之间的在中间。
这样进行一次后递归的进行下一次双轴快排,一直到结束,但是在这个执行过程应该去如何处理分析呢?需要几个参数呢?
假设知道排序区间[start,end]。数组为arr,
pivot1=arr[start],pivot2=arr[end]
还需要三个参数left,right和k。 l
left初始为start,[start,left]区域即为小于等于pivot1小的区域(第一个等于)。
right与left对应,初始为end,[right,end]为大于等于pivot2的区域(最后一个等于)。
k初始为start+1,是一个从左往右遍历的指针,遍历的数值与pivot1,pivot2比较进行适当交换,当k>=right即可停止。
3.2、k交换过程
然后你可能会问k遍历时候究竟怎么去交换?left和right该如何处理呢?不急我带你慢慢分析,首先K是在left和right中间的,遍历k的位置和pivot1,pivot2进行比较:
如果arr[k]<pivot1,那么先++left,然后swap(arr,k,left),因为初始在start在这个过程不结束start先不动。然后k++;继续进行
而如果arr[k]>pivot2.(区间自行安排即可)有点区别的就是right可能连续的大于arr[k],比如9 3 3 9 7
如果我们需要跳过7前面9到3才能正常交换,这和快排的交换思想一致,当然再具体的实现上就是right--到一个合适比arr[k]小的位置。然后swap(arr,k,right)切记此时k不能自加。因为带交换的那个有可能比pivot1还小要和left交换。
如果是介于两者之间,k++即可
3.3、收尾工作
在执行完这一趟即k=right之后,即开始需要将pivot1和pivot2的数值进行交换
swap(arr, start, left);
swap(arr, end, right);
然后三个区间根据编号递归执行排序函数即可。
四、双轴快排代码
在这里,分享下个人实现双轴快排的代码:
import java.util.Arrays;
public class 双轴快排 {
public static void main(String[] args) {
int a[]= {7,3,5,4,8,5,6,55,4,333,44,7,885,23,6,44};
dualPivotQuickSort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
private static void dualPivotQuickSort(int[] arr, int start, int end) {
if(start>end)return;//参数不对直接返回
if(arr[start]>arr[end])
swap(arr, start, end);
int pivot1=arr[start],pivot2=arr[end];//储存最左侧和最右侧的值
//(start,left]:左侧小于等于pivot1 [right,end)大于pivot2
int left=start,right=end,k=left+1;
while (k<right) {
//和左侧交换
if(arr[k]<=pivot1)
{
//需要交换
swap(arr, ++left, k++);
}
else if (arr[k]<=pivot2) {//在中间的情况
k++;
}
else {
while (arr[right]>=pivot2) {//如果全部小于直接跳出外层循环
if(right--==k)
break ;
}
if(k>=right)break ;
swap(arr, k, right);
}
}
swap(arr, start, left);
swap(arr, end, right);
dualPivotQuickSort(arr, start, left-1);
dualPivotQuickSort(arr, left+1, right-1);
dualPivotQuickSort(arr, right+1, end);
}
static void swap(int arr[],int i,int j)
{
int team=arr[i];
arr[i]=arr[j];
arr[j]=team;
}
}
执行结果为:
来源:https://www.cnblogs.com/bigsai/p/13930945.html
猜你喜欢
- 详解java中的PropertyChangeSupport与PropertyChangeListenerjava中的PropertyChan
- 实现Java多态性的时候,关于方法调用的优先级:我们这样假设下,super(超类)、this(当前类对象)、show(方法)、object(
- 这篇文章主要介绍了Spring如何在一个事务中开启另一个事务,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需
- 1. maven项目导入idea报ComponentLookupException异常1.1. 问题描述最近将IDEA 升级到 Intell
- 前言这篇博客介绍Java环境的配置,主要是安装JDK,以及path、JAVA_hOME、CLASSPAT的配置,还会介绍配置这些的原因。一.
- 本文主要对SpringBoot2.x参数校验进行简单总结,其中SpringBoot使用的2.4.5版本。一、引入依赖<dependen
- 对于自定义注解这里就不唠叨了,百度一大堆,这里有我一个自定义注解@Retention(RetentionPolicy.RUNTIME)@Ta
- 1、IndexTagController.java@GetMapping("/tags/{id}") &n
- 背景今天学习Springboot,但是用的apache-maven 3.0 ,导入springboot1.5.19 ,Maven项目老是爆红
- 1.微信配置信息 global.properties2.方法wxpay用于生成预支付订单信息方法notifyWeiXinPay用于微信支付成
- 改了个bug,发现这个东西以前不知道,搜索了一下,看到的都是长篇大论,还谈js的源码,也是醉了。我就简单的说说这个是干啥的。简单说:就是触发
- 这篇文章主要介绍了springboot跨域CORS处理代码解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- 页面提交请求参数有两种,一种是form格式提交,一种json格式提交通常情况下我们使用的都是form格式提交的数据,数据格式:k=v&
- 这篇文章主要介绍了Springboot整合MybatisPlus的实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定
- 本文实例讲述了java实现新浪微博Oauth接口发送图片和文字的方法。分享给大家供大家参考。具体如下:基于网上很多人利用新浪api开发新浪微
- 1.<constant name="struts.i18n.encoding" value="UTF-8
- 前言我们经常会被问到这么一个问题:SpringBoot相对于spring有哪些优势呢?其中有一条答案就是SpringBoot自动注入。那么自
- 一、题目描述题目:模拟一个简单的银行系统,使用两个不同的线程向同一个账户存钱。实现:使用特殊域变量volatile实现同步。二、解题思路创建
- 自定义工具类PropertyUtil,并在该类的static静态代码块中读取properties文件内容保存在static属性中以供别的程序
- 在Spring Boot Actuator中提供很多像health、metrics等实时监控接口,可以方便我们随时跟踪服务的性能指标。Spr