1. 基本规则

1. 排序类算法模板

public class Example
{
    public static void sort(Comparable[] a)
    {
        /* See Algorithms 2.1, 2.2, 2.3, 2.4, 2.5, or 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)
    { // Print the array, on a single
        // line.
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a)
    { // Test whether the array
        // entries are in order.
        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)
    { // Read strings from standard
        // input, sort them, and print.
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

2. Comparable接口
   实现了Comparable接口的数据类型：Integer、String、Double都实现了Comparable接口。创建自己的数据类型时，我们也要实现Comparable接口就能使用该模板进行排序。必须要实现Comparable接口中的compareTo方法。

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;
    }
}

compareTo必须实现一个全序关系：
①自反性：对所有的v=v
②反对称性：对所有v<w都有v>w，且v=w时w=v
③传递性

3. 排序成本模型：比较次数和访问数组的次数
4. 额外的内存使用

2. 选择排序

1. 思想：
   首先，找到数组中最小的元素，其次将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素和数组的第二个元素交换位置。如此往复，直到将整个数组排序。不断选择剩余元素中的最小者。

public class Selection
{
    public static void sort(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;
            exch(a,i,min);
        }
    }
}

2. Example
   

   选择排序

3. 分析：
   ①运行时间和输入无关
   ②数据移动是最少的
   ③长度为N的数组需要交换N次，比较次数：(N-1)+(N-2)+...1=N(N-1)/2~

3. 插入排序

1. 思想：
   想象打扑克牌，一张一张地把牌插入到适当地位置。在计算机的视线中，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向后移动一位。插入排序所需要的时间取决于输入元素中的初始顺序。

public class Insertion
{
    public static void sort(Comparable[] a)
    {
        int N=a.length;
        for(int i=1;i<N;i++)
        {   //a[i]插入到a[i-1] a[i-2]...1中
            for(int j=i;j>=0&&less(a[j],a[j-1]);j--)
            {
                exch(a,j,j-1);
            }
        }
    }
}

2. Example
   插入排序
3. 分析：
   ①best：输入顺序增大，无需移动元素，只需要N-1次比较。
   ②worst：输入是逆序的：N²/2次比较和交换
   ③平均：N²/4次比较和交换

4. 希尔排序

1. 思想：
   基于插入排序的快速排序算法。对于大规模乱序的数组插入排序很慢，是因为它只会交换相邻的元素，因此元素只能一点一点移动。希尔排序改进了插入排序算法，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。 关键：使数组中任意间隔为h的元素都是有序的

public static void sort(Comparable[] a) {
        int n = a.length;
        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
        int h = 1;
        while (h < n/3) h = 3*h + 1; 
        while (h >= 1) {
            // h-sort the array
            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);
                }
            }
            assert isHsorted(a, h); 
            h /= 3;
        }
        assert isSorted(a);
}

2. Example
   希尔排序
3. 分析：
   希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度与增量序列的选取有关，希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O( n^2 )复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。