排序算法之插入排序

前言：按照王道书上来定义，插入排序又分为直接插入排序，折半插入排序和希尔排序。

1.直接插入排序

将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。直接插入排序是一种稳定的排序算法。

实现代码：

// 插入排序算法实现

void insertion_sort(int arr[], int len) {
  for (int i = 1; i < len; ++i) {  // 从第二个元素开始遍历数组
    int key = arr[i];  // 当前要插入的元素
    int j = i - 1;  // 已排序部分的最后一个元素的索引

    // 在已排序部分寻找合适的位置插入当前元素
    while (j >= 0 && arr[j] > key) {  // 循环条件：索引合法且当前元素比 key 大
      arr[j + 1] = arr[j];  // 将比 key 大的元素后移一位
      j--;  // 继续向前查找合适的位置
    }
    
    arr[j + 1] = key;  // 将当前元素插入到合适的位置
  }
}

时间复杂度最优为O(n)，在数列几乎有序时效率很高。

最坏时间复杂度和平均时间复杂度都O(n^2)

2.折半插入排序

通过二分算法优化性能，在元素多时优化效果明显。

实现代码：

void insertion_sort(int arr[], int len) {
  if (len < 2) return;
  for (int i = 1; i != len; ++i) {
    int key = arr[i];
    auto index = upper_bound(arr, arr + i, key) - arr;
    // 使用 memmove 移动元素，比使用 for 循环速度更快，时间复杂度仍为 O(n)
    memmove(arr + index + 1, arr + index, (i - index) * sizeof(int));
    arr[index] = key;
  }
}

折半插入排序的本质依然是插入排序，仅仅是对插入排序进行了部分优化。而优化的部分就是向前查找比较的部分。其实它就是将查找从暴力枚举一一遍历变为二分查找。所以优化后的时间复杂度仍然不变。

折半插入可以理解为对于每个位置的平均时间复杂度从O(N)查找+O(N)交换移动变成O(logN)查找+Ｏ(n)交换移动。所以，整个时间复杂度依然是Ｏ(n2)

3.希尔排序

通过增量(gap)将元素两两分组，对每组使用直接插入排序算法排序；增量(gap)逐渐减少，当增量(gap)减至1时，整个数据恰被分成一组，最后进行一次插入排序，整个数组就有序了。是一种不稳定的排序算法。

希尔排序过程较复杂，参考动图动画:一篇文章快速学会希尔排序 - 知乎 (zhihu.com)

第一次：

第二次：

第三次：

实现代码：

.

template <typename T>
void shell_sort(T array[], int length) {
  int h = 1;

  // 使用 Knuth 序列确定初始间隔序列
  while (h < length / 3) {
    h = 3 * h + 1;
  }

  // 不断缩小间隔 h，直至 h 为 1
  while (h >= 1) {
    // 对每个间隔为 h 的子序列进行插入排序
    for (int i = h; i < length; i++) {
      // 插入排序，将当前元素插入到已排序序列的正确位置
      for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
        // 如果当前元素小于之前的元素，交换它们的位置
        std::swap(array[j], array[j - h]);
      }
    }
    // 缩小间隔 h
    h = h / 3;
  }
}

希尔排序的最优时间复杂度为O(n)。

希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取有关。