插入排序

是将一个数据插入到已经排好序的有序数组中，从而得到一个新的、个数加一的有序数组;

算法适用于少量数据的排序;

时间复杂度为O(n^2);

是稳定的排序方法。

示例代码:

 public int[] insertSort(int[] ary) {
        System.out.println("排序前数组:\t" + Arrays.toString(ary));
        int[] sortAry = new int[ary.length];
        System.arraycopy(ary, 0, sortAry, 0, ary.length);
        for (int i = 1; i < sortAry.length; i++) {
            System.out.println("准备排序组数中第"+i+"个元素");
            int tmp = sortAry[i];
            if (sortAry[i] < sortAry[i - 1]) {
                int j = i - 1;
                for (; j >= 0 && sortAry[j] > tmp; j--) {
                    sortAry[j + 1] = sortAry[j];
                  System.out.println("第" + i + "个元素排序过程:\t" + Arrays.toString(sortAry));
                }
                sortAry[j + 1] = tmp;
            }
            System.out.println("数组中排序第" + i + "个元素后:\t" + Arrays.toString(sortAry));
            System.out.println();
        }
        System.out.println("最后排序结果:\t" + Arrays.toString(sortAry));
        return sortAry;
    }

假设我们要对如下数组进行排序

[42, 41, 31, 7, 17, 2, 55, 26]

排序前数组:[42, 41, 31, 7, 17, 2, 55, 26]

第0个元素是不需要进行排序的,所以是从第1个元素开始排序

准备排序组数中第1个元素:41

第1个元素排序过程:[42, 42, 31, 7, 17, 2, 55, 26]

说明:41小于42,41会对前面的数组元素进行比较移位,并确定好覆盖位置,41存储在tmp变量中

数组中第1个元素排序后:[41, 42, 31, 7, 17, 2, 55, 26]

准备排序组数中第2个元素:31

第2个元素排序过程:[41, 42, 42, 7, 17, 2, 55, 26]

说明:原索引为1的元素42,大于31,42向后移位,31存储在tmp变量中

第2个元素排序过程:[41, 41, 42, 7, 17, 2, 55, 26]

说明:索引为0的元素41,大于31,41向后移位,31存储在tmp变量中

同时索引位置为0,结束遍历,tmp变量存放在当前索引位置0

数组中第2个元素排序后:[31, 41, 42, 7, 17, 2, 55, 26]

准备排序组数中第3个元素:7

第3个元素排序过程:[31, 41, 42, 42, 17, 2, 55, 26]

第3个元素排序过程:[31, 41, 41, 42, 17, 2, 55, 26]

第3个元素排序过程:[31, 31, 41, 42, 17, 2, 55, 26]

数组中第3个元素排序后:[7, 31, 41, 42, 17, 2, 55, 26]

准备排序组数中第4个元素:17

第4个元素排序过程:[7, 31, 41, 42, 42, 2, 55, 26]

第4个元素排序过程:[7, 31, 41, 41, 42, 2, 55, 26]

第4个元素排序过程:[7, 31, 31, 41, 42, 2, 55, 26]

数组中第4个元素排序后:[7, 17, 31, 41, 42, 2, 55, 26]

准备排序组数中第5个元素:2

第5个元素排序过程:[7, 17, 31, 41, 42, 42, 55, 26]

第5个元素排序过程:[7, 17, 31, 41, 41, 42, 55, 26]

第5个元素排序过程:[7, 17, 31, 31, 41, 42, 55, 26]

第5个元素排序过程:[7, 17, 17, 31, 41, 42, 55, 26]

第5个元素排序过程:[7, 7, 17, 31, 41, 42, 55, 26]

数组中第5个元素排序后:[2, 7, 17, 31, 41, 42, 55, 26]

准备排序组数中第6个元素:55

说明:55大于左侧数组中的任何元素,不需要进行移位

数组中第6个元素排序后:[2, 7, 17, 31, 41, 42, 55, 26]

准备排序组数中第7个元素:26

第7个元素排序过程:[2, 7, 17, 31, 41, 42, 55, 55]

第7个元素排序过程:[2, 7, 17, 31, 41, 42, 42, 55]

第7个元素排序过程:[2, 7, 17, 31, 41, 41, 42, 55]

第7个元素排序过程:[2, 7, 17, 31, 31, 41, 42, 55]

数组中第7个元素排序后:[2, 7, 17, 26, 31, 41, 42, 55]

最后排序结果:[2, 7, 17, 26, 31, 41, 42, 55]

可见,在排序的过程中,是将原数组分为了有序数组和无序数组两部分,逐步将后面无序数组中的元素插入到有序数组中的合理位置中.最后所有元素完成遍历,完成排序.