那些常见的排序算法你真的能写出来吗？-一一网

排序

排序算法的额外内存开销和运行时间是同等重要的。排序算法可以分为两类：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一份数组副本的其他排序算法。

在创建自己的数据类型时，我们只要实现 Comparable 接口就能够保证用例代码可以将其排序。要做到这一点，只需要实现一个 compareTo() 方法来定义目标类型对象的自然次序。

对于 v<w、v=w 和 v>w 三种情况， Java 的习惯是在 v.compareTo(w) 被调用时分别返回一个负整数、零和一个正整数（一般是 -1、0 和 1）。如果 v 和 w 无法比较或者两者之一是 null，v.compareTo(w) 将会抛出一个异常。此外，compareTo() 必须实现一个完整的比较序列，即：

自反性，对于所有的 v，v=v；
反对称性，对于所有的 v<w 都

有 v>w，且 v=w 时 w=v；
传递性，对于所有的 v、w 和 x，

如果 v<=w 且 w<=x，则 v<=x。

public class Date implements Comparable<Date> {
 private final int day;
 private final int month;
 private final int year;
 public Date(int d, int m, int y) { 
     day = d; 
     month = m; 
     year = y; 
 }
 public int day() { 
     return day; 
 }
 public int month() {
     return month; 
 }
 public int year() {
     return year; 
 }
 public int compareTo(Date that) {
 	if (this.year > that.year ) return +1;
 	if (this.year < that.year ) return -1;
 	if (this.month > that.month) return +1;
 	if (this.month < that.month) return -1;
 	if (this.day > that.day ) return +1;
 	if (this.day < that.day ) return -1;
	return 0;
 }
 public String toString() { 
     return month + "/" + day + "/" + year; }
}
复制代码

排序算法里的模板

public class Example { 
    public static void sort(Comparable[] a) { 
        /* 请见算法2.1、算法2.2、算法2.3、算法2.4、算法2.5或算法2.7*/ 
    } 
    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 = 1; i < a.length; i++) 
            if (less(a[i], a[i-1])) 
                return false;
        return true; 
    }
    public static void main(String[] args){ // 从标准输入读取字符串，将它们排序并输出 
        String[] a = In.readStrings(); 
        sort(a); 
        assert isSorted(a); 
        show(a); 
    } 
}
复制代码

选择排序

一种最简单的排序算法是这样的：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换的总次数是 N。所以算法的时间效率取决于比较的次数。

总的来说，选择排序是一种很容易理解和实现的简单排序算法，它有两个很鲜明的特点。

运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点，因为使用选择排序，一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长！其他算法会更善于利用输入的初始状态。
数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。我们将研究的其他任何算法都不具备这个特征（大部分的增长数量级都是线性对数或是平方级别）。

public class Selection { 
    public static void sort(Comparable[] 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); 
        } 
    }// less()、exch()、isSorted()和main()方法见“排序算法类模板”
复制代码

该算法将第 i 小的元素放到 a[i] 之中。数组的第 i 个位置的左边是 i 个最小的元素且它们不会再被访问。

插入排序

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

public class Insertion { 
    public static void sort(Comparable[] a) { 
        // 将a[]按升序排列 
        int N = a.length; 
        for (int i = 1; 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); 
        } 
    }// less()、exch()、isSorted()和main()方法见“排序算法类模板” 
}
复制代码

对于 0 到 N-1 之间的每一个 i，将 a[i] 与 a[0] 到 a[i-1] 中比它小的所有元素依次有序地交换。在索引 i 由左向右变化的过程中，它左侧的元素总是有序的，所以当 i 到达数组的右端时排序就完成了。

插入排序对这样的数组很有效，而选择排序则不然：

数组中每个元素距离它的最终位置都不远
一个有序的大数组接一个小数组
数组中只有几个元素的位置不正确

也就是插入排序更适合部分有序的数组。当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快。

总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。

希尔排序

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要 N-1 次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。换句话说，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组。在进行排序时，如果 h 很大，我们就能将元素移动到很远的地方，为实现更小的 h 有序创造方便。用这种方式，对于任意以 1 结尾的 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 = 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; 
    } 
}// less()、exch()、isSorted()和main()方法见“排序算法类模板” }
复制代码

和选择排序以及插入排序形成对比的是，希尔排序也可以用于大型数组。它对任意排序（不一定是随机的）的数组表现也很好。

归并排序

将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。这种递归排序算法：归并排序。

归并排序最吸引人的性质是它能够保证将任意长度为7V的数组排序所需时间和TVlogTV成正比；它的主要缺点则是它所需的额外空间和W成正比。

public static void merge(Comparable[] a, int lo, int mid, int hi){ 
    // 将a[lo..mid ]和a[mid + l..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++)
        if (i > mid)
            a[k] = aux[j++];// 归并回到a[lo..hi]
        else if (j > hi) 
            a[k] = aux[i++];
        else if (less(aux[j] , aux[i])) 
            a[k] = aux[j++];
        else 
            a[k] = aux[i++];
}
复制代码

该方法先将所有元素复制到a u x []中，然后再归并回a [ ] 中。方法在归并时（第二个for 循环）进行了4 个条件判断：左半边用尽（取右半边的元素）、右半边用尽（取左半边的元素）、右半边的当前元素小于左半边的当前元素（取右半边的元素）以及右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。

自顶向下的归并排序

public class Merge {
    private static Comparable[] aux; // 归并所需的辅助数组
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length]; // 一次性分配空间
        sort(a,0,a.length - 1);
    }
	private static void sort(Comparable[] a ，in t lo, in t 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); // 归并结果
    }
}
复制代码

可以用归并排序处理数百万甚至更大规模的数组，这是插入排序或者选择排序做不到的。归并排序的主要缺点是辅助数组所使用的额外空间和N的大小成正比。

自底向上的归并排序

实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并得到的子数组，如此这般，直到我们将整个数组归并在一起。

public class MergeBU {
	private static Comparable[] aux;  //归并所需的辅助数组
    //merge()方法的代码请见“原地归并的抽象方法”
	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)); 
    }
}
复制代码