详解Java双轴快速排序算法

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);		
}

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;
    }
}