public class ThreeWayQuickSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        threeWayQuickSort(arr, 0, arr.length - 1);
    }

    private static void threeWayQuickSort(int[] arr, int low, int high) {
        if (low >= high) return;

        // 选择基准值（这里选第一个元素）
        int pivot = arr[low];
        int lt = low;      // 小于 pivot 的右边界
        int gt = high;     // 大于 pivot 的左边界
        int current = low; // 当前遍历指针

        while (current <= gt) {
            if (arr[current] < pivot) {
                swap(arr, lt, current);
                lt++;
                current++;
            } else if (arr[current] > pivot) {
                swap(arr, current, gt);
                gt--;
            } else {
                current++;
            }
        }

        // 递归处理小于和大于区域
        threeWayQuickSort(arr, low, lt - 1);
        threeWayQuickSort(arr, gt + 1, high);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        sort(arr);
        System.out.println(Arrays.toString(arr)); 
        // 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
    }
}