## 插入排序 InsertSort * 空間復雜度：O(1) * 時間復雜度：O(n2) ## 思路描述 (把數組分為左和右，左邊的默認有順序，右邊的數逐個插入到左邊合適的位置）  ## 例子 ``` old:[13, 7, 4, 6, 9, 24, 12] 1)[7, 13, 4, 6, 9, 24, 12] 2)[7, 4, 13, 6, 9, 24, 12] 2)[4, 7, 13, 6, 9, 24, 12] 3)[4, 7, 6, 13, 9, 24, 12] 3)[4, 6, 7, 13, 9, 24, 12] 4)[4, 6, 7, 9, 13, 24, 12] 6)[4, 6, 7, 9, 13, 12, 24] 6)[4, 6, 7, 9, 12, 13, 24] result:[4, 6, 7, 9, 12, 13, 24] ``` ## Java實現 ~~~ public class InsertSort { 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){ for(int i=0;i<nums.length;i++){ for(int j=i;j>0;j--){ if(nums[j] < nums[j-1]){ swap(nums,j,j-1); System.out.println(i+")"+Arrays.toString(nums)); }else{ break; } } } return nums; } // 交換數組下標 public static void swap(int[] nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } ~~~