分组插入排序算法:
取整数d1 = n / 2; 元素分成d1个组， 每组元素相邻元素距离d1。在各组内进行直接插入排序。
取第二个整数d2 = n / 2, 重复上述分组排序过程知道di = 1。即所有元素在同一组内直接排序。
希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序。直至最后一趟排序使得所有数据有序。

#include "cstdio"


void Shell_Sort(int arr[], int length){
    // 初始化希尔排序的间隔（gap）为数组长度的一半
    for(int gap = length / 2; gap > 0; gap = gap / 2){
        // 对间隔为gap的元素进行插入排序
        for(int i = gap; i < length; i++){
            // 保存当前位置的数值
            int current = arr[i];
            int j = 0;
            // 对当前元素前面的所有间隔为gap的元素进行比较，依次向前
            for(j = i - gap; j >= 0 && arr[j] > current; j = j - gap){
                // 如果前面的元素大于当前元素，将其后移一个间隔
                arr[j + gap] = arr[j];
            }
            // 将当前元素插入到正确的位置上
            arr[j + gap] = current;
        }
    }
}


void Display(int arr[], int length){
    for(int count = 0; count < length; count++){
        printf("%d, ", arr[count]);
    }
    printf("\n");
}


int main() {
    int arr[] = {8, 32, 22, 73, 95, 13, 9, 82, 23, 46, 71, 52, 90, 53, 77, 75, 65, 64, 74, 24};
    int length = sizeof (arr) / sizeof(arr[0]);
    Display(arr, length);
    Shell_Sort(arr, length);
    Display(arr, length);
    return 0;
}