1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/**
 * 插入排序
 *
 * @author PengHao
 * @date 2020-05-21 17:27:17
 */
public class InsertionSort {
    /**
     * 直接插入排序<br>
     * 时间复杂度：<br>
     * 1、待排序数组是递增序列，复杂度为O(n)<br>
     * 2、待排序数组是递减序列，复杂度为O(n^2)<br>
     * 空间复杂度：O(1)<br>
     * 稳定性：稳定<br>
     *
     * @param src 待排序数组
     */
    public static void straightInsertionSort(int[] src) {
        if (src == null) {
            System.err.println("待排序数组不能为null");
            return;
        }
        for (int i = 1; i < src.length; ++i) {
            if (src[i - 1] > src[i]) {
                int key = src[i];
                int j = 0;
                // 循环将比key大的数向后挪一位
                for (j = i - 1; j >= 0 && src[j] > key; --j) {
                    src[j + 1] = src[j];
                }
                // 循环结束说明索引为j的数不存在或者比key小，那么key应该插入到j后面
                src[j + 1] = key;
            }
        }
    }

    /**
     * 折半插入排序<br>
     * 时间复杂度：<br>
     * 1、待排序数组是递增序列，复杂度为O(n)<br>
     * 2、待排序数组是递减序列，复杂度为O(n^2)<br>
     * 空间复杂度：O(1)<br>
     * 稳定性：稳定<br>
     *
     * @param src 待排序数组
     */
    public static void binaryInsertionSort(int[] src) {
        if (src == null) {
            System.err.println("待排序数组不能为null");
            return;
        }
        for (int i = 1; i < src.length; ++i) {
            if (src[i - 1] > src[i]) {
                int key = src[i];
                int left = 0, right = i - 1;
                // 二分查找第一个比key大的数的索引
                while (left < right) {
                    int mid = left + (right - left >> 1);
                    if (src[mid] > key) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                if (i - left >= 0) {
                    // 将区间[left, i - 1]整体后移一位到区间[left + 1, i]上
                    System.arraycopy(src, left, src, left + 1, i - left);
                }
                src[left] = key;
            }
        }
    }

    /**
     * 2-路插入排序
     *
     * @param src 待排序数组
     */
    public static void twoWayInsertionSort(int[] src) {
        if (src == null) {
            System.err.println("待排序数组不能为null");
            return;
        }
        int[] arr = new int[src.length];
        arr[0] = src[0];
        int first = 0;
        int last = 0;
        for (int i = 1; i < src.length; ++i) {
            if (src[i] < arr[0]) {
                if (first == 0) {
                    first = arr.length - 1;
                    arr[first] = src[i];
                } else {
                    int j = 0;
                    for (j = first; j < arr.length && arr[j] < src[i]; ++j) {
                        arr[j - 1] = arr[j];
                    }
                    arr[j - 1] = src[i];
                    --first;
                }
            } else {
                int j = 0;
                for (j = last; j >= 0 && arr[j] > src[i]; --j) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = src[i];
                ++last;
            }
        }
        System.arraycopy(arr, first, src, 0, arr.length - first);
        System.arraycopy(arr, 0, src, arr.length - first, last + 1);
    }

    /**
     * 表插入排序<br>
     * 时间复杂度：<br>
     * 1、待排序数组为递增序列，复杂度为O(n^2)<br>
     * 2、待排序数组为递减序列，复杂度为O(n)<br>
     * 空间复杂度为O(n)<br>
     *
     * @param src 待排序数组
     */
    public static void listInsertionSort(int[] src) {
        if (src == null) {
            System.err.println("待排序数组不能为null");
            return;
        }
        int len = src.length;
        int[] arr = new int[len + 1];
        arr[len] = 0;
        arr[0] = len;
        for (int i = 1; i < len; ++i) {
            int j = len;
            // 找到小于src[i]的最大值的索引
            while (src[arr[j]] < src[i] && arr[arr[j]] < len) {
                j = arr[j];
            }
            // 将src[i]插入到这个数的后面
            arr[i] = arr[j];
            arr[j] = i;
        }
        int[] res = new int[len];
        for (int i = arr[len], j = 0; i < len; i = arr[i], ++j) {
            res[j] = src[i];
        }
        System.arraycopy(res, 0, src, 0, len);
    }
}