希尔排序 (Shell Sort)像“分组接力赛”一样一开始步长(gap)很大把相隔很远的元素分到一组进行插入排序让数据能快速跨越到接近最终位置的地方(预排序)然后不断缩小步长让数组越来越接近整体有序最后当步长为 1 时整个数组只需进行一次普通的插入排序就能轻松搞定。核心代码#include stdio.h // 希尔排序函数 void shellSort(int arr[], int n) { // 初始步长设为数组长度的一半每次缩小为原来的一半直到为1 for (int gap n / 2; gap 0; gap / 2) { // 从第 gap 个元素开始对每个子序列进行插入排序 for (int i gap; i n; i) { int temp arr[i]; // 暂存当前需要插入的元素 int j i; // 在当前子序列中将比 temp 大的元素向后移动 gap 个位置 // j - gap 0 保证不越界 while (j - gap 0 arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } // 找到正确位置后将 temp 插入 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[] {64, 34, 25, 12, 22}; int n sizeof(arr) / sizeof(arr[0]); // 计算数组长度 printf(排序前); printArray(arr, n); shellSort(arr, n); // 调用希尔排序 printf(排序后); printArray(arr, n); return 0; }示例演示{64, 34, 25, 12, 22}第 1 趟步长 gap 2 (5/2)目标将相隔 2 个位置的元素分为一组进行预排序。分组情况组1(下标 0, 2, 4){64, 25, 22}组2(下标 1, 3){34, 12}对组1进行插入排序22 25 64排序后组1变为 {22, 25, 64}。对组2进行插入排序12 34排序后组2变为 {12, 34}。第 1 趟结束数组变为 [22, 12, 25, 34, 64]数据整体更有序了。第 2 趟步长 gap 1 (2/2)目标步长缩小为 1相当于对整个数组进行一次普通的插入排序。处理元素 12(下标 1)12 2222 往后挪12 插入到最前面。数组变为[12, 22, 25, 34, 64]处理元素 25(下标 2)25 22无需挪动。处理元素 34(下标 3)34 25无需挪动。处理元素 64(下标 4)64 34无需挪动。第 2 趟结束排序完成。最终结果[12, 22, 25, 34, 64]复杂度时间复杂度是\(O(n^{1.3})\)(平均情况具体取决于步长序列的选取最坏情况为\(O(n^2)\))空间复杂度是\(O(1)\)(原地排序仅需常数级的额外空间用于暂存元素)