简单插入排序（Insertion Sort） O(n2)

介绍

简单插入排序是一种插入排序算法，在已经有序的数列中相应的位置插入数据使得插入后的数据依旧有序。

算法描述

• 从第一个元素开始，该元素是一个有序数列
• 依次取出下一个没有遍历的元素（A），从后往前扫描数列
• 如果当前元素（A）小于有序数列的元素则继续往前比较
• 重复前面步骤，直到找到A大于等于有序数列的元素
• 将A插入该位置
• 重复步骤2-5直到整个数列有序

稳定性

稳定，因为在插入的时候，相同元素的相对位置并没有发生改变

动图展示

insertionSort.gif

代码实现

public class InsertionSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28};
        int[] res = insertionSort(arrays);
        print(res);
    }

    /**
     * 27   6   27  42  23  15  38  50  35  14  40  28
     * 6    27  27  42  23  15  38  50  35  14  40  28
     * 6    27  27  42  23  15  38  50  35  14  40  28
     * 6    27  27  42  23  15  38  50  35  14  40  28
     * 6    23  27  27  42  15  38  50  35  14  40  28
     * 6    15  23  27  27  42  38  50  35  14  40  28
     * 6    15  23  27  27  38  42  50  35  14  40  28
     * 6    15  23  27  27  38  42  50  35  14  40  28
     * 6    15  23  27  27  35  38  42  50  14  40  28
     * 6    14  15  23  27  27  35  38  42  50  40  28
     * 6    14  15  23  27  27  35  38  40  42  50  28
     * 6    14  15  23  27  27  28  35  38  40  42  50
     */
    public static int[] insertionSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {
            print(arr);
            int current = arr[i];
            int preIdx = i - 1;
            //arr[preIdx] > current 为了确保相同值的相对位置不发生改变
            while (preIdx >= 0 && arr[preIdx] > current) {
                arr[preIdx + 1] = arr[preIdx];
                preIdx--;
            }
            arr[preIdx + 1] = current;
        }

        return arr;
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}