C++ 中怎么实现希尔排序

希尔排序（Shell Sort）是由美国计算机科学家 Donald Shell 在 1959 年提出的一种排序算法。它不同于传统的排序算法，通过将数据分为多个子序列，分别进行插入排序，最后合并为一个有序序列，从而提高排序的效率。希尔排序在实践中已证明是一种高效的排序算法，经常被用作排序大型数据集。

希尔排序的工作原理是，将一组数据按照一定间隔分成若干个子集，对每个子集进行插入排序，逐渐缩小间隔直至为 1。这里的间隔可以自定义，通常会选择一个特定的序列，如希尔序列。希尔序列的定义为：h1, h2, …, hk，其中 hk = 1，而 hi-1 除以 i 是一个整数序列。最常用的希尔序列为：1, 4, 13, 40, 121, 364, 1093…。

下面让我们看一下如何在 C 语言中实现希尔排序：

1、定义希尔排序函数

void shellSort(int arr[], int n)
{
    //循环次数、增量step
    int i, j, step;
    int temp;

    for (step = n / 2; step >= 1; step /= 2)
    {
        //插入排序
        for (i = step; i < n; ++i)
        {
            temp = arr[i];
            for (j = i - step; j >= 0 && arr[j] > temp; j -= step)
            {
                arr[j + step] = arr[j];
            }
            arr[j + step] = temp;
        }
    }
}

在这个函数中，我们定义了循环次数 i、j 和增量 step。增量 step 初始为 n / 2，每次循环时将其除以 2，直到其值为 1。在循环中，我们将数据分为几个子序列，每个子序列都使用插入排序算法。

2、调用希尔排序函数

int main()
{
    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:
");
    printArray(arr, n);

    shellSort(arr, n);

    printf("Sorted array:
");
    printArray(arr, n);

    return 0;
}

在 main 函数中，我们定义了一个整数数组 arr，并使用 sizeof 操作符计算出其长度。然后我们调用了希尔排序函数，将 arr 数组作为参数传递给它。最后，我们调用了一个打印数组函数 printArray，以输出排序后的数组。

3、定义打印数组函数

void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("
");
}

这个函数很简单，只是循环遍历了整个数组，并将每个元素打印出来。

完整的代码如下所示：

#include <stdio.h>

void shellSort(int arr[], int n);
void printArray(int arr[], int n);

int main()
{
    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:
");
    printArray(arr, n);

    shellSort(arr, n);

    printf("Sorted array:
");
    printArray(arr, n);

    return 0;
}

void shellSort(int arr[], int n)
{
    //循环次数、增量step
    int i, j, step;
    int temp;

    for (step = n / 2; step >= 1; step /= 2)
    {
        //插入排序
        for (i = step; i < n; ++i)
        {
            temp = arr[i];
            for (j = i - step; j >= 0 && arr[j] > temp; j -= step)
            {
                arr[j + step] = arr[j];
            }
            arr[j + step] = temp;
        }
    }
}

void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("
");
}

使用希尔排序，在最优情况下排序时间复杂度为 O(n)，在最坏情况下排序时间复杂度为 O(n log^2 n)，但是通常情况下的时间复杂度介于这两种情况之间。虽然希尔排序并不是最快的排序算法，但它相对而言非常容易实现，程序代码量较小，排序效率较高，在大多数场合下都能够很好地工作。