## 插入排序 InsertXSort * 空间复杂度：O(1) * 时间复杂度：O(n2) ## 思路描述 (把数组分为左和右，左边的默认有顺序，右边的数逐个插入到左边合适的位置） 1. 先找到最小的数做哨兵，放到最左边 2. 从第3个数开始，发现左边的数大于右边的，就右移动，最后把原来的数赋值给适合的下标 ## 例子 ``` old:[13, 7, 4, 6, 9, 24, 12] 1)[4, 13, 7, 6, 9, 12, 24] 2)[4, 7, 13, 6, 9, 12, 24] 3)[4, 6, 7, 13, 9, 12, 24] 4)[4, 6, 7, 9, 13, 12, 24] 5)[4, 6, 7, 9, 12, 13, 24] 6)[4, 6, 7, 9, 12, 13, 24] result:[4, 6, 7, 9, 12, 13, 24] ``` ## Java实现 ~~~ public class InsertXSort { public static void main(String[] args) { int[] nums = {13,7,4,6,9,24,12}; System.out.println("old:"+Arrays.toString(nums)); System.out.println("result:"+Arrays.toString(sort(nums))); } // 插入排序 public static int[] sort(int[] nums){ int swap = 0; // 找到最小的数字做为哨兵 for(int i=nums.length-1;i>0;i--){ if(nums[i] < nums[i-1]){ swap(nums,i,i-1); swap ++; } } if(swap == 0) return nums; System.out.println("1)"+Arrays.toString(nums)); // 从第二位数字开始对比，如果后面数字比前面数字大，将大的数字统一往后面移动，最后将原来数组插入到对应下标 for(int i=2;i<nums.length;i++){ int j=i; int value = nums[i]; while(value < nums[j-1]){ nums[j] = nums[j-1]; j--; } nums[j] = value; System.out.println(i+")"+Arrays.toString(nums)); } return nums; } // 交换数组下标 public static void swap(int[] nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } ~~~