p157算法2.2插入排序

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);
    }

}

}
插入排序比选择排序要快一点,插入排序只与左边作比较,而选择排序则只与右边作比较
算法学习来自<算法第四版>书籍