快速排序之3路排序算法

快速排序中的3路排序算法，除了具备普通快速排序的速度外，主要是针对集合汇总相同元素做了优化。

package com.proaholic.algs.sort.qsortv4;

import java.util.Arrays;
import java.util.Random;

// 快速排序之3路排序算法
// 如果数组元素都是一样，也会交换，但不会退化
public class QuickSortV4 {

    private static Random random = new Random();

    private QuickSortV4() {
    }

    public static <E extends Comparable<E>> void sort3ways(E[] arr) {
        sort3ways(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort3ways(E[] arr, int l, int r) {

        if (l >= r) return;
        int p = l + random.nextInt(r-l+1);
        swap(arr, l, p);
        // arr[l+1, lt] < v, arr[lt+1, i - 1] == v, arr[gt, r] > v
        int lt = l, i = l + 1, gt = r + 1;
        while(i < gt){
            if(arr[i].compareTo(arr[l]) < 0) {
                lt++;
                swap(arr, i, lt);
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                gt--;
                swap(arr,i, gt);
                // i 不用++ 因为 gt-- 这个值交换到 i 位置
            } else { // arr[i] == arr[l]å
                i++;
            }
        }
        swap(arr, l, lt);
        // arr[l, lt-1] < v, arr[lt, gt - 1] == v, arr[gt, r] > v
        sort3ways(arr, l, lt - 1);
        sort3ways(arr, gt, r);
    }

    private static <E> void swap(E[] arr, int i, int j) {
        // System.out.println("i="+i+",j="+j);
        if(i == j) return;
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}