排序算法

public class Insertion {
    private Insertion() { }

    public static void sort(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--) {
                exch(a, j, j-1);
            }
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}

func InsertionSort(A []int) {
    for i := 1; i < len(A); i++ {
        for j := i; j > 0 && A[j] < A[j-1]; j-- {
            A[j], A[j-1] = A[j-1], A[j]
        }
    }
}

public class Merge {
    private Merge() { }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        int i = lo, j = mid+1;
        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++];
        }
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
}

func MergeSort(A []int) {
    if len(A) <= 1 {
        return
    }
    mid := len(A) / 2
    L := A[:mid]
    R := A[mid:]
    MergeSort(L)
    MergeSort(R)
    merge(L, R, A)
}

func merge(L, R, A []int) {
    C := make([]int, len(A))
    i := 0
    j := 0
    for k := 0; k < len(C); k++ {
        if i >= len(L) {
            C[k] = R[j]
            j++
        } else if j >= len(R) {
            C[k] = L[i]
            i++
        } else if L[i] < R[j] {
            C[k] = L[i]
            i++
        } else {
            C[k] = R[j]
            j++
        }
    }
    copy(A, C)
}

public class MergeBU {
    private MergeBU() { }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        int i = lo, j = mid+1;
        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 sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int len = 1; len < n; len *= 2) {
            for (int lo = 0; lo < n-len; lo += len+len) {
                int mid  = lo+len-1;
                int hi = Math.min(lo+len+len-1, n-1);
                merge(a, aux, lo, mid, hi);
            }
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
}

func MergeBUSort(A []int) {
    for length := 1; length < len(A); length *= 2 {
        for lo := 0; lo < len(A)-length; lo += length * 2 {
            mid := lo + length
            var hi int
            if lo+length*2-1 < len(A)-1 {
                hi = lo + length*2
            } else {
                hi = len(A)
            }
            merge(A[lo:mid], A[mid:hi], A[lo:hi])
        }
    }
}
func merge(L, R, A []int) {
    C := make([]int, len(A))
    i := 0
    j := 0
    for k := 0; k < len(C); k++ {
        if i >= len(L) {
            C[k] = R[j]
            j++
        } else if j >= len(R) {
            C[k] = L[i]
            i++
        } else if L[i] < R[j] {
            C[k] = L[i]
            i++
        } else {
            C[k] = R[j]
            j++
        }
    }
    copy(A, C)
}

public class Quick {
    private Quick() { }

    public static void sort(Comparable[] a) {
        shuffle(a);
        sort(a, 0, a.length - 1);
    }

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

    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int 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;

            exch(a, i, j);
        }

        exch(a, lo, j);

        return j;
    }

    private static boolean less(Comparable v, Comparable w) {
        if (v == w) return false;
        return v.compareTo(w) < 0;
    }

    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static void shuffle(Object[] a) {
        validateNotNull(a);
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int r = i + uniform(n-i);     // between i and n-1
            Object temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    private static void validateNotNull(Object x) {
        if (x == null) {
            throw new IllegalArgumentException("argument must not be null");
        }
    }

    private static int uniform(int n) {
        if (n <= 0) throw new IllegalArgumentException("argument must be positive: " + n);
        return random.nextInt(n);
    }
}

func QuickSort(A []int) {
    shuffle(A)
    quickSort(A)
}

func quickSort(A []int) {
    j := partition(A, 0, len(A))
    if j > 0 {
        quickSort(A[:j])
    }
    if j < len(A)-1 {
        quickSort(A[j+1:])
    }
}

func partition(A []int, lo, hi int) int {
    pivot := A[lo]
    i := lo + 1
    for j := lo + 1; j < hi; j++ {
        if A[j] < pivot {
            A[i], A[j] = A[j], A[i]
            i++
        }
    }
    A[lo], A[i-1] = A[i-1], A[lo]
    return i - 1
}

func shuffle(slice []int) {
    r := rand.New(rand.NewSource(time.Now().Unix()))
    for len(slice) > 0 {
        n := len(slice)
        randIndex := r.Intn(n)
        slice[n-1], slice[randIndex] = slice[randIndex], slice[n-1]
        slice = slice[:n-1]
    }
}

public class Quick3way {
    private Quick3way() { }

    public static void sort(Comparable[] a) {
        shuffle(a);
        sort(a, 0, a.length - 1);
    }

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

        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }

    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static void shuffle(Object[] a) {
        validateNotNull(a);
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int r = i + uniform(n-i);     // between i and n-1
            Object temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    private static void validateNotNull(Object x) {
        if (x == null) {
            throw new IllegalArgumentException("argument must not be null");
        }
    }

    private static int uniform(int n) {
        if (n <= 0) throw new IllegalArgumentException("argument must be positive: " + n);
        return random.nextInt(n);
    }
}

func Quick3WaySort(A []int) {
    shuffle(A)
    quick3WaySort(A, 0, len(A))
}

func quick3WaySort(A []int, lo, hi int) {
    if hi-lo < 2 {
        return
    }
    lt := lo
    gt := hi - 1
    i := lo
    pivot := A[lo]
    for i <= gt {
        if A[i] < pivot {
            A[lt], A[i] = A[i], A[lt]
            lt++
            i++
        } else if A[i] > pivot {
            A[i], A[gt] = A[gt], A[i]
            gt--
        } else {
            i++
        }
    }
    quick3WaySort(A, lo, lt)
    quick3WaySort(A, gt+1, hi)
}

func shuffle(slice []int) {
    r := rand.New(rand.NewSource(time.Now().Unix()))
    for len(slice) > 0 {
        n := len(slice)
        randIndex := r.Intn(n)
        slice[n-1], slice[randIndex] = slice[randIndex], slice[n-1]
        slice = slice[:n-1]
    }
}