排序算法学习

package com.dominic;
import edu.princeton.cs.algs4.StdRandom;
public class Sort {
    private static boolean less(Comparable x, Comparable y)
    { return x.compareTo(y) < 0; }
    private static void exchange(Comparable[] a, int i, int j)
    {    Comparable t = a[i]; a[i] = a[j]; a[j] = t;}
    public static void show(Comparable[] a){
        for (Comparable comparable : a)
            System.out.print(comparable + " ");
        System.out.println();
    }
    public static boolean isSorted(Comparable[] a){
        for (int i = 1;i < a.length;i++)
            if(less(a[i],a[i-1]))
                return false;
            return true;
    }
    public static void selection(Comparable[] a){
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++)
                if (less(a[j], a[min])) min = j;
                exchange(a,i,min);
        }
    }
    public static void insertion(Comparable[] a){
        int N = a.length;
        for (int i=1;i<N;i++){
            for (int j = i;j>0&&less(a[j],a[j-1]);j++)
                exchange(a,j,j-1);
        }
    }
    public static void shell(Comparable[] a){
        int N = a.length;
        int h = 1;
        while (h < N/3)
            h = 3*h+1;
        while (h >= 1){
            for (int i = h;i < N;i++){
                for(int j = i;j>=h && less(a[j],a[j-h]);j-=h)
                    exchange(a,j,j-h);
            }
            h = h/3;
        }
    }
    public static void merge(Comparable[] a){
        Comparable[] aux = new Comparable[a.length];
        _merge_sort(a, aux,0, a.length-1);
    }
    private static void _merge_sort(Comparable[] a, Comparable[] aux, int lo, int hi){
        if (hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        _merge_sort(a, aux, lo, mid);
        _merge_sort(a, aux, mid+1, hi);
        _merge(a, aux, lo, mid, hi);
    }
    private static void _merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi){
        int i = lo, j = mid + 1;
        if (hi + 1 - lo >= 0) System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
        for (int k = lo; k <= hi; k++){
            if      (i>mid)               a[k]=aux[j++];
            else if (j>hi)                a[k]=aux[i++];
            else if (less(aux[j],aux[i])) a[k]=aux[j++];
            else                          a[k]=aux[i++];
        }
    }
    public static void quick(Comparable[] a){
        StdRandom.shuffle(a);
        _quick_sort(a, 0, a.length-1);
    }
    private static void _quick_sort(Comparable[] a, int lo, int hi){
        if (hi <= lo) return;
        int j = _partition(a, lo, hi);
        _quick_sort(a, lo, j-1);
        _quick_sort(a, j+1, hi);
    }
    private static int _partition(Comparable[] a, int lo, int hi){
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while(true){
            while(less(a[++i],v)) if(i==hi) break;
            while(less(v,a[--j])) if(j==lo) break;
            if(i >= j) break;
            exchange(a, i, j);
        }
        exchange(a, lo, j);
        return j;
    }
    public static void quick3way(Comparable[] a){
        StdRandom.shuffle(a);
        _quick3way_sort(a, 0, a.length-1);
    }
    private static void _quick3way_sort(Comparable[] a, int lo, int hi){
        if (hi<=lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while(i <= gt){
            int cmp = a[i].compareTo(v);
            if (cmp<0) exchange(a, lt++, i++);
            else if (cmp > 0) exchange(a, i, gt--);
            else i++;
        }
        _quick3way_sort(a, lo, lt-1);
        _quick3way_sort(a, gt+1, hi);
    }
}