经典排序算法系列2-插入排序

Insertion Sort 插入排序

需求

对N个整数升序排序

思路

假如将一个数插入到有序的序列中(升序)，则将该数序列中的每个元素逐个比较，插入到正确的位置。对静态的数据排序，也可按照这种思路，将源序列分为两部分，一部分有序，另一部分无序，逐个将无序中的元素插入到有序序列中。在实现中，有序部分只有源序列的第一个元素。

个人觉得这种排序思路是最符合生活中的思维方式的，比如斗地主起牌时，每拿到一张牌，插入到手中已排好序的牌当中（对于大神不需要捋顺的另当别论。。。）

需要比对的次数

算法评判

• 时间复杂度

  

• 空间复杂度

  

  只需要常量级的辅助空间，所以也叫原地排序

• 稳定性

  如果将后出现的元素插入到相等元素的后面，没有改变两个元素原有的相对次序，则是稳定的。

有两种实现方案，

方案一、在每一次插入过程中，将待插入的元素和前面的元素交换，直至到达正确的位置，实现代码如下

    public void sort1(int[] arr) {
        for (int index = 1; index < arr.length; index++) {
            int i = index - 1;
            while (i >= 0 && arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                i--;
            }
        }
    }

方案二、先用变量将待插入的元素保存起来，向前遍历比较，如果大于待插入元素，则向后移一位，最后待插入元素插入到空位上，实现代码如下

private void sort2(int[] arr) {
    for (int index = 1; index < arr.length; index++) {
        int value = arr[index];
        int i = index - 1;
        while (i >= 0) {
            if (arr[i] > value) {
                //向后移
                arr[i + 1] = arr[i];
                i--;
            } else {
                break;
            }
        }
        arr[i] = value;
    }
}

每一次移动已排好序的元素，方案一需要3次赋值操作，方案二只需要1次。因此方案二更优于方案一。