雙軸快排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);
       }
       /**
        * j就是用來移動周遊比較該數字應該存放的空間
        * i最後就是比start大的比end小的區間的開始下标
        * k最後就是比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;
           }
       }
       /**
        * 把第一個基準值放在i的前面
        * 最後一個基準值放在j的後面
        * (i,j)就是比剛開始的i大但是比剛開始的j小
        */
       exchange(arr,start,i -1);
       exchange(arr,end,k+1);
       /**
        * 現在就會出來五個部分
        * (0,i-1-1)
        * i-1
        * (i,k)
        * k + 1 (也就是j)
        * (k+1+1,end)
        * 對這五個部分分别遞歸排序
        */
       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));
   }
}
           

• 排序前

  

• 排序後