博客

插入排序类似于我们平时打牌，我们首先拿起来第一张牌，之后拿起第二张牌并跟第一张牌比较，如果大于第一张牌，就放在第二，否则放在第一，之后依次找到他们的位置。

假设现在有一个数组A,我们首先取出来第一个元素作为我们手里的第一张牌B{a},此时我们手里的牌是已经经排好序的，此时拿出来数组A中的第二个元素，放到子数组B{a},并跟A做比较排序，此时，子数组B依然是排好序的，依次类推B{a…r}子数组不论在任何时候都是一个排好序的数组，并且每次都是增加的。

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {10, 6, 4, 5, 8, 9, 7, 2, 3, 1};
        sortAsc(a);
    }

    static void sortDesc(int[] a) {
        for (int j = 1; j < a.length; j++) {
            int key = a[j];
            int i = j - 1;
            while (i >= 0 && a[i] > key) {
                a[i + 1] = a[i];
                i = i - 1;
            }
            a[i + 1] = key;
        }

        for (int i : a) {
            System.out.println(i);

        }
    }

    static void sortAsc(int[] arr) {
        for (int j = 2; j < arr.length; j++) {
            int key = arr[j];
            int i = j - 1;
            while (i >= 0 && arr[i] < key) {
                arr[i + 1] = arr[i];
                --i;
            }
            arr[i + 1] = key;
        }

        for (int i : arr) {
            System.out.println(i);
        }
    }
}