C语言实现希尔排序算法详解

C语言实现希尔排序算法详解

引用

CSDN

1.

https://m.blog.csdn.net/qq_42037383/article/details/140025479

希尔排序是一种基于插入排序的改进算法，通过分组和逐步缩小间隔的方式，显著提升了排序效率。本文将详细介绍希尔排序的原理、实现步骤，并通过C语言代码示例和动画演示（由于系统原因，动画无法显示，但描述部分仍然清晰），帮助读者全面理解这一经典算法。

原理

希尔排序的核心思想是将数组分成若干个间隔为h的子数组，对每个子数组分别进行插入排序。通过逐步缩小间隔h（通常称为增量），最终使整个数组基本有序。最后一次的插入排序实际上是对几乎已经排好序的数组进行最后的微调。

算法步骤

1. 选择增量序列：选择一个增量序列，逐步缩小增量。
2. 分组排序：按照当前增量将数组分成若干个子数组。
3. 插入排序：对每个子数组进行插入排序。
4. 减小增量：重复上述步骤，缩小增量直到增量为1。

以下是希尔排序的动画演示，有助于理解其工作原理：

#include <stdio.h>

// 希尔排序函数
void shell_sort(int arr[], int n) {
    int gap, i, j, temp;
    
    // 初始化增量gap为数组长度的一半，逐步减半
    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, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 调用希尔排序函数
    shell_sort(arr, n);
    
    printf("排序后的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

特性与复杂度分析

• 时间复杂度：希尔排序的时间复杂度依赖于增量序列的选择，最好情况下为O(n log n)，最坏情况下为O(n^2)。
• 稳定性：希尔排序是不稳定的排序算法，因为在插入排序过程中，可能会改变相同元素的相对顺序。
• 空间复杂度：希尔排序的空间复杂度为O(1)，是一种原地排序算法。