「排序算法」图解双轴快排

bigsai

关注

发布于: 2020 年 11 月 05 日

原创公众号：bigsai

前言

在排序算法中，快排是占比非常多的一环，但是快排其思想一直被考察研究，也有很多的优化方案。这里主要讲解双轴快排的思想和实现。

首选，双轴快排也是一种快排的优化方案，在 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 个，划分的区间由原来的两个变成三个，最坏最坏的情况就是左右同大小并且都是最大或者最小，但这样的概率相比一个最大或者最小还是低很多很多，所以双轴快排的优化力度还是挺大的。

总体情况分析

至于双轴快排具体是如何工作的呢？其实也不难理解，这里通过一系列图讲解双轴快排的执行流程。

首先在初始的情况我们是选取待排序区间内最左侧、最右侧的两个数值作为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 即可停止。

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++即可

收尾工作

在执行完这一趟即 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;    }}

复制代码

执行结果为：

好啦，到这里双轴快排就实现完成啦。至于算法分析，希望在评论区和你们讨论哦！

原创不易，欢迎关注「bigsai」回复 bigsai 领取 Java 进阶资料：

发布于: 2020 年 11 月 05 日阅读数: 36

bigsai

关注

前方唯有坚持不懈！ 2020.10.29 加入

原创公众号：bigsai 回复bigsai获取大厂进阶资料！

发布

暂无评论

创作场景

「排序算法」图解双轴快排

前言

回顾单轴快排

双轴快排分析

总体情况分析

k 交换过程

收尾工作

双轴快排代码

bigsai

评论