快速排序的Java实现以及算法优化

  public static void sort(Comparable[] a,int lo,int hi){
        if (lo>=hi) return;
        int j = partition(a,lo,hi);
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }

  public static int partition(Comparable[] a,int lo,int hi){
        //左右扫描的指针
        int i=lo,j=hi+1;
        //切分元素
        Comparable v = a[lo];

        while (true){
            //左指针扫描直到遇到比v大的数字停止
            while (less(a[++i],v)) if (i==hi) break;
            while (less(v,a[--j])) if (j==lo) break;
            if (i>=j) break;
            swap(a,i,j);
        }
        swap(a,lo,j);
        return j;
    }

  public static boolean less(Comparable x,Comparable y){
        return x.compareTo(y)<0;
    }

    public static  void swap(T[] a, int i, int j){
        T x =a[i];
        a[i] = a[j];
        a[j] = x;
    }

   //此元素为切换标准元素，此参数和系统相关，在5-15内任意值大多数情况下让人满意
   private static final int M = 8;
   
   private static void BetterSort(Comparable[] a,int lo,int hi){
        //数组中元素小于M 转换为插入排序
        if (lo+M>=hi) { InsertSort(a); return;}
        int j = partition(a,lo,hi);
        sort(a, lo, j-1);
        sort(a, j+1,hi);
    }

应用场景

1. 待排序数组中有大量重复元素

    public static void threeQuickSort(Comparable[] a,int lo,int hi){
        //[lo..lt] : <切分元素v的位置
        //[lt..i] : ==切分元素v的位置
        //[i..gt] : 未确定位置
        //[gt..hi] : >v 的位置
        if (lo>=hi) return;
        int lt = lo,gt = hi,i=lo+1;
        //取第一个元素为切分点 保证随机性可以随机选取
        Comparable v = a[lo];

        while (i<=gt){
            int cmp = a[i].compareTo(v);
            if (cmp<0) swap(a,i++,lt++);
            else if (cmp>0) swap(a,gt--,i);
            else i++;
        }
        sort(a,lo,lt-1);
        sort(a,gt+1,hi);
    }