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
Java代码
- publicclassInsertion{ publicstaticvoidmain(String[]args){ intn=20; MyItem[]a=newMyItem[n]; for(inti=0;i<n;i++){ a[i]=newMyItem(); a[i].rand(); } for(inti=0;i<n;i++){ System.out.print(a[i]+""); } insertion(a,0,n); System.out.println(""); print(a,n); } privatestaticvoidprint(MyItema[],intn){ for(inti=0;i<n;i++){ System.out.print(a[i]+""); } } publicstaticvoidinsertion(MyItem[]a,intl,intr){ inti; for(i=r-1;i>=l+1;i–){ compExch(a,i-1,i); } for(i=l+2;i<r;i++){ intj=i; MyItemv=a[i]; while(less(v,a[j-1])){ a[j]=a[j-1]; j–; } a[j]=v; } } publicstaticbooleanless(Itemv,Itemw){ returnv.less(w); } publicstaticvoidexch(Item[]a,inti,intj){ Itemt=a[i]; a[i]=a[j]; a[j]=t; } publicstaticvoidcompExch(Item[]a,inti,intj){ 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);}}}
插入排序的运行时间主要依赖于输入文件中关键字的最初顺序。如，文件很大而且关键字已经排好（或者几乎排好），那么插入排序运算就很快了，而选择排序运行却很慢。
青春一经典当即永不再赎
