排序算法--希尔排序

希尔排序是插入排序的改进版本，适合中等规模数据排序，性能优于简单插入排序。

// 希尔排序函数
void shellSort(int arr[], int n) {// 初始间隔（gap）为数组长度的一半，逐步缩小for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个间隔进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i]; // 当前需要插入的元素int j;// 将比 temp 大的元素向后移动for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp; // 插入 temp 到正确位置}}
}

#include <stdio.h>
// 打印数组函数
void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 34, 54, 2, 3}; // 待排序数组int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度printf("排序前的数组: \n");printArray(arr, n);shellSort(arr, n); // 调用希尔排序函数printf("排序后的数组: \n");printArray(arr, n);return 0;
}

优化建议

1.优化间隔序列：使用更高效的间隔序列（如 Hibbard 或 Sedgewick 序列）可以提升性能。

void shellSortOptimized(int arr[], int n) {int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1}; // Sedgewick 序列int gapsSize = sizeof(gaps) / sizeof(gaps[0]);for (int k = 0; k < gapsSize; k++) {int gap = gaps[k];for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

2.结合插入排序：当间隔缩小到 1 时，希尔排序退化为插入排序，适合小规模数据。

3.稳定性：希尔排序是不稳定的排序算法（相同元素的相对顺序可能改变）。