希尔排序(附C语言实现) 🚀

希尔排序是一种高效的插入排序算法，它通过将原始列表分割成多个子序列来减少数据项之间的距离，从而提高排序效率。这种方法可以更有效地对数据进行预排序，最终达到整个列表有序的效果。希尔排序的时间复杂度介于O(n log n)到O(n^(3/2))之间，具体取决于所选的增量序列。

下面展示如何使用C语言实现希尔排序：

```c

include

void shellSort(int arr[], int n) {

for (int gap = n / 2; gap > 0; gap /= 2) {

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;

}

}

}

int main() {

int arr[] = {8, 5, 3, 9, 4};

int n = sizeof(arr) / sizeof(arr[0]);

shellSort(arr, n);

printf("Sorted array: \n");

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

return 0;

}

```

上面的代码中，`shellSort`函数实现了希尔排序的核心逻辑。`main`函数则展示了如何调用该排序函数，并输出排序后的结果。希尔排序通过调整间隔（`gap`）值逐步缩小，直到变为1，从而完成整个数组的排序。这种方法使得希尔排序在处理大规模数据时具有明显优势。🚀