插入排序

2021-07-05
2025-04-27
  1/**
  2 * 插入排序的Java实现
  3 * <p>
  4 * 假设有数组a[N]，插入排序的原理是：
  5 * <br>
  6 * 排序由N-1趟完成，从i = 1开始到N-1趟，插入排序保证从0到i-1位置上的元素是已排序的。
  7 * <br>
  8 * 因此第i趟时，只需要将位置i上的元素插入到已排序的元素中。
  9 * <p>
 10 * 假设有数组【34, 16, 25, 8, 56, 42, 17】，那么插入排序需要6趟，即可完成排序：
 11 * <table BORDER CELLPADDING=3 CELLSPACING=1>
 12 * <caption>插入排序的过程</caption>
 13 * <tr>
 14 * <td>原数组</td>
 15 * <td>34</td>
 16 * <td>16</td>
 17 * <td>25</td>
 18 * <td>8</td>
 19 * <td>56</td>
 20 * <td>42</td>
 21 * <td>17</td>
 22 * <td>移动的位置</td>
 23 * </tr>
 24 * <tr>
 25 * <td>第一趟</td>
 26 * <td>16</td>
 27 * <td>34</td>
 28 * <td>25</td>
 29 * <td>8</td>
 30 * <td>56</td>
 31 * <td>42</td>
 32 * <td>17</td>
 33 * <td>1</td>
 34 * </tr>
 35 * <tr>
 36 * <td>第二趟</td>
 37 * <td>16</td>
 38 * <td>25</td>
 39 * <td>34</td>
 40 * <td>8</td>
 41 * <td>56</td>
 42 * <td>42</td>
 43 * <td>17</td>
 44 * <td>1</td>
 45 * </tr>
 46 * <tr>
 47 * <td>第三趟</td>
 48 * <td>8</td>
 49 * <td>16</td>
 50 * <td>25</td>
 51 * <td>34</td>
 52 * <td>56</td>
 53 * <td>42</td>
 54 * <td>17</td>
 55 * <td>3</td>
 56 * </tr>
 57 * <td>第四趟</td>
 58 * <td>8</td>
 59 * <td>16</td>
 60 * <td>25</td>
 61 * <td>34</td>
 62 * <td>56</td>
 63 * <td>42</td>
 64 * <td>17</td>
 65 * <td>0</td>
 66 * </tr>
 67 * <td>第五趟</td>
 68 * <td>8</td>
 69 * <td>16</td>
 70 * <td>25</td>
 71 * <td>34</td>
 72 * <td>42</td>
 73 * <td>56</td>
 74 * <td>17</td>
 75 * <td>1</td>
 76 * </tr>
 77 * <td>第六趟</td>
 78 * <td>8</td>
 79 * <td>16</td>
 80 * <td>17</td>
 81 * <td>25</td>
 82 * <td>34</td>
 83 * <td>42</td>
 84 * <td>56</td>
 85 * <td>4</td>
 86 * </tr>
 87 * </table>
 88 *
 89 * <p>
 90 * 关于插入排序的复杂度分析，完全参考冒泡排序{@link BubbleSort}的分析过程。<br>
 91 * 插入排序也是稳定排序。
 92 * </p>
 93 *
 94 * @author wangy
 95 * @version 1.0
 96 * @date 2021/7/5 / 09:11
 97 */
 98public class InsertSort {
 99
100    // 通过比较->交换来排序
101    // 平均时间复杂度O(N^2)
102    static void sort(int[] a) {
103        for (int i = 1; i < a.length; i++) {
104            for (int j = 0; j < i; j++) {
105                // 元素交换
106                if (a[j] > a[i]) {
107                    int swap = a[j];
108                    a[j] = a[i];
109                    a[i] = swap;
110                }
111            }
112            System.out.println("===> " + Arrays.toString(a));
113        }
114    }
115
116    // 通过比较->移动来排序
117    // 时间复杂度 O(N^2)
118    // 性能更好的插入排序
119    static void sort2(int[] a) {
120        for (int i = 1; i < a.length; i++) {
121            int tmp = a[i];
122            int j;
123            for (j = i; j > 0 && a[j - 1] > tmp; j--) {
124                // 元素右移
125                a[j] = a[j - 1];
126            }
127            a[j] = tmp;
128            System.out.println("===> " + Arrays.toString(a));
129        }
130    }
131
132    /**
133     * <a href =
134     * "https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F">
135     * 希尔排序</a>
136     * <p>
137     * 简单讲，希尔排序是带<b>步长</b>的插入排序。
138     * <br>
139     * 希尔排序通过【h1, h2,...,hk】步长序列分别对数组中的元素进行插入排序。
140     * 步长序列是任意的，只要保证<code>h1 =1</code>即可。
141     * <br>
142     * 常用的步长序列（不是最好的）为 h(k) = h(k+1)/2，该序列的最坏时间复杂度为O(N^2)。
143     * <p>
144     * 关于复杂度的证明，稍微繁琐，此处不予讨论，仅给出代码实现
145     * </p>
146     */
147    static void shellSort(int[] a) {
148
149        for (int step = a.length / 2; step > 0; step /= 2) {
150            for (int i = step; i < a.length; i++) {
151                int temp = a[i];
152                int j = i - step;
153                while (j >= 0 && a[j] > temp) {
154                    a[j + step] = a[j];
155                    j -= step;
156                }
157                a[j + step] = temp;
158            }
159        }
160    }
161
162    public static void main(String[] args) {
163        int[] a = new int[] { 34, 16, 25, 8, 56, 42, 17 };
164
165        // InsertSort.sort(a);
166
167        InsertSort.shellSort(a);
168        System.out.println(Arrays.toString(a));
169    }
170}
xf&pl

插入排序
