## 插入排序 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; } } ~~~