public class QuickSort {
    
    /**
     * 快速排序（入口方法）
     */
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    
    /**
     * 快速排序递归实现（Lomuto 分区方案）
     */
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = lomutoPartition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    /**
     * Lomuto 分区方案
     * 选择最右侧元素作为基准
     */
    private static int lomutoPartition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;  // i 指向最后一个小于 pivot 的元素
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    /**
     * Hoare 分区方案（通常更高效，交换次数更少）
     */
    private static int hoarePartition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low - 1;
        int j = high + 1;
        
        while (true) {
            // 从左向右找到第一个大于等于 pivot 的元素
            do {
                i++;
            } while (arr[i] < pivot);
            
            // 从右向左找到第一个小于等于 pivot 的元素
            do {
                j--;
            } while (arr[j] > pivot);
            
            if (i >= j) {
                return j;
            }
            swap(arr, i, j);
        }
    }
    
    /**
     * 快速排序（三数取中法优化）
     * 使用三数取中法选择基准，避免最坏情况
     */
    public static void sortWithMedianOfThree(int[] arr) {
        quickSortMedian(arr, 0, arr.length - 1);
    }
    
    private static void quickSortMedian(int[] arr, int low, int high) {
        if (low < high) {
            // 使用三数取中法选择基准
            int mid = low + (high - low) / 2;
            // 将三个数的中位数放到 low 位置
            if (arr[mid] < arr[low]) swap(arr, low, mid);
            if (arr[high] < arr[low]) swap(arr, low, high);
            if (arr[high] < arr[mid]) swap(arr, mid, high);
            swap(arr, low, mid);  // 将中位数放到 low 位置
            
            int pivotIndex = hoarePartition(arr, low, high);
            quickSortMedian(arr, low, pivotIndex);
            quickSortMedian(arr, pivotIndex + 1, high);
        }
    }
    
    /**
     * 快速排序（三向切分，适用于大量重复元素）
     * Dijkstra 三向切分方案
     */
    public static void sortThreeWay(int[] arr) {
        quickSortThreeWay(arr, 0, arr.length - 1);
    }
    
    private static void quickSortThreeWay(int[] arr, int low, int high) {
        if (low >= high) return;
        
        int pivot = arr[low];
        int lt = low;      // arr[low..lt-1] < pivot
        int gt = high;     // arr[gt+1..high] > pivot
        int i = low + 1;   // arr[lt..i-1] == pivot
        
        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt, i);
                lt++;
                i++;
            } else if (arr[i] > pivot) {
                swap(arr, i, gt);
                gt--;
            } else {
                i++;
            }
        }
        
        quickSortThreeWay(arr, low, lt - 1);
        quickSortThreeWay(arr, gt + 1, high);
    }
    
    /**
     * 快速排序（泛型版本）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
        quickSortGeneric(arr, 0, arr.length - 1);
    }
    
    private static <T extends Comparable<T>> void quickSortGeneric(T[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partitionGeneric(arr, low, high);
            quickSortGeneric(arr, low, pivotIndex - 1);
            quickSortGeneric(arr, pivotIndex + 1, high);
        }
    }
    
    private static <T extends Comparable<T>> int partitionGeneric(T[] arr, int low, int high) {
        T pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j].compareTo(pivot) <= 0) {
                i++;
                T temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        T temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}