算法笔记－排序01:选择排序,插入排序,希尔排序

实现两种初级的排序算法：

选择排序思路

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

完整代码

public class Selection {

    public static void sort(Comparable[] a){
        for (int i = 0; i < a.length; i++){
            for (int j = i+1; j < a.length;j++){
                if (less(a[j], a[i])) exchange(a,i,j);
            }
        }
        show(a);
    }
    
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    
    private static void exchange(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++)
            System.out.print(a[i]);
        System.out.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;
    }    
}

分析

这种实现十分简单且容易理解的算法有两个特点：
1.运行时间和输入无关：即使输入了一个已经有序的数组，这个算法依然会从头到尾的比较一遍，也就是说，没有利用到数组的初始状态。
2.数据移动较小：最多只进行N次交换。

插入排序思路与分析

从序列的第二个元素开始，向前进行比较，如果第二个元素比第一个小，那么将它们对换，然后从第三个元素开始，如果第三个元素比第二个大，那么直接向后从第四个开始，如果第三个元素比第二个小，那么将它们对换，然后又比较第二个和第一个，完成后向后从第四个开始，在这种情况下，如果数组是部分有序的，这种算法就因为可以省略掉一些向前进行的比较从而加快速度。事实上，当序列中倒置的元素非常少时，这个算法可能比其他任何算法都快。

完整代码

public class Insertion {
    
    public static void sort(Comparable[] a){
        for (int i = 1; i < a.length; i++){
            for (int j = i; j > 0 && less(a[j], a[j-1]);j--) exchange(a,j,j-1);
        }
        show(a);
    }
    
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
     
    private static void exchange(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++)
            System.out.print(a[i]);
        System.out.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;
    }
}

比较两种初级的排序算法：

在实际应用中插入排序都比选择排序要快一些，往往是快一倍左右(使用尽量大的数据更容易得到这个结果，比如大小为一万的数组重复一千次)。

测试代码

1.用于计时的类

public class StopWatch {
    private final long start;
    
    public StopWatch(){
        start = System.currentTimeMillis();
    }
    
    public double elapsedTime(){
        long now = System.currentTimeMillis();
        return (now-start)/1000.0;
    }
}

用于比较两种排序算法运行时间的测试代码

public class Main {
    
    public static void main(String[] args) {
        String alg1 = args[0];
        String alg2 = args[1];
        int N = Integer.parseInt(args[2]);
        int T = Integer.parseInt(args[3]);
        double t1 = timeRandomInput(alg1,N,T);
        double t2 = timeRandomInput(alg2,N,T);
        System.out.println(alg1 + " : " + t1);
        System.out.println(alg2 + " : " + t2);
    }
    
    public static double timeRandomInput(String alg, int N, int T){
        double total = 0.0;
        Double[] a = new Double[N];
        for (int t = 0; t < T; t++){
            for (int i = 0; i < N; i++) a[i] = Math.random();
            total += time(alg,a);
        }
        return total;
    }
    
    public static double time(String alg, Double[] a){
        StopWatch timer = new StopWatch();
        if (alg.equals("Insertion")) Insertion.sort(a);
        if (alg.equals("Selection")) Selection.sort(a);
        if (alg.equals("Shell"))Shell.sort(a); 
        return timer.elapsedTime();
        
    }
}

运行命令

% javac Insertion.java Main.java Selection.java StopWatch.java
% java Main Insertion Selection 10000 1000

代码比较简单，执行用例所需的参数为两种算法的名称，数组大小，循环次数（循环进行用户指定大小的随机数组的生成及排序），输出结果是两种算法各自运行的时间。在笔者的电脑上输出是这样的

输出结果

这验证了插入排序往往比选择排序快一倍的说法。然而，这两种算法对于大规模的乱序数组都是非常慢的（等上面的输出等了老半天，不过满屏的数字很有黑客帝国的感觉）。

一种改进：希尔排序

希尔排序是对插入排序的一个改进，我认为对于这种算法比较好的一种理解方式就是假装自己是一台计算机，然后假装收到了一条需要为一个容量为10的乱序数组排序的命令，再按照下面的代码在草稿纸上一步一步地去运行，自然就明白了，参见维基百科 。
代码中除了sort方法于上面不同之外其他部分都一样：

public class Shell {
    public static void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3*h + 1;
        while (h >= 1){
            for (int i = h; i < N; i++){
                for (int j = i; j > h &&less(a[j], a[j-h]); j -= h)exchange(a,j,j-h);
            }
            h/=3;
        }
    }
    
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
     
    private static void exchange(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++)
            System.out.print(a[i]);
        System.out.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;
    }
}

测试一下改进后算法的速度：

运行命令

% javac Shell.java
% java Main Insertion Shell 10000 1000 

运行结果

希尔排序比插入排序快的不是一点点。

问：我去，这是为什么？为什么多跳了几遍会比直接排快？为什么一个小小的改变会带来这么大的差距？
答：不知道。

算法一书原文：“The study of the performance characteristics of shellsort requires mathematical arguments that are beyond the scope of this book.”（这题超纲了）

维基百科：“希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）”。

对于中等大小的问题，希尔排序的运行时间是可以接受的,他的代码量很小而且不需要额外的存储空间，砖家推荐一般先用希尔排序实现，在发现性能不行的时候再考虑改进。对于大型问题，就需要接下来的算法了。

资源以及参考

普林斯顿大学算法课程以其教材《算法》第四版
维基百科