排序算法-希尔排序

一、算法介绍

????????希尔排序是一种基于插入排序的高效、不稳定的排序算法，它通过对待排序序列进行一系列间隔划分的子序列排序来改进插入排序的性能。该算法的基本思想是先将整个序列分割成若干个子序列，然后分别对各个子序列进行插入排序。这一过程通过逐渐减小子序列的间隔，最终达到整个序列基本有序的状态。

具体而言，希尔排序的步骤如下：

1. 选择一个增量序列，通常以n/2、n/4、n/8...等方式逐渐减小，直至增量为1。
2. 对于每个增量，将序列划分为若干个子序列，分别对这些子序列进行插入排序。
3. 逐渐缩小增量，重复上述子序列的插入排序过程，直至增量为1。
4. 最终，以增量为1的插入排序将整个序列排序完成。

????????希尔排序之所以比插入排序更快，是因为在初始阶段，序列的局部顺序已经得到改善，这有助于减少后续插入排序的比较和交换次数。希尔排序的时间复杂度依赖于所选择的增量序列，最坏情况下为O(n^2)，但在一般情况下，其性能相对较好，接近O(n log n)。希尔排序是一种原地排序算法，但不稳定，因为在不同的增量阶段，相等元素的相对位置可能会发生改变。

二、代码示例

void shell_sort(int index[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1) {
        for (i = gap; i < len; i++) {
            temp = index[i];
            for (j = i - gap; j >= 0 && index[j] > temp; j -= gap)
                index[j + gap] = index[j];
            index[j + gap] = temp;
        }
    }
}