【排序算法】直接插入排序和希尔排序的全方位解读-EW帮帮网

从数组的第二个元素开始，将其视为当前要插入的元素。

与前面已排好序的元素逐个进行比较，从后往前扫描已排序部分。

如果当前要插入的元素小于已排序元素，则将已排序元素向后移动一位，为要插入的元素腾出位置。

继续向前比较，直到找到一个合适的位置，使得当前要插入的元素大于等于前面的元素且小于等于后面的元素（或者已到达数组的起始位置）。

将当前要插入的元素插入到该位置，此时前面的部分序列仍然保持有序。

重复上述步骤，直到整个数组都被排序。

😏图解如下：

😃例如：

对于数组 $[5, 3, 8, 4, 2]$ ，初始时 $5$ 被视为已排序部分，然后处理 $3$ ，将与比较，因为，所以将 $5$ 向后移动一位，得到 $[5, 5, 8, 4, 2]$ ，再将 $3$ 插入到合适位置，此时数组变为 $[3, 5, 8, 4, 2]$ 。接着处理，因为大于已排序部分的最后一个元素，所以直接将 $8$ 插入到已排序部分的后面，数组变为 $[3, 5, 8, 4, 2]$ 。再处理，将 $4$ 与 $8$ ， $5$ 依次比较，移动元素后插入，数组变为 $[3, 4, 5, 8, 2]$ 。最后处理，经过比较和移动，得到最终排序后的数组。

⭐代码实现

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        int key = arr[i];

        // 将arr[i]插入到已排序的子序列arr[0..i - 1]中
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

🌷在这段代码中：

i 用于遍历数组中的元素，从第二个元素开始，因为第一个元素默认已排好序。

key 变量用于存储当前要插入的元素，它的值在每次循环中会更新为 arr[i]。

j 变量用于标记已排序子序列的最后一个元素的位置，初始值为 i - 1。

内层的 while 循环用于在已排序子序列中找到合适的插入位置。如果 arr[j] 大于key，说明 key应该插入到 arr[j] 的前面，所以将 arr[j] 向后移动一位，即 arr[j + 1] = arr[j]，然后 j 减 1，继续向前比较。当找到合适位置（j >= 0 && arr[j] > key 条件不满足）时，将key 插入到 j + 1 的位置，即 arr[j + 1] = key。

⭐性能分析

（一）时间复杂度

最好情况：当输入的数组已经是有序时，直接插入排序的效率最高。在这种情况下，每次插入操作只需要比较一次，不需要移动元素。对于一个长度为的数组，外层循环需要执行 $n - 1$ 次，但内层循环每次只执行一次比较操作。因此，最好情况下的时间复杂度为 $O(n)$
最坏情况：当输入的数组是逆序时，每次插入操作都需要将当前元素与前面已排序的所有元素进行比较和移动。对于第个元素，需要进行次比较和移动操作。那么总的比较和移动次数为 $1 + 2 + 3 +... + (n - 1)$ ，根据等差数列求和公式 $\sum_{k = 1}^{n} k = \frac{n(n + 1)}{2}$ ，这里的和为 $\frac{n(n - 1)}{2}$ ，所以时间复杂度为 $O(n^2)$
平均情况：在平均情况下，假设数组中元素的排列是随机的。对于第个元素，平均需要比较和移动大约 $\frac{i}{2}$ 次。那么总的平均比较和移动次数为 $\sum_{i = 2}^{n} \frac{i}{2}$ ，通过数学推导可得平均时间复杂度也为 $O(n^2)$

（二）空间复杂度

直接插入排序是一种原地排序算法，它只需要常数级别的额外空间，用于存储临时变量。在排序过程中，不需要额外的数组或数据结构来存储数据。因此，空间复杂度为 $O(1)$

（三）稳定性

直接插入排序是稳定的排序算法。这是因为在比较和移动元素的过程中，如果两个元素相等，不会交换它们的位置。只有当待插入元素小于已排序元素时，才会进行移动操作。所以，相等元素的相对顺序在排序前后不会改变，保证了算法的稳定性。

💯希尔排序（Shell sort）

希尔排序是一种对直接插入排序进行改进的高效排序算法。

希尔（shell) 做了俩个步骤，优化了直接插入排序：

预排序，目的在于：让序列接近有序，避免逆序直接插入时更高的时间复杂度

插入排序

⭐原理剖析

希尔排序的基本思想是👉先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行一次直接插入排序。

😛具体操作过程如下：

