C语言实现排序之希尔排序算法

一、希尔排序算法

基本思想

希尔排序通过选择一个间隔序列来将原始数组分成若干个子数组，对这些子数组进行插入排序，然后再逐步减少间隔直至1，最终完成整个数组的排序。

步骤

1. 选择间隔：首先选择一个初始间隔 gap，通常是数组长度的一半。
2. 分组并排序：将数组按照 gap 分隔成若干个子数组，对这些子数组进行插入排序。
3. 缩小间隔：每次迭代都将 gap 缩小一半，重复步骤2，直到 gap 变为1。

示例

假设我们有一个数组 [5, 2, 4, 6, 1, 3]：

1. 选择间隔：gap = 3（数组长度为6，取一半）
2. 分组并排序：
   • [5, 4] -> [4, 5]
   • [2, 1] -> [1, 2]
   • [6, 3] -> [3, 6]
   • 经过第一轮排序后数组变为 [4, 1, 5, 3, 2, 6]
3. 缩小间隔：gap = 1（数组长度为6，取一半）
4. 分组并排序：
   • 进行插入排序，得到最终排序结果 [1, 2, 3, 4, 5, 6]

性能分析

• 时间复杂度：平均情况下接近 O(n^(3/2))，具体取决于所选的间隔序列；最坏情况为 O(n^2)。
• 空间复杂度：O(1)（原地排序）。

二、代码

#include <stdlib.h>
#include <stdio.h>
#include <time.h>// 函数声明
int* create_and_generate_random_array(int size);
void print_array(int *array, int size);
void shell_sort(int *array, int size);
int generate_random_size();int main() {int size = generate_random_size(); // 随机生成数组大小int *array = create_and_generate_random_array(size);if (array == NULL) {// 如果内存分配失败printf("Memory allocation failed\n");free(array);return 1;}// 打印原始数组（如果需要，可以取消注释）// printf("Original array:\n");// print_array(array, size);// 获取开始时间clock_t start_time = clock();// 对数组进行希尔排序shell_sort(array, size);// 获取结束时间clock_t end_time = clock();// 计算时间差并转换为毫秒double execution_time = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000;// 打印排序后的数组（如果需要，可以取消注释）// printf("Sorted array:\n");// print_array(array, size);printf("array_size = %d\n", size);// 打印执行时间printf("Execution time: %.2f ms\n", execution_time);// 释放分配的内存free(array);return 0;
}// 生成随机数组大小
int generate_random_size() {srand(time(NULL));return rand() % 9000 + 1000; // 生成1000到9999之间的随机数
}// 创建并生成随机数组
int* create_and_generate_random_array(int size) {int *array = (int *)malloc(sizeof(int) * size);if (array == NULL) {// 如果内存分配失败return NULL;}// 使用当前时间作为随机数种子srand(time(NULL));for (int i = 0; i < size; i++) {array[i] = rand() % 1000; // 生成0到999之间的随机数}return array;
}// 打印数组
void print_array(int *array, int size) {for (int i = 0; i < size; i++) {printf("%d ", array[i]);}printf("\n");
}// 希尔排序
void shell_sort(int *array, int size) {int gap, i, j, temp;for (gap = size / 2; gap > 0; gap /= 2) {for (i = gap; i < size; i++) {temp = array[i];for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {array[j] = array[j - gap];}array[j] = temp;}}
}