programming

希尔排序算法详解：插入排序的高效改进版本

希尔排序是由Donald Shell于1959年提出的排序算法，它是插入排序的一种改进版本。通过引入”增量序列”的概念，希尔排序有效地解决了插入排序在处理逆序数据时效率低下的问题。

1. 算法原理

1.1 基本思想

希尔排序的核心思想：

  1. 分组排序：按增量将数组分成若干子组
  2. 插入排序：对每个子组进行插入排序
  3. 递减增量：逐步减小增量值
  4. 最终排序：当增量为1时，进行最后一次插入排序

1.2 算法步骤演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
原始数组: [49, 38, 65, 97, 76, 13, 27, 49]

增量序列: 4 → 2 → 1

增量为4时的分组:
组1: [49, 76] → [49, 76]
组2: [38, 13] → [13, 38]  
组3: [65, 27] → [27, 65]
组4: [97, 49] → [49, 97]
结果: [49, 13, 27, 49, 76, 38, 65, 97]

增量为2时的分组:
组1: [49, 27, 76, 65] → [27, 49, 65, 76]
组2: [13, 49, 38, 97] → [13, 38, 49, 97]
结果: [27, 13, 49, 38, 65, 49, 76, 97]

增量为1时：
整个数组进行插入排序
结果: [13, 27, 38, 49, 49, 65, 76, 97]

2. C语言实现

2.1 基础版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Shell原始增量序列 (n/2, n/4, ..., 1)
void shell_sort_basic(int arr[], int n) {
    printf("开始希尔排序...\n");
    
    // 从n/2开始，每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        printf("\n增量 gap = %d:\n", gap);
        
        // 对每个分组进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            
            printf("  处理元素 %d (位置%d):\n", temp, i);
            
            // 在当前分组中进行插入排序
            while (j >= gap && arr[j - gap] > temp) {
                printf("    移动 %d 从位置%d到位置%d\n", 
                       arr[j - gap], j - gap, j);
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = temp;
            printf("    插入 %d 到位置%d\n", temp, j);
            
            // 显示当前状态
            printf("    当前数组: ");
            for (int k = 0; k < n; k++) {
                printf("%d ", arr[k]);
            }
            printf("\n");
        }
        
        printf("增量%d完成后: ", gap);
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
}

// 测试基础希尔排序
void test_basic_shell_sort() {
    printf("=== 基础希尔排序测试 ===\n");
    
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    shell_sort_basic(arr, n);
    
    printf("\n最终结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

2.2 不同增量序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
// Knuth增量序列 (3^k - 1)/2: 1, 4, 13, 40, 121, ...
void shell_sort_knuth(int arr[], int n) {
    printf("使用Knuth增量序列的希尔排序:\n");
    
    // 生成Knuth序列的最大增量
    int gap = 1;
    while (gap < n / 3) {
        gap = gap * 3 + 1;
    }
    
    while (gap >= 1) {
        printf("\nKnuth增量 gap = %d:\n", gap);
        
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = temp;
        }
        
        printf("完成后: ");
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        
        gap /= 3;
    }
}

// Hibbard增量序列: 2^k - 1: 1, 3, 7, 15, 31, ...
void shell_sort_hibbard(int arr[], int n) {
    printf("使用Hibbard增量序列的希尔排序:\n");
    
    // 生成Hibbard序列的最大增量
    int gap = 1;
    while (gap < n) {
        gap = gap * 2 + 1;
    }
    gap /= 2;
    
    while (gap >= 1) {
        printf("\nHibbard增量 gap = %d:\n", gap);
        
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = temp;
        }
        
        printf("完成后: ");
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        
        gap = (gap - 1) / 2;
    }
}

// Sedgewick增量序列
void shell_sort_sedgewick(int arr[], int n) {
    printf("使用Sedgewick增量序列的希尔排序:\n");
    
    // 预定义的Sedgewick序列
    int sedgewick[] = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929};
    int seq_len = sizeof(sedgewick) / sizeof(sedgewick[0]);
    
    // 找到小于n的最大增量
    int start = 0;
    for (int i = seq_len - 1; i >= 0; i--) {
        if (sedgewick[i] < n) {
            start = i;
            break;
        }
    }
    
    for (int k = start; k >= 0; k--) {
        int gap = sedgewick[k];
        printf("\nSedgewick增量 gap = %d:\n", gap);
        
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = temp;
        }
        
        printf("完成后: ");
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
}

// 测试不同增量序列
void test_different_sequences() {
    printf("=== 不同增量序列测试 ===\n");
    
    int original[] = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
    int n = sizeof(original) / sizeof(original[0]);
    
    // 测试Knuth序列
    int arr1[n];
    memcpy(arr1, original, sizeof(original));
    printf("Knuth序列测试:\n");
    shell_sort_knuth(arr1, n);
    printf("\n");
    
    // 测试Hibbard序列
    int arr2[n];
    memcpy(arr2, original, sizeof(original));
    printf("Hibbard序列测试:\n");
    shell_sort_hibbard(arr2, n);
    printf("\n");
    
    // 测试Sedgewick序列
    int arr3[n];
    memcpy(arr3, original, sizeof(original));
    printf("Sedgewick序列测试:\n");
    shell_sort_sedgewick(arr3, n);
    printf("\n");
}

