首页请你用C语言写出希尔排序的代码

请你用C语言写出希尔排序的代码

时间: 2024-12-25 09:36:57 浏览: 53

希尔排序（Shell Sort），也称为缩小增量排序，是一种插入排序的改进版本，通过将数组分割成若干部分，对每一部分独立进行插入排序，然后逐步减少序列长度直到整个序列有序。以下是希尔排序的一个基本实现，这里使用了经典的Hibbard增量序列： ```c #include <stdio.h> // 希尔排序辅助函数，用于计算增量序列 int gap(int n) { if (n < 10) return n; else if (n % 3 == 0) return n / 3; else if (n % 2 == 0) return n / 2; else return n / 3 + 1; } void shellSort(int arr[], int n) { for (gap = n / 2; gap > 0; gap /= 3) { // 进行多轮插入排序，每次增量减小 for (i = gap; i < n; i++) { // 将元素arr[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; // 将找到的位置赋值给temp } } } // 测试函数 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {9, 7, 5, 11, 12, 2, 14, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array:\n"); printArray(arr, n); shellSort(arr, n); printf("Sorted array after Shell Sort:\n"); printArray(arr, n); return 0; } ``` 在这个例子中，`shellSort`函数首先选择一个增量，然后对每一段进行插入排序，直至增量为1，完成所有增量后的数组就变得有序。

阅读全文