java算法：插入排序

如，对EXAMPLE 字母进行排序：

 E   X   A   M   P   L   E   开始

 E  [X]  A   M   P   L   E   E<X 不变

[A]  E   X   M   P   L   E   A < E：A插入到E前

 A   E  [M]  X   P   L   E   ...

 A   E   M  [P]  X   L   E  

 A   E  [L]  M   P   X   E  

 A   E  [E]  L   M   P   X 

public class Insertion {

    public static void main(String[] args) {
        int n = 20;
        MyItem [] a = new MyItem[n];
        for (int i = 0; i < n; i++) {
            a[i] = new MyItem();
            a[i].rand();
        }

        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }

        insertion(a, 0, n);
        System.out.println("");
        print(a, n);
    }

    private static void print(MyItem a [], int n){
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void insertion(MyItem [] a, int l, int r){
        int i;
        for(i = r - 1; i >= l + 1; i--){
            compExch(a, i-1, i);
        }
        for (i = l + 2; i < r; i++){
            int j = i;
            MyItem v = a[i];
            while(less(v, a[j - 1])){
                a[j] = a[j - 1];
                j--;
            }
            a[j] = v;
        }
    }

    public static boolean less(Item v, Item w){
        return v.less(w);
    }

    public static void exch(Item [] a, int i, int j){
        Item t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void compExch(Item [] a, int i, int j){
        if(less(a[j],a[i])){
            exch(a, i, j);
        }
    }
}

public class Insertion {	public static void main(String[] args) {		int n = 20;		MyItem [] a = new MyItem[n];		for (int i = 0; i < n; i++) {			a[i] = new MyItem();			a[i].rand();		}				for (int i = 0; i < n; i++) {			System.out.print(a[i] + " ");		}				insertion(a, 0, n);		System.out.println("");		print(a, n);	}		private static void print(MyItem a [], int n){		for (int i = 0; i < n; i++) {			System.out.print(a[i] + " ");		}	}		public static void insertion(MyItem [] a, int l, int r){		int i;		for(i = r - 1; i >= l + 1; i--){			compExch(a, i-1, i);		}		for (i = l + 2; i < r; i++){			int j = i;			MyItem v = a[i];			while(less(v, a[j - 1])){				a[j] = a[j - 1]; 				j--;			}			a[j] = v;		}	}		public static boolean less(Item v, Item w){		return v.less(w);	}		public static void exch(Item [] a, int i, int j){		Item t = a[i];		a[i] = a[j];		a[j] = t;	}		public static void compExch(Item [] a, int i, int j){		if(less(a[j],a[i])){			exch(a, i, j);		}	}}

插入排序的运行时间主要依赖于输入文件中关键字的最初顺序。如，文件很大而且关键字已经排好（或者几乎排好），那么插入排序运算就很快了，而选择排序运行却很慢。