双轴快排DualPivotQuicksort

java中Arrays.sort中的排序方法就是双轴快排

public class DualPivotQuicksort {
   public static void sort(Comparable[] arr ,int start , int end){
       if(start >= end)return;
       if(greater(arr[start] , arr[end]) > 0){
           exchange(arr,start,end);
       }
       
       int i = start +1;
       int j = start +1;
       int k = end - 1;
       while (j <= k){
           if(greater(arr[j],arr[start]) < 0){
               exchange(arr, j,i);
               i++;
               j++;
               continue;
           }
           if(greater(arr[j],arr[end]) > 0){
               exchange(arr,j,k);
               k--;
               continue;
           }
           if(greater(arr[j] , arr[start]) >= 0 && greater(arr[j] , arr[end]) <= 0){
               j++;
               continue;
           }
       }
       
       exchange(arr,start,i -1);
       exchange(arr,end,k+1);
       
       sort(arr,start,i-1-1);
       sort(arr,i,k);
       sort(arr,k+1+1,end);
   }
    private static void exchange(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static int greater(Comparable v , Comparable w){
        return v.compareTo( w );
    }
//greater(arr[j],arr[start]) == -1
   //测试代码
   public static void main(String[] args) {
       Integer[] nums = {6,1,7,4,5,2,3,9,1,7,8,2,3};
//       Integer[] nums = {23,7,5,8,0,2,1,43,22,3,9,1,7,8,2,3};
       DualPivotQuicksort.sort(nums,0,12);
//       DualPivotQuicksort.sort(nums,0,15);
       System.out.println(Arrays.toString(nums));
   }
}

• 排序前
  
• 排序后