1. 初级排序算法
2. 选择排序
3. 插入排序
4. 希尔排序

初级排序算法

public abstract class SortTemplate {

    //抽象的排序方法
    public abstract void sort(Comparable[] comparables);


    //比较两个元素大小
    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;
    }

    //打印元素
    public static void show(Comparable[] comparables) {
        for (Comparable comparable : comparables) {
            StdOut.print(comparable + " ");
        }
        StdOut.println();
    }

    //检测是否有序
    public static boolean isSorted(Comparable[] comparables) {
        for (int i = 1; i < comparables.length; i++) {
            if (less(comparables[i], comparables[i - 1])) {
                return false;
            }
        }
        return true;
    }
}

1. 数组的初始状态有的时候未必能够成功执行算法, 比如全部都是一个值的数组
2. 是否使用额外的内容, 排序算法其实有两类, 一类在运行的时候除了栈和固定数目的实例变量之外无需额外内存的原地排序算法, 还有需要动态申请内存空间来存储另外一个数组副本的其他排序算法.
3. 如果要自己创建数据类型而不是使用Java内置的已经实现了Comparable接口的数据类型, 则需要自己实现Comparable接口中的compareTo方法, 这个方法小于0表示调用方法的对象小于参数.

选择排序

1. 首先, 找到最小的元素, 将其和数组的第一个元素进行交换
2. 然后对从第二个开始的剩余数组, 重复这个过程. 直到到达最后一个元素.

public static void sort(Comparable[] comparables) {
    int length = comparables.length;
    int i = 0;
    Comparable min;
    int min_index = 0;

    while (i < length) {
        //找到最小值和对应的索引, 这个循环执行完之后, min为最小值, min_index是索引
        min = comparables[i];
        min_index = i;
        for (int j = i + 1; j < length; j++) {

            if (less(comparables[j], min)) {
                min = comparables[j];
                min_index = j;
            }
        }
        //交换第一个元素和最小元素的索引
        exch(comparables, i, min_index);
        i++;
    }
}

插入排序

public static void sort(Comparable[] comparables) {
    int N = comparables.length;
    //从数组的第二个位置开始遍历
    for (int i = 1; i < N; i++) {
        //然后使用一个循环从i当前位置反向遍历, 如果当前位置比上一个位置小, 就交换二者, 然后继续比较, 直到将小数字交换到正确位置
        for (int j = i; j > 0 && less(comparables[j], comparables[j - 1]);j--) {
            exch(comparables, j, j - 1);
        }
    }
}

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

public class Test {

    public static double time(String alg, Comparable[] comparables) {
        Stopwatch timer = new Stopwatch();
        if(alg.equals("Insertion")) Insertion.sort(comparables);
        else if(alg.equals("Selection")) Selection.sort(comparables);
        else{
            StdOut.println("未执行排序");
        }
        return timer.elapsedTime();
    }

    public static double timeRandomInputs(String alg, int N, int T) {
        double total = 0.0;
        Double[] a = new Double[N];

        //进行T次, 数组长度为N的排序, 将每次排序的时间累加到total上
        for (int t = 0; t < T; t++) {
            for (int i = 0; i < N; i++) {
                a[i] = StdRandom.uniform();
            }
            total += time(alg, a);
        }
        return total;
    }

    public static void main(String[] args) {
        StdOut.print("Input two INT, first is length, second is times: ");
        String a1 = StdIn.readLine();
        String[] a = a1.split("\\s+");
        StdOut.println(Arrays.toString(a));
        int N = Integer.parseInt(a[0]);
        int T = Integer.parseInt(a[1]);

        double Inserton_time = timeRandomInputs("Insertion", N, T);
        double Selection_time = timeRandomInputs("Selection", N, T);

        StdOut.printf("Insertion_time is %f, Selection_time is %f, rate is %f", Inserton_time, Selection_time, Inserton_time / Selection_time);
    }
}

希尔排序

public static void sort(Comparable[] a) {
    int N = a.length;

    //h是组数
    int h = 1;
    //这个实际上是如何分配组数来的, 循环执行完之后, 会得到不超过N的最大分组数量
    while (h < N / 3) {
        h = 3 * h + 1;
    }

    //这个循环就是不断缩小组数也就是h的数, 最后h=1的时候就是对整个数组排序, 之后控制h /= 3, 就会结束循环
    while (h >= 1) {
        //从分组的地方开始, 而不是从头开始
        for (int i = h; i < N; i++) {
            //以h为间隔, 从索引h开始到最后一个元素, 不断的反向判断和交换间隔为h的元素
            for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                exch(a, j, j - h);
            }
        }
        h = h / 3;
    }
}

For 200 times of length=4000 array, result is:
Insertion: 4.304000, Selection: 2.760000, Shell: 0.170000