2.3 性能优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// 统计版本：记录比较和移动次数
typedef struct {
    int comparisons;
    int movements;
    double time_taken;
    char* sequence_name;
} ShellSortStats;

void shell_sort_with_stats(int arr[], int n, ShellSortStats* stats, 
                          int gaps[], int gap_count) {
    clock_t start = clock();
    stats->comparisons = 0;
    stats->movements = 0;
    
    for (int g = 0; g < gap_count; g++) {
        int gap = gaps[g];
        
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            stats->movements++;  // 取出元素
            
            while (j >= gap) {
                stats->comparisons++;
                if (arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    stats->movements++;
                    j -= gap;
                } else {
                    break;
                }
            }
            
            if (j != i) {
                arr[j] = temp;
                stats->movements++;
            }
        }
    }
    
    clock_t end = clock();
    stats->time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
}

// 生成Shell原始序列
int generate_shell_gaps(int n, int gaps[]) {
    int count = 0;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        gaps[count++] = gap;
    }
    return count;
}

// 生成Knuth序列
int generate_knuth_gaps(int n, int gaps[]) {
    int count = 0;
    int gap = 1;
    
    // 找到最大的gap
    while (gap < n / 3) {
        gap = gap * 3 + 1;
    }
    
    // 生成序列
    while (gap >= 1) {
        gaps[count++] = gap;
        gap /= 3;
    }
    
    return count;
}

// 性能比较测试
void performance_comparison() {
    printf("=== 增量序列性能比较 ===\n");
    
    const int size = 1000;
    int* original = (int*)malloc(size * sizeof(int));
    
    // 生成测试数据
    srand(time(NULL));
    for (int i = 0; i < size; i++) {
        original[i] = rand() % 1000;
    }
    
    printf("数组大小: %d\n", size);
    printf("%-15s %-12s %-12s %-15s\n", "增量序列", "比较次数", "移动次数", "时间(秒)");
    printf("-------------------------------------------------------\n");
    
    // 测试Shell原始序列
    int* arr1 = (int*)malloc(size * sizeof(int));
    memcpy(arr1, original, size * sizeof(int));
    int shell_gaps[20];
    int shell_count = generate_shell_gaps(size, shell_gaps);
    
    ShellSortStats stats1;
    stats1.sequence_name = "Shell原始";
    shell_sort_with_stats(arr1, size, &stats1, shell_gaps, shell_count);
    
    printf("%-15s %-12d %-12d %-15.6f\n", 
           stats1.sequence_name, stats1.comparisons, 
           stats1.movements, stats1.time_taken);
    
    // 测试Knuth序列
    int* arr2 = (int*)malloc(size * sizeof(int));
    memcpy(arr2, original, size * sizeof(int));
    int knuth_gaps[20];
    int knuth_count = generate_knuth_gaps(size, knuth_gaps);
    
    ShellSortStats stats2;
    stats2.sequence_name = "Knuth";
    shell_sort_with_stats(arr2, size, &stats2, knuth_gaps, knuth_count);
    
    printf("%-15s %-12d %-12d %-15.6f\n", 
           stats2.sequence_name, stats2.comparisons, 
           stats2.movements, stats2.time_taken);
    
    free(original);
    free(arr1);
    free(arr2);
    printf("\n");
}

3. 算法分析

3.1 时间复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void analyze_time_complexity() {
    printf("=== 时间复杂度分析 ===\n");
    
    printf("希尔排序的时间复杂度：\n");
    printf("- 最好情况: O(n log n) (使用最优增量序列)\n");
    printf("- 平均情况: 取决于增量序列的选择\n");
    printf("- 最坏情况: O(n²) (Shell原始序列)\n\n");
    
    printf("不同增量序列的复杂度:\n");
    printf("%-20s %-20s\n", "增量序列", "时间复杂度");
    printf("----------------------------------------\n");
    printf("%-20s %-20s\n", "Shell (n/2^k)", "O(n²)");
    printf("%-20s %-20s\n", "Knuth (3k+1)", "O(n^1.5)");
    printf("%-20s %-20s\n", "Hibbard (2^k-1)", "O(n^1.5)");
    printf("%-20s %-20s\n", "Sedgewick", "O(n^1.25)");
    printf("\n");
    
    printf("空间复杂度: O(1) - 原地排序\n\n");
}