假设我们有一个数组 [9, 5, 1, 8, 3, 7, 4, 6, 2]，我们将使用希尔排序对其进行排序。

😌步骤一：确定增量序列

通常，我们可以选择增量序列为 n/2，n/4，n/8，...，1，其中 n 是数组的长度。在这个例子中，数组长度为 9，所以初始增量 gap = 9 / 2 = 4。

😛步骤二：按增量分组并进行插入排序

对于增量 gap = 4，我们将数组分成以下子序列：
- 子序列 1：[9, 3]
- 子序列 2：[5, 7]
- 子序列 3：[1, 4]
- 子序列 4：[8, 6]
- 子序列 5：[3, 2]（这里最后一个子序列元素个数可能较少，这是正常的情况）（每种颜色代表不同的子序列）
对每个子序列进行插入排序：
- 子序列 1 [9, 3]：
  - 初始时，9 被认为是已排序部分，3 是待插入元素。
  - 因为 3 < 9，所以将 9 向后移动一位，得到 [9, 9]。
  - 然后将 3 插入到正确位置，此时子序列变为 [3, 9]。
- 子序列 2 [5, 7]：
  - 这里 5 和 7 已经是相对有序的（因为 5 < 7），所以子序列不变，仍为 [5, 7]。
- 子序列 3 [1, 4]：
  - 初始时，1 被认为是已排序部分，4 是待插入元素。
  - 因为 1 < 4，所以 4 直接插入到已排序部分后面，子序列变为 [1, 4]。
- 子序列 4 [8, 6]：
  - 初始时，8 被认为是已排序部分，6 是待插入元素。
  - 因为 6 < 8，所以将 8 向后移动一位，得到 [8, 8]。
  - 然后将 6 插入到正确位置，此时子序列变为 [6, 8]。
- 子序列 5 [3, 2]：
  - 初始时，3 被认为是已排序部分，2 是待插入元素。
  - 因为 2 < 3，所以将 3 向后移动一位，得到 [3, 3]。
  - 然后将 2 插入到正确位置，此时子序列变为 [2, 3]。

经过这一轮对每个子序列的插入排序后，数组变为 [3, 5, 1, 6, 2, 7, 4, 8, 9]。

😜步骤三：减小增量并重复步骤二

此时，我们将增量 gap 更新为 gap = 4 / 2 = 2。

对于增量 gap = 2，我们将数组分成以下子序列：
- 子序列 1：[3, 1, 2, 4]
- 子序列 2：[5, 6, 7, 8]
- 子序列 3：[9]（当增量为 2 时，最后一个元素单独构成一个子序列）（每种颜色代表不同的子序列）
对每个子序列进行插入排序：
- 子序列 1 [3, 1, 2, 4]：
  - 初始时，3 被认为是已排序部分，1 是待插入元素。
  - 因为 1 < 3，所以将 3 向后移动一位，得到 [3, 3]。
  - 再将 1 插入到正确位置，此时子序列变为 [1, 3, 2, 4]。
  - 接着，对于 2，它与 3 比较，因为 2 < 3，将 3 向后移动一位，得到 [1, 3, 3]。
  - 再将 2 与 1 比较，因为 1 < 2，所以 2 插入到 1 后面，此时子序列变为 [1, 2, 3, 4]。
- 子序列 2 [5, 6, 7, 8]：
  - 这里 5，6，7，8 已经是相对有序的（在前面的步骤中已经有一定的有序性），所以子序列不变，仍为 [5, 6, 7, 8]。
- 子序列 3 [9]：
  - 只有一个元素，无需排序。

经过这一轮对每个子序列的插入排序后，数组变为 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

😝步骤四：最后一次增量为 1，进行直接插入排序

此时，gap = 2 / 2 = 1，这实际上就是对整个数组进行直接插入排序。但由于前面的步骤已经使数组基本有序，所以这一步的比较和移动次数会相对较少。

从第二个元素开始，将其与前面已排序的元素进行比较和插入：
- 初始时，2 与 1 比较，因为 1 < 2，所以 2 已经在正确位置，数组不变。
- 接着，3 与 2 和 1 比较，因为 1 < 3 且 2 < 3，所以 3 也在正确位置，数组不变。
- 以此类推，对后面的元素进行比较和插入，最终得到完全有序的数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

这种分阶段使用不同增量进行排序的方式，使得在早期能够让元素快速地移动到大致正确的位置，减少了后期直接插入排序的工作量。