希尔排序怎么用c++写

希尔排序是一种插入排序算法。它的基本思想是：将整个待排序的记录序列分割成若干子序列，并对子序列分别进行插入排序。最后，再将有序的子序列合并成整体。

希尔排序的时间复杂度取决于增量序列的选择。如果使用不当，希尔排序的时间复杂度可能达到 O(n^2)。但是，如果使用合适的增量序列，希尔排序的时间复杂度可以达到 O(n^1.3)。

下面是一个使用 C 语言实现的希尔排序函数的示例：

#include <stdio.h>

void shell_sort(int array[], int length) {
  int gap, i, j, temp;
  for (gap = length / 2; gap > 0; gap /= 2) {
    for (i = gap; i < length; i++) {
      temp = array[i];
      for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
        array[j] = array[j - gap];
      }
      array[j] = temp;
    }
  }
}

int main() {
  int array[] = {5, 2, 4, 6, 1, 3};
  int length = sizeof(array) / sizeof(array[0]);
  shell_sort(array, length);
  for (int i = 0; i < length; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");
  return 0;
}

上面的代码实现了希尔排序的基本流程。首先，通过设置 gap 为数组长度的一半，然后不断将 gap 除以 2，来枚举所有可能的增量值。然后，使用双重循环，对每一个增量值进行插入