插入排序

算法原理

通过构建有序序列，对于未排序数据，在已排序数据中从后向前扫描，找到相应位置并插入

排序过程

算法描述

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

   复杂度

   | 平均时间复杂度 | O(n^2) | | —- | —- | | 最坏时间复杂度 | O(n^2) | | 最优时间复杂度 | O(n) | | 空间复杂度 | 总共O(n)，需要辅助空间O(1) | | 最佳解 | No | | 排序方式 | in-place | | 稳定性 | 稳定 |

Java代码

    public static void insertSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 新元素
            int key = array[i + 1];
            // 有序数组长度
            int j = i;
            // 取出下一个元素，在已经排序的元素序列中从后向前扫描,如果已排序元素大于新元素
            while (j >= 0 && array[j] > key) {
                // 将已排序元素移到下一位置
                array[j + 1] = array[j];
                j--;
            }
            // 找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置后
            array[j + 1] = key;
        }
    }