3.2 增量序列选择的影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void analyze_gap_sequences() {
    printf("=== 增量序列选择分析 ===\n");
    
    printf("Shell原始序列 (n/2, n/4, ..., 1):\n");
    printf("- 优点: 简单易实现\n");
    printf("- 缺点: 最坏情况O(n²)\n");
    printf("- 问题: 相邻增量可能有公因数\n\n");
    
    printf("Knuth序列 (3^k-1)/2:\n");
    printf("- 时间复杂度: O(n^1.5)\n");
    printf("- 实际性能优秀\n");
    printf("- 增量间无公因数\n\n");
    
    printf("Hibbard序列 (2^k-1):\n");
    printf("- 时间复杂度: O(n^1.5)\n");
    printf("- 理论分析完善\n");
    printf("- 增量互质\n\n");
    
    printf("Sedgewick序列:\n");
    printf("- 时间复杂度: O(n^1.25)\n");
    printf("- 实际性能最佳\n");
    printf("- 复杂度最低\n\n");
    
    printf("选择原则:\n");
    printf("1. 增量序列应互质（最大公约数为1）\n");
    printf("2. 最后一个增量必须为1\n");
    printf("3. 增量递减速度要适中\n\n");
}

4. 优缺点与应用

4.1 优点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void shell_sort_advantages() {
    printf("=== 希尔排序的优点 ===\n");
    
    printf("1. 改进的插入排序\n");
    printf("   - 减少了数据移动距离\n");
    printf("   - 提高了整体效率\n\n");
    
    printf("2. 原地排序\n");
    printf("   - 空间复杂度O(1)\n");
    printf("   - 内存使用效率高\n\n");
    
    printf("3. 实现简单\n");
    printf("   - 代码简洁易懂\n");
    printf("   - 容易调试和维护\n\n");
    
    printf("4. 性能稳定\n");
    printf("   - 对各种数据分布适应性好\n");
    printf("   - 不会退化到O(n²)\n\n");
    
    printf("5. 实用性强\n");
    printf("   - 中等规模数据排序的好选择\n");
    printf("   - 嵌入式系统友好\n\n");
}

4.2 缺点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void shell_sort_disadvantages() {
    printf("=== 希尔排序的缺点 ===\n");
    
    printf("1. 不稳定排序\n");
    printf("   - 可能改变相等元素的相对位置\n");
    printf("   - 不适合需要稳定性的场景\n\n");
    
    printf("2. 增量序列依赖\n");
    printf("   - 性能高度依赖增量序列选择\n");
    printf("   - 最优序列仍在研究中\n\n");
    
    printf("3. 理论分析困难\n");
    printf("   - 精确的复杂度分析很困难\n");
    printf("   - 平均情况分析复杂\n\n");
    
    printf("4. 不如高级算法\n");
    printf("   - 对大数据集不如快排、归并\n");
    printf("   - 最优复杂度仍高于O(n log n)\n\n");
}

4.3 应用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void shell_sort_applications() {
    printf("=== 应用场景 ===\n");
    
    printf("1. 中等规模数据排序\n");
    printf("   - 数组大小在几百到几万\n");
    printf("   - 对性能有要求但不苛刻\n\n");
    
    printf("2. 嵌入式系统\n");
    printf("   - 内存受限环境\n");
    printf("   - 代码简洁性要求高\n\n");
    
    printf("3. 教学和学习\n");
    printf("   - 理解排序算法改进思想\n");
    printf("   - 增量序列设计研究\n\n");
    
    printf("4. 预排序阶段\n");
    printf("   - 为其他算法做数据预处理\n");
    printf("   - 改善数据局部性\n\n");
    
    printf("5. 实时系统\n");
    printf("   - 性能可预测\n");
    printf("   - 无递归开销\n\n");
}

5. 主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    printf("========================================\n");
    printf("       希尔排序算法完整演示\n");
    printf("========================================\n\n");
    
    test_basic_shell_sort();
    test_different_sequences();
    performance_comparison();
    analyze_time_complexity();
    analyze_gap_sequences();
    shell_sort_advantages();
    shell_sort_disadvantages();
    shell_sort_applications();
    
    printf("========================================\n");
    printf("            测试完成\n");
    printf("========================================\n");
    
    return 0;
}

6. 总结

希尔排序是一种重要的排序算法，具有以下特点：

核心价值

  • 改进思想: 通过增量序列改进插入排序
  • 实用性强: 在中等规模数据上表现优异
  • 理论意义: 体现了算法改进的重要思想

技术特点

  • 空间高效: O(1)空间复杂度
  • 实现简单: 代码简洁易懂
  • 性能稳定: 不会退化到最坏情况

学习价值

希尔排序展示了如何通过巧妙的思想改进现有算法，其增量序列的设计思想对算法研究有重要启发意义。虽然不是最优的排序算法，但其实用性和教学价值使其成为算法学习中的重要一环。

理解希尔排序有助于：

  • 掌握算法改进的基本思路
  • 理解增量序列设计的重要性
  • 为学习更高级的排序算法奠定基础

版权所有，如有侵权请联系我