public class Insertion {
public static void sort(Comparable[] a){//所有實(shí)現(xiàn)了Comparable接口的數(shù)組都可以使用插入排序
int N = a.length;//數(shù)組的長(zhǎng)度,便于遍歷使用
for(int i = 1; i<N;i++){//因?yàn)椴迦肱判虻乃枷胧钱?dāng)前角標(biāo)和前一個(gè)角標(biāo)作比較,所以,外循環(huán)i的初始值為1,那么內(nèi)循環(huán)中就可以和1角標(biāo)前面的0角標(biāo)比較了
//內(nèi)循環(huán)中,j=i,出口判斷條件為j>0,則j最小滿足條件為1,那么他還可以與j-1=0角標(biāo)作對(duì)比,
for(int j = i;j>0;j--){
if(less(a[j],a[j-1])){//如果a[j]小于a[j--],那么就交換j和j--值的位置
exch(a,j,j-1);//調(diào)用自定義的交換方法
}
}
}
}
private static void exch(Comparable[] a, int j, int i) {//調(diào)用自定義的交換方法
Comparable temp = a[j];
a[j] = a[i];
a[i] = temp;
}
private static boolean less(Comparable v, Comparable w) {//v小于w的話返回真
return v.compareTo(w) <0;
}
public static void main(String[] args) {
Integer[] a = new Integer[]{888,494,110,12,154,123,456,356,486,576,16,654,23,451,};
sort(a);
for(int num : a){
System.out.print(" "+num);
}
}
}
插入排序比選擇排序要快一點(diǎn),插入排序只與左邊作比較,而選擇排序則只與右邊作比較
算法學(xué)習(xí)來(lái)自<算法第四版>書籍
