package com.cyq7on.practice.sort;


public class QuickSort3Ways extends Sort {

    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        swap(arr, left, (int) ((right - left) * Math.random() + left));
        int pivot = arr[left];

        int lt = left;     // arr[l+1,lt] < v
        int gt = right + 1; // arr[gt,r] > v
        int i = left + 1;    // arr[lt+1,i) == v
        while (i < gt) {
            if (arr[i] > pivot) {
                swap(arr, i, gt - 1);
                gt--;
            } else if (arr[i] < pivot) {
                swap(arr, i, lt + 1);
                lt++;
                i++;
            } else {
                i++;
            }
        }
        swap(arr, left, lt);
        quickSort(arr, left, lt);
        quickSort(arr, gt + 1, right);
    }


    public static void main(String[] args) {
        test(InsertionSort.class.getName(), 50000, 1, 10);
        test(SelectionSort.class.getName(), 50000, 1, 10);
        test(QuickSort3Ways.class.getName(), 50000, 1, 10);
        test(QuickSort2Ways.class.getName(), 50000, 1, 10);
        test(QuickSort.class.getName(), 50000, 1, 10);
    }
}

@@ -862,32 +862,63 @@
 arr, left, lt);%0A
+        //%E6%B3%A8%E6%84%8Flt%E6%98%AFleft%EF%BC%8C%E7%AD%89%E4%BA%8Ev%EF%BC%8C%E6%89%80%E4%BB%A5%E9%9C%80%E8%A6%81-1%0A
         quickSor
@@ -924,32 +924,36 @@
 rt(arr, left, lt
+ - 1
 );%0A        quick
@@ -964,20 +964,16 @@
 (arr, gt
- + 1
 , right)

fix bugs 三路快排