C语言实现希尔排序算法
简介
希尔排序（Shell Sort）是插入排序的一种改进版本，也被称为“缩小增量排序”。它由 Donald Shell 于 1959 年发明。希尔排序通过将原始数据分成多个子序列，对每个子序列进行插入排序，逐步减少增量，最终使得整个序列有序。这种方法能够在一定程度上减少数据移动的次数，提高排序效率。相比于简单的插入排序，希尔排序在处理大规模数据时表现更为出色。
目录
- 基础概念
- 使用方法
- 常见实践
- 最佳实践
- 代码示例
- 小结
- 参考资料
基础概念
1. 插入排序回顾
在理解希尔排序之前，先来回顾一下插入排序。插入排序的基本思想是将数组分为已排序和未排序两部分，每次从未排序部分选择一个元素，插入到已排序部分的合适位置。插入排序在数据基本有序时效率较高，但对于大规模无序数据，效率较低。
2. 希尔排序原理
希尔排序引入了“增量”（increment）的概念。它首先将数组按照一个较大的增量分成多个子序列，每个子序列中的元素间隔为增量值。对每个子序列分别进行插入排序，使得数组中的元素大致有序。然后逐步减小增量，重复上述过程，直到增量为 1 时，整个数组就基本有序了，最后进行一次普通的插入排序。
例如，对于数组 [9, 1, 5, 8, 3, 7, 4, 6, 2]，初始增量设为 4，则分成的子序列为 [9, 3]，[1, 7]，[5, 4]，[8, 6]，[2]。对这些子序列分别进行插入排序后，数组变为 [3, 1, 4, 6, 2, 7, 5, 8, 9]。随着增量的减小，子序列越来越接近最终的有序状态。
使用方法
1. 选择增量序列
增量序列的选择对希尔排序的性能有重要影响。常见的增量序列有原始希尔增量序列（h = n/2, h = h/2,..., h = 1），还有 Hibbard 增量序列（1, 3, 7,..., 2^k - 1）等。不同的增量序列在不同的数据规模和分布下表现各异。
2. 实现步骤
- 确定初始增量值。
- 按照增量值将数组分成多个子序列，对每个子序列进行插入排序。
- 减小增量值，重复步骤 2，直到增量值为 1。
- 当增量值为 1 时，对整个数组进行一次插入排序，此时数组已经基本有序。
常见实践
1. 简单实现
下面是使用原始希尔增量序列的简单实现：
#include <stdio.h>
// 交换两个整数的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 希尔排序函数
void shellSort(int arr[], int n) {
int gap, i, j;
// 初始化增量
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
int temp = arr[i];
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
// 打印数组函数
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
shellSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}2. 性能分析
希尔排序的时间复杂度依赖于增量序列的选择。对于原始希尔增量序列，时间复杂度大致在 $O(n^2)$ 到 $O(n^{1.3})$ 之间。而 Hibbard 增量序列的时间复杂度为 $O(n^{3/2})$。空间复杂度为 $O(1)$，因为它是在原数组上进行排序，不需要额外的大量存储空间。
最佳实践
1. 选择合适的增量序列
经过大量实验和研究，一些特定的增量序列在不同情况下表现更好。例如，Sedgewick 增量序列在许多实际应用中展现出了较好的性能。Sedgewick 增量序列的元素为 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,...。使用该增量序列可以有效减少数据移动次数，提高排序效率。
2. 针对不同数据类型的优化
如果排序的数据类型不是整数，而是结构体等复杂类型，需要根据具体情况对比较和交换操作进行优化。例如，可以将比较操作封装成一个函数指针，以便在不同的数据类型下灵活使用。
#include <stdio.h>
#include <stdlib.h>
// 定义一个比较函数指针类型
typedef int (*CompareFunc)(const void *, const void *);
// 交换两个 void* 指针所指向的值
void swap(void *a, void *b, size_t size) {
char temp[size];
char *pa = (char *)a;
char *pb = (char *)b;
for (size_t i = 0; i < size; i++) {
temp[i] = pa[i];
pa[i] = pb[i];
pb[i] = temp[i];
}
}
// 希尔排序通用函数
void shellSortGeneric(void *base, size_t num, size_t size, CompareFunc compare) {
size_t gap, i, j;
for (gap = num / 2; gap > 0; gap /= 2) {
for (i = gap; i < num; i++) {
void *temp = (void *)malloc(size);
char *src = (char *)base + i * size;
for (size_t k = 0; k < size; k++) {
((char *)temp)[k] = src[k];
}
for (j = i; j >= gap; j -= gap) {
void *prev = (void *)((char *)base + (j - gap) * size);
if (compare(temp, prev) < 0) {
char *dst = (char *)base + j * size;
for (size_t k = 0; k < size; k++) {
dst[k] = ((char *)prev)[k];
}
} else {
break;
}
}
char *dst = (char *)base + j * size;
for (size_t k = 0; k < size; k++) {
dst[k] = ((char *)temp)[k];
}
free(temp);
}
}
}
// 整数比较函数
int intCompare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
// 打印整数数组函数
void printIntArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printIntArray(arr, n);
shellSortGeneric(arr, n, sizeof(int), intCompare);
printf("Sorted array: ");
printIntArray(arr, n);
return 0;
}小结
希尔排序是一种高效的排序算法，通过合理选择增量序列，可以显著提高排序效率。在实际应用中，需要根据数据规模、数据分布以及数据类型等因素，选择合适的增量序列和优化策略。希望通过本文的介绍，读者能够深入理解希尔排序的原理和实现方法，并在实际编程中灵活运用。
参考资料
- 《算法导论》（第 3 版），Thomas H. Cormen 等著
- Donald Shell, “A High-Speed Sorting Procedure”, Communications of the ACM, 2(7): 30–32, July 1959
- Robert Sedgewick, “A New Lower Bound for Shellsort”, Journal of Algorithms, 7(1): 159–173, 1986