插入排序原理图
https://www.runoob.com/w3cnote/insertion-sort.html
java实现代码
/** * 插入排序 */ public class InsertionSortTest { public static void main(String[] args) { int[] arr = {2,4,7,5,3,6,8,9,1}; insertionSort(arr); } /** * 插入排序的原理: * 将待排序数组看成两部分: 有序数组和无序数组,初始时,第一次可以将第一张看成有序数组,其余作为无序数组 * 无序数组插入到有序数组中,遍历无序数组(无序数组个数就是需要插入的次数) * 将有序数组的右侧第一张和 无序的第一张, * 如果 从有序的右侧起: 获取无序的元素小于于有序的元素的第一个元素的索引,有序的这些元素向右移动一位 * 同时当前的索引值+1的位置就是 插入的元素 */ public static void insertionSort(int[] arr){ //外层为 要插入的元素 for (int i=1;i<arr.length;i++){ //有序位置的最后一个元素 int tmp = arr[i]; //获取要插入的元素的位置 int j = i - 1; //从右侧起,获取第一个比要插入的元素小的元素的索引,索引右侧的值 右移一位 while (j>=0 && arr[j] > tmp){ arr[j+1] = arr[j]; //arr[j] = tmp; j--; } arr[j+1] = tmp; System.out.println(Arrays.toString(arr)); } } }
运行结果:
复杂度
完