希尔排序c语言用stdio与stdlib

希尔排序（Shell Sort），是一种改进后的插入排序算法，通过将数组分割成若干小序列，对每个小序列进行插入排序，随着步长逐渐减小，最后整个序列就变为有序了。以下是使用C语言编写的一个简单希尔排序示例，它利用`stdio.h`用于输入输出，`stdlib.h`库中的`malloc`函数来动态分配内存：

#include <stdio.h>
#include <stdlib.h>

// 选择一个增量序列，如常见的希尔排序中的Hibbard增量序列
#define SHELL_SORT_INCREMENT {10, 5, 2, 1}

void shell_sort(int arr[], int n) {
    int i, j, gap;
    for (gap = SHELL_SORT_INCREMENT[0]; gap > 0; gap /= 2) {
        // 对于当前增量，将数组分为多个子序列
        for (i = gap; i < n; i++) {
            int temp = arr[i];
            // 使用插入排序对子序列进行排序
            j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            // 将元素插入到正确的位置
            arr[j] = temp;
        }
    }
}

int main() {
    int* arr;
    int n, i;

    printf("Enter the number of elements: ");
    scanf("%d", &n);

    // 动态分配内存
    arr = (int*) malloc(n * sizeof(int));

    if (arr == NULL) {
        printf("Memory allocation failed.\n");
        return 1;
    }

    printf("Enter %d numbers: ", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    shell_sort(arr, n);

    printf("Sorted array: \n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    free(arr); // 释放内存
    return 0;
}

在这个例子中，用户首先输入元素的数量，然后逐个输入数值。希尔排序完成后，打印出排序后的数组。注意，在`main()`函数结束时，我们使用`free(arr)`来释放先前动态分配的内存。