插入算法Insertion Sort

介绍

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法思想

构建有序序列，对未排序的数据在有序队列中依次进行比较，找到相应位置进行插入。

1. 获取待插入的元素
2. 将待插入的元素与前一个元素进行比较
3. 如果当前元素比待插入元素大则将当前元素后移，再重复2-3进行比较

算法实现

public static void insertSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        // 待插入元素
        int needInsert = array[i];
        // 待比较的索引
        int index = i - 1;
        while (index >= 0 && needInsert < array[index]) {
            // 将该位置的元素后移
            array[index + 1] = array[index];
            // 继续比较前一位置元素
            index--;
        }
        // 当前位置满足条件
        array[index + 1] = needInsert;
    }
}

• 最好时间复杂度为当前序列已经有序，O(n)
• 最坏时间复杂度为O(n^2)