希尔排序

算法描述

希尔排序是一种基于插入排序的排序算法，它通过将数组的相距一定间隔的元素进行比较和交换来实现排序。具体步骤如下：

选择一个增量序列，通常使用 Knuth 增量序列 $（gap = gap * 3 + 1）$ 来计算初始间隔值。
根据间隔值对数组进行分组。将相距间隔值的元素分为一组，并对每组进行插入排序。
逐步缩小间隔值，重复进行分组和插入排序操作，直到间隔值为 1。
最后一次使用间隔值为 $1$ 的插入排序，完成整个排序过程。

具体描述如下：

选择一个增量序列，通常使用 Knuth 增量序列 $（gap = gap * 3 + 1）$ 来计算初始间隔值。增量序列是一系列递减的间隔值，用于确定分组的间隔。
根据初始间隔值进行分组。将数组的相距间隔值的元素分为一组，每个分组内的元素之间的间隔为初始间隔值。
对每个分组进行插入排序。在每个分组内部，使用插入排序的思想，将元素按照从小到大的顺序进行排序。即从第二个元素开始，逐个将元素与之前已排序的元素进行比较，如果前面的元素较大，则交换它们的位置，直到找到合适的位置插入当前元素。
缩小间隔值。通过减小间隔值的方式，重复进行分组和插入排序操作。每次迭代，间隔值减小，分组的元素逐渐增多，直到间隔值为 1。
最后一次使用间隔值为 $1$ 的插入排序。当间隔值减小到 $1$ 时，整个数组被分为一组，使用插入排序对整个数组进行最后一次排序。
完成排序。经过多次分组和插入排序操作后，数组中的元素按照从小到大的顺序排列。

希尔排序的核心思想是通过多次分组和插入排序操作，逐步减小间隔值，使得整个数组的元素逐渐接近它们的最终位置。相比于传统的插入排序，希尔排序在初始阶段可以快速将较小的元素移动到前面的位置，从而减少了后续插入排序的比较和交换次数，提高了排序的效率。最坏情况下，希尔排序的时间复杂度可以达到 $O(n^2)$ ，然而，当使用一些好的增量序列时，希尔排序的时间复杂度可以显著降低。例如，Hibbard 增量序列 $（1, 3, 7, 15, ... 2^{k-1}）$ 的希尔排序时间复杂度为 $O(n^{(3/2)})$ ，而 Sedgewick 增量序列 $（1, 5, 19, 41, 109, ... 4^k+3*2^{(k-1)+1}）$ 的希尔排序时间复杂度为 $O(n^{(4/3)})$ 。

编程实现

#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int size) {
    int gap, i, j, temp;

    // 使用 Knuth 增量序列计算初始间隔值
    gap = 1;
    while (gap < size / 3) {
        gap = gap * 3 + 1;
    }

    // 根据间隔值进行插入排序
    while (gap > 0) {
        for (i = gap; i < size; i++) {
            temp = arr[i];
            j = i;

            // 在已排序的子数组中，向后移动元素直到找到合适的位置
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = temp;
        }

        // 缩小间隔值
        gap = (gap - 1) / 3;
    }
}

// 打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：");
    printArray(arr, size);

    shellSort(arr, size);

    printf("排序后的数组：");
    printArray(arr, size);

    return 0;
}

希尔排序

算法描述​

编程实现​

算法描述

编程实现