希尔排序

希尔排序是一种高效的排序算法，也被称为缩小增量排序，是直接插入排序的优化版本。它是非稳定的排序算法，时间复杂度为O(n log n)或O(n^(3/2))，取决于步长序列的选择。

希尔排序的基本思想是先将待排序的数组分成若干个子序列，对每个子序列进行插入排序，然后再对整个数组进行一次插入排序。在这个过程中，我们需要选择一个增量序列，将数组分割成不同的子序列。增量序列通常是一个递减的序列，比如{5, 3, 1}。

希尔排序的核心是增量序列的选择，增量序列的选择会影响到算法的时间复杂度和稳定性。增量序列的选择有很多种，比较常用的有希尔增量和Hibbard增量。希尔增量的选择方式是将数组长度不断除以2，直到增量为1，即{1, n/2, n/4, ..., 1}。Hibbard增量的选择方式是将数组长度不断除以2的幂次方，直到增量为1，即{1, 3, 7, 15, ..., 2^k-1}，其中2^k-1小于等于数组长度。

下面是希尔排序的C语言实现代码：

#include <stdio.h>

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    shell_sort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

在这个实现中，我们首先将数组分成一些子数组，这些子数组相互独立且元素个数较少，然后对每个子数组进行插入排序。随着子数组的不断合并，最终整个数组就被排序了。

具体实现中，我们通过计算一个称为“间隔（gap）”的值来确定子数组的大小。然后，我们从第一个子数组开始，对它进行插入排序。之后，我们通过缩小gap的大小来处理下一个子数组，继续进行插入排序，直到最后gap为1。