面试基础-插入排序
第二个排序算法,插入排序的思想是遍历数组中的每一个元素,插入到已经有序的数组中,插入的过程仍需保持数组的有序性。实际写代码时,插入的过程类似于冒泡的过程,从后往前遍历,找到合适的位置插入。插入排序是一次只关心一个元素,直接找到最终位置,冒泡排序是一次比较若干元素,找到一个最大元素放到最终位置。 测试输入: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 图片仍来自百度,图片能大致反应排序的思想,但仍不能完全的反应内存真实的动作,所以想自己写一个动画,来反应排序过程中数据在内存中的动画效果,包括比较过程,包括交换过程。...