插入排序java实现

import java.util.Arrays;

public class Insert {
    public static void main(String args[]) {
        int array[] = {4, 3, 1, 2, 5};
        sort2(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 5 .4 3 2 1
     * 5 5 3 2 1
     * .4 5 3 2 1
     * <p>
     * 4 5 .3 2 1
     * 4 4 5 2 1
     * .3 4 5 2 1
     * <p>
     * 以上类推
     * <p>
     * 插入排序，类似于扑克中的抓牌，每次抓取牌的时候都与手中的牌进行比较，如果手中的牌都大于此牌，将这些牌都往右移，然后此牌插入。
     * 时间复杂度没有最坏的情况，比较稳定
     * 最坏情况：
     * 一层：n
     * 二层+三层：(1+...(n-2))
     * <p>
     * O(n+(n-1)*n/2)=n+n^2/2+1/2*n=3/2*n+n^2/2=O(n+n^2)
     *
     * @param array
     */
    public static void sort(int array[]) {
        int n = 0;
        for (int i = 1; i < array.length; i++) {
            int a = array[i];
            int n1 = 0;
            for (int j = 0; j < i; j++) {
                int b = array[j];
                int n2 = 0;
                if (a < b) {
                    for (int k = i; k > j; k--) {
                        array[k] = array[k - 1];
                        n++;
                        n2++;
                    }
                    array[j] = a;
                    break;
                }
                System.out.println("count2:" + n2);
                n++;
                n1++;
            }
            System.out.println("count1:" + n1);
            n++;
        }
        System.out.println("count:" + n);
    }

    /**
     * 3, 1, 4, 2, 5 k=0
     * 3, 3, 4, 2, 5 k=-1
     * 1, 3, 4, 2, 5 k=0
     *
     * 1, 3, .4, 2, 5 k=1
     * 1, 3, 4,  2, 5 k=2
     *
     * 少了一层循环，代码更简洁了，sort1方法的2层循环是从头比较，如果发现有比自己大的，就将大的之后的整体右移，然后替换当前。
     * 而此方法是：与元素前面的每一个比较，碰到比自己大的就把大的右移，没有比自己大的那就是我的位置。
     * 时间复杂度：
     * 最坏：跟sort1一样
     * 最好：(n-1)*2
     * @param array
     */
    public static void sort2(int array[]) {
        int n = 0;
        for (int i = 1; i < array.length; i++) {
            int a = array[i];
            int k = i - 1;
            //>=0是为了比较到第一个
            for (; k >= 0; k--) {
                //如果小于当前元素就向右移动
                if (a < array[k]) {
                    array[k + 1] = array[k];
                } else {
                    //如果大于或等于，
                    break;
                }
            }
            array[k + 1] = a;
            n++;
        }
        System.out.println("count:" + n);
    }
}