面试基础-插入排序

第二个排序算法，插入排序的思想是遍历数组中的每一个元素，插入到已经有序的数组中，插入的过程仍需保持数组的有序性。实际写代码时，插入的过程类似于冒泡的过程，从后往前遍历，找到合适的位置插入。插入排序是一次只关心一个元素，直接找到最终位置，冒泡排序是一次比较若干元素，找到一个最大元素放到最终位置。

测试输入：new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5};

    /**
     * 从后往前遍历插入，这个插入过程有点像冒泡，只冒到合适的位置即可
     *
     * @param arr
     */
    public void sort(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                compareTimes++;
                if (arr[j] < arr[j - 1]) {
                    Util.swap(arr, j, j - 1);
                    swapTimes++;
                } else {
                    break;
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }

打印输出：数组长度:16 比较次数:61 交换次数:46

图片仍来自百度，图片能大致反应排序的思想，但仍不能完全的反应内存真实的动作，所以想自己写一个动画，来反应排序过程中数据在内存中的动画效果，包括比较过程，包括交换过程。努力ing