插入排序

算法思路

0~i范围上已经有序，新来的数从右到左滑到不再小的位置插入，然后继续

算法步骤

原始数组：[5, 3, 4, 1, 2]

第1轮：3作为新来的数，开始往前对比，小的数往左边插入
第1轮第1比：3 小于 5，交换，变成[3,5,4,1,2]
第1轮结果：[3,5,4,1,2]

第2轮：4作为新来的数，开始往前对比，小的数往左边插入
第2轮第1比：4 小于 5，交换，结果[3,4,5,1,2]
第2轮第2比：4 不小于3，不交换，并停止本轮
第2轮结果：[3,4,5,1,2]

第3轮：1作为新来的数，开始往前对比，小的数往左边插入
第3轮第1比：1 小于 5，交换，结果[3,4,1,5,2]
第3轮第2比：1 小于 4，交换，结果[3,1,4,5,2]
第3轮第3比：1 小于 3，交换，结果[1,3,4,5,2]
第3轮结果：[1,3,4,5,2]

第4轮：2作为新来的数，开始往前对比，小的数往左边插入
第4轮第1比：2 小于 5，交换，结果[1,3,4,2,5] 第4轮第2比：2 小于 4，交换，结果[1,3,2,4,5]
第4轮第3比：2 小于 3，交换，结果[1,2,3,4,5]
第4轮第4比：2 不小于 1，不交换，并停止本轮
第4轮结果：[1,2,3,4,5]

停止的条件：

• 插入的数不比左边小
• 已经是最左边了

像是打牌的时候插牌

算法代码

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    for (int i = 1; i < arr.length; i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

测试方法

public static void main(String[] args) {
    int[] arr = {5, 3, 4, 1, 2};
    insertionSort(arr);
    print(arr);
}

时间复杂度

暂无