代码实现：

package com.qiusongde;import edu.princeton.cs.algs4.In;import edu.princeton.cs.algs4.StdOut;public class InsertionWithSentinel {        public static void sort(Comparable[] a) {                int N = a.length;                for(int i = N - 1; i > 0; i--) {            if(less(a[i], a[i-1])) {                exch(a, i, i-1);//                show(a);            }        }                for(int i = 2; i < N; i++) {            for(int j = i; less(a[j], a[j-1]); j--) {                exch(a, j, j-1);            }//            show(a);        }            }        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) {                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();        show(a);        sort(a);        assert isSorted(a);        show(a);    }}

 

SortCompare：

package com.qiusongde;import edu.princeton.cs.algs4.Shell;import edu.princeton.cs.algs4.StdOut;import edu.princeton.cs.algs4.StdRandom;public class SortCompare {    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] = StdRandom.uniform();            total += time(alg, a);        }                return total;            }        public static double time(String alg, Double[] a) {                Stopwatch timer = new Stopwatch();                if(alg.equals("Selection"))            Selection.sort(a);        if(alg.equals("Insertion"))            Insertion.sort(a);        if(alg.equals("InsertionHalfExchange"))            InsertionHalfExchange.sort(a);        if(alg.equals("InsertionWithSentinel"))            InsertionWithSentinel.sort(a);        if(alg.equals("Shell"))            Shell.sort(a);                return timer.elapsedTime();            }        public static void main(String[] args) {                String alg1 = "Insertion";        String alg2 = "InsertionWithSentinel";        int N = 2000;        int T = 1000;                double t1 = timeRandomInput(alg1, N, T);        double t2 = timeRandomInput(alg2, N, T);                StdOut.printf("For %d random Doubles %d trials\n", N, T, alg1);        StdOut.printf("%s is %.1fs %s is %.1fs", alg1, t1, alg2, t2);            }}

 

 

测试结果：

For 2000 random Doubles 1000 trialsInsertion is 4.5s InsertionWithSentinel is 3.7s