排序算法的思想

选择排序

• 思路
  首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素是最小元素那么它就和自己交换位置）。再次，在剩下的元素中找到最小的元素，将它和数组的第二个元素交换位置。如此往复，知道将整个数组排序。

• 特点
  运行时间和输入无关、数据移动是最少的。

• 代码

public class Selection {
    public static void sort(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            int min = i; // 最小元素索引
            for (int j = 0; j < a.length; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            exch(a, i, min);
        }
    }
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }
    public static boolean isSorted(Comparable[] a) {
        // 测试数组元素是否有序
        for (int i = 0; i < a.length; i++) {
            if (less(a[i], a[i - 1])){
                return false;
            }
        }
        return true;
    }
}

插入排序

• 思路：见代码
• 特点
  插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快的多。
• 代码

public class Insertion {
    public static void sort(Comparable[] 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(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }
    public static boolean isSorted(Comparable[] a) {
        // 测试数组元素是否有序
        for (int i = 0; i < a.length; i++) {
            if (less(a[i], a[i - 1])){
                return false;
            }
        }
        return true;
    }
}

希尔排序

• 思路
  希尔排序的思想是使数组中间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。
• 特点
  希尔排序是基于快速排序的。希尔排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。希尔排序可以用于大型数组
• 代码

public class Shell {
    public static void sort(Comparable[] 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 = 0; 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(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }
    public static boolean isSorted(Comparable[] a) {
        // 测试数组元素是否有序
        for (int i = 0; i < a.length; i++) {
            if (less(a[i], a[i - 1])){
                return false;
            }
        }
        return true;
    }
}

归并排序

• 思路
  要将一个数组排序，可以(递归的）将他分成两半分别排序，然后将结果归并起来。
• 特点
  它能保证将任意长度为N的数组排序所需时间和NlogN成正比；主要缺点是它所需的额外空间和N成正比。
• 代码（自顶向下的归并排序）

public class Merge {
    private static Comparable[] aux; // 归并所需的辅助数组
    private static void sort(Comparable[] a){
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] 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(Comparable[] a, int lo, int mid, int hi){
        // 将a[lo..mid]和a[mid+1..hi]归并
        int i = lo, j = mid+1;
        for (int k = 0; k <= hi; k++) { // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        }

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

• 代码（自底向上的归并排序）

public class MergeBU {
    private static Comparable[] aux; // 归并所需的辅助数组
    public static void sort(Comparable[] a){
        // 进行lgN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz){ // sz子数组的大小
            for (int lo = 0; lo < N - sz; lo += sz + sz) { // lo:子数组索引
                merge(a, lo, lo+sz-1,Math.min(lo+sz+sz-1, N - 1));
            }
        }
    }
    public static void merge(Comparable[] a, int lo, int mid, int hi){
        // 将a[lo..mid]和a[mid+1..hi]归并
        int i = lo, j = mid+1;
        for (int k = 0; k <= hi; k++) { // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        }

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

快速排序

• 思想
  快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。使用此方法排序之前要先打乱打乱数组，以免切分元素过大或者过小。
  该方法的关键在于切分，这个过程使得数组满足下面三个条件：
  1.对于某个j，a[j]已经被排定
  2.a[lo]到a[j-1]中的所有元素都不大于a[j]
  3.a[j+1]到a[hi]中的所有元素都不小于a[j]
• 特点
  原地排序
• 代码

public class Quick {
    public static void sort(Comparable[] a){
        StdRandom.shuffle(a); // 消除对输入的依赖
        sort(a, 0, a.length - 1);
    }
    public static void sort(Comparable[] a, int lo, int hi){
        if (hi <= lo){
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1); // 将左半部分a[lo..j-1]排序
        sort(a, j + 1, hi); // 将右半部分a[j+1..hi]排序
    }
    private static int partition(Comparable[] a, int lo, int hi){
        // 将数组切分为a[lo..i-1]、a[i]、a[i+1..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;
            }
            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(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }