public class Insertion {
public static void sort(Comparable[] a){//所有实现了Comparable接口的数组都可以使用插入排序
int N = a.length;//数组的长度,便于遍历使用
for(int i = 1; i<N;i++){//因为插入排序的思想是当前角标和前一个角标作比较,所以,外循环i的初始值为1,那么内循环中就可以和1角标前面的0角标比较了
//内循环中,j=i,出口判断条件为j>0,则j最小满足条件为1,那么他还可以与j-1=0角标作对比,
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);//调用自定义的交换方法
}
}
}
}
private static void exch(Comparable[] a, int j, int i) {//调用自定义的交换方法
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);
}
}
}
插入排序比选择排序要快一点,插入排序只与左边作比较,而选择排序则只与右边作比较
算法学习来自<算法第四版>书籍
