最后有改進版

算法思路

• 將一個要排序的序列分為"已排序"，"未排序"兩部分
• 把未排序的序列的元素依次取出，插入已排序序列中

算法實現(xiàn)

完整代碼

建議復(fù)制完整代碼然后對照著后面的具體步驟

import java.util.Arrays;

public class InsertSortDemo {
    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private static void insertSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 3, 6, 7, 9, 8, 1, 4, 5, 1, 7, 9, 6, 5, 8};
        System.out.println(Arrays.toString(nums));
        insertSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

核心思想

• 每次從"未排序"序列中取出元素(實際上兩個序列都在數(shù)組中，這里說的取出只是方便理解)，插入"已排序"序列時，假如是升序排序，如果從"已排序"序列末端往前端逐個掃描，只要取出的元素比被掃描到的元素小，就交換位置，直到取出元素比掃描到的元素大，則停下(因為這是個"已排序"的序列，所以只要比被掃描到的元素大，則比該元素往前的都大)，直接進入下一輪
• 指定數(shù)組第一個元素為初始"已排序"序列

具體步驟

• void swap(int[] nums, int i, int j) 是一個輔助方法，交換數(shù)組元素
• void insertSort(int[] nums) 是排序方法(升序排序)
  • for (int i = 0; i < nums.length - 1; i++) 外層循環(huán)表示過程需要"數(shù)組長度 - 1"次循環(huán)，因為默認第一個元素作為"已排序"序列，剩下元素作為"未排序"序列
  • for (int j = i + 1; j > 0; j--) 表示內(nèi)層每一輪循環(huán)，從"未排序"序列第一個元素開始，所以第一次是索引j = 0 + 1，j-- 表示每次是從"已排序"序列的后往前掃描的，由于交換元素的時候可能與第一個"已排序"序列第一個元素，所以內(nèi)層循環(huán)變量j要> 0而不是>= 0
  • if (nums[j] < nums[j - 1]) { swap(nums, j, j - 1); } 這個逐個往前交換的過程實際上就是插入，不滿足條件時break

測試

排序前：[ 4, 5, 2, 3, 6, 7, 9, 8, 1, 4, 5, 1, 7, 9, 6, 5, 8 ]
排序后：[ 1, 1, 2, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 ]

----------------------------華麗的分割線--------------------------------

上面寫的插入排序使用類似冒泡的方法，把插入的數(shù)往"已排序"序列中間插入的，性能有點拉垮，改進一下，上面的方法是每次發(fā)現(xiàn)比插入數(shù)大的，就交換兩個數(shù)，新方法用一個待插入的索引insertIndex，用它指向可能要往后挪的數(shù)，先看完整代碼吧

    private static void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int insertValue = nums[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && nums[insertIndex] > insertValue) {
                nums[insertIndex + 1] = nums[insertIndex];
                insertIndex--;
            }
            if (insertIndex != i - 1) {
                nums[insertIndex + 1] = insertValue;
            }
        }
    }

• insertValue保存本輪要插入的數(shù)
• insertIndex指向可能要插入的位置

演示過程
{1, 3, 4, 2}，把2插入前面時，insertIndex指向4，4 > 2，則nums[insertIndex + 1] = nums[insertIndex]，數(shù)組變成{1, 3, 4, 4}，然后insertIndex指向3，3 > 2則再次賦值，數(shù)組變成{1, 3, 3, 4}，然后insertIndex指向1，此時1 < 2，跳出循環(huán)
nums[insertIndex + 1] = insertValue賦值時索引 + 1是因為insertIndex指向了要插入的前一個位置，插入后{1, 2, 3, 4}
插入時判斷insertIndex != i - 1索引是否為初始值，如果是則說明本輪不需要插入，也就是待插入的數(shù)比"已排序"的所有數(shù)都大，則排最后即可

測試的時候發(fā)現(xiàn)性能足足提高到原來的兩倍多，嘖嘖嘖