思路

  1. 反序
  2. 如果相鄰兩個數字大小相反,就交換位置
  3. 最小在右邊,最大在左邊

實作

測試方法

public static void main(String[] args) {
    int[] nums = new int[]{8, 2, 6, 10, 4};
    Sort_Insertion3.insertion_sort(nums);

    System.out.println();
}

具體

public static void insertion_sort(int[] nums) {
    // 從 0 開始跑
    for (int i_start = 0; i_start < nums.length; i_start++) {
        // 與開始的前一位做比較,一直往前比較
        //0=8,1=2,3=6,4=10,5=4
        //i_start=0,j_run=-1 x
        //i_start=1,j_run=0 in, nums[1]=2, nums[0]=8 break;
        //i_start=2,j_run=1 in, nums[2]=6, nums[1]=2 swap; [8,6,2,10,4]
        //i_start=2,j_run=0 in, nums[1]=6, nums[0]=8 break;
        //i_start=3,j_run=2 in, nums[3]=10, nums[2]=2 swap; [8,6,10,2,4]
        //i_start=3,j_run=1 in, nums[2]=10, nums[1]=6 swap; [8,10,6,2,4]
        //i_start=3,j_run=0 in, nums[1]=10, nums[0]=8 swap; [10,8,6,2,4]
        //i_start=4,j_run=3 in, nums[4]=4, nums[3]=2 swap; [10,8,6,4,2]
        //i_start=4,j_run=2 in, nums[3]=4, nums[2]=6 break;
        for (int j_run = i_start - 1; j_run >= 0; j_run--) {
            // 後面的數字大於前面的數字,就交換位置
            if (nums[j_run + 1] > nums[j_run]) {
                swap(nums,j_run + 1, j_run);
            } else { // 否則跳出迴圈
                break;
            }
        }
    }
}

private static void swap(int[] nums, int i_left, int i_right) {
    int tmp = nums[i_left]; // set temp variable
    nums[i_left] = nums[i_right]; // 把 right 放到 left
    nums[i_right] = tmp; // 把 left 放到 right
}

實作 by recursion

測試方法

public static void main(String[] args) {
    nums = new int[]{8, 2, 6, 10, 4};
    Sort_Insertion3.insertion_sort_recursion(nums);

    System.out.println();
}

具體

public static void insertion_sort_recursion(int[] nums) {
    int i_start = 0;
    insertion_sort_recursion_help01(nums, i_start);
}

private static void insertion_sort_recursion_help01(int[] nums, int i_start) {
    /** end condition **/
    if (i_start >= nums.length) {
        return;
    }

    /** main logic **/
    int j_run = i_start - 1;
    insertion_sort_recursion_help02(nums, j_run);

    /** data flow **/
    insertion_sort_recursion_help01(nums, i_start + 1);

}

private static void insertion_sort_recursion_help02(int[] nums, int j_run) {
    /** end condition **/
    if (j_run < 0) {
        return;
    }

    /** main logic **/
    if (nums[j_run + 1] > nums[j_run]) { // 右邊>左邊,就交換位置
        swap(nums,j_run + 1, j_run);
    }else {
        return;
    }

    /** data flow **/
    insertion_sort_recursion_help02(nums, j_run - 1);
}

private static void swap(int[] nums, int i_left, int i_right) {
    int tmp = nums[i_left]; // set temp variable
    nums[i_left] = nums[i_right]; // 把 right 放到 left
    nums[i_right] = tmp; // 把 left 放到 right
}