排序算法可以说是算法的基本功，今天看下常见的五种排序算法的java实现代码

排序算法模板

public class Example {
    public static void sort(int[] a) {
        /* 请见算法2.1、算法2.2、算法2.3、算法2.4、算法2.5、算法2.6或算法2.7*/
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

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

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将它们排序并输出
        int[] a = {5, 6, 9, 1, 2, 3};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

1. 选择排序

/**
 * 时间复杂度: O(n^2)
 * 空间复杂度: O(n^2)
 * 稳定性: 不稳定
 * 复杂性: 简单
 *
 * @Description: 选择排序
 * @author: Gao Hang Hang
 * @date 2019/01/18 19:38
 */
public class Selection {
    public static void sort(int[] a) {
        // 将a[]按升序排列
        int N = a.length;           // 数组长度
        for (int i = 0; i < N; i++) {
            // 将a[i]和a[i+1..N]中最小的元素交换
            int min = i;
            for (int j = i + 1; j < N; j++)
                if (less(a[j], a[min])) min = j;
            exch(a, i, min);
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

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

    private static void show(int[] a) {
        // 在单行打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] nums = {6, 3, 5, 9, 1, 2};
        sort(nums);
        show(nums);
        System.out.println(isSorted(nums));
    }
}

2. 插入排序

/**
 * 时间复杂度: O(n^2)
 * 空间复杂度: O(n^2)
 * 稳定性: 稳定
 * 复杂性: 简单
 *
 * @Description: a2_插入排序
 * @author: Gao Hang Hang
 * @date 2019/01/02 12:04
 */
public class InsertSort {
    public static void sort(int[] a) {
        // 将a[]按升序排列
        int N = a.length;
        for (int i = 0; i < N; i++) {
            // 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

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

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

3. 希尔排序

/**
 * 时间复杂度: O(n^1.3)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 * 复杂性: 较复杂
 *
 * 思想: 先部分排序，再插入排序
 *
 * @Description: 希尔排序
 * @author: Gao Hang Hang
 * @date 2019/01/18 21:44
 */
public class Shell {
    public static void sort(int[] a) {
        // 将a[]按升序排列
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
        while (h >= 1) {
            // 将数组变为h有序
            for (int i = h; i < N; i++) {
                // 将a[i] 插入到a[i-h], a[i-2*h], a[i-3*h]... 之中
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

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

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3, 19};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

4. 归并排序

/**
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(n)
 * 稳定性: 稳定
 * 复杂性: 较复杂
 *
 * @Description:
 * @author: Gao Hang Hang
 * @date 2019/01/19 22:15
 */
public class Merge {

    private static int[] aux;      // 归并所需的辅助数组

    public static void sort(int[] a) {
        aux = new int[a.length];   // 一次性分配空间
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi) {
        // 将数组a[lo..hi]排序
        if (hi <= lo) return;       // 边界条件
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);            // 将左半边排序
        sort(a, mid + 1, hi);    // 将右半边排序
        merge(a, lo, mid, hi);       // 归并结果
    }

    public static void merge(int[] a, int lo, int mid, int hi) {
        // 将a[lo..mid] 和 a[mid+1..hi] 归并
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) { // 归并回到a[lo..hi]
            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 boolean less(int v, int w) {
        return v < w;
    }

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

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3, 19};
        sort(a);
        show(a);
    }
}

5. 快速排序

/**
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(logn)
 * 稳定性: 不稳定
 * 复杂性: 较复杂
 *
 * @Description: 快速排序
 * @author: Gao Hang Hang
 * @date 2019/01/19 22:43
 */
public class Quick {
    public static void sort(int[] a) {
        sort(a, 0, a.length -1);
    }

    private static void sort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = prrtion(a, lo, hi);   // 切分
        sort(a, lo, j -1);        // 将左半边部分a[lo .. j-1]排序
        sort(a, j+1, hi);         // 将右半部分a[j+1 .. hi]排序
    }

    private static int prrtion(int[] a, int lo, int hi) {
        // 将数组切分为a[lo..i-1], a[i], a[i+1..hi]
        int i = lo, j = hi + 1; // 左右扫描指针
        int 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);         // 将v = a[j]放入正确的位置
        return j;               // a[lo..j-1] <= a[j] <= a[j+1..hi] 达成
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

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

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

参考书籍：《算法》第四版