用C语言编写哈希排序算法

哈希排序（Hash Sort）是一种利用哈希函数将记录映射到数组下标以实现排序的算法。下面是用C语言编写的哈希排序算法实现：

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

#define MAX_SIZE 1000
#define HASH_SIZE 100

typedef struct Node {
    int data;
    struct Node *next;
} Node;

void insert(Node **hash_table, int data) {
    int index = data % HASH_SIZE;
    Node *p = (Node *) malloc(sizeof(Node));
    p->data = data;
    p->next = hash_table[index];
    hash_table[index] = p;
}

void hash_sort(int *arr, int n) {
    Node *hash_table[HASH_SIZE] = {0};
    for (int i = 0; i < n; i++)
        insert(hash_table, arr[i]);
    int k = 0;
    for (int i = 0; i < HASH_SIZE; i++) {
        Node *p = hash_table[i];
        while (p) {
            arr[k++] = p->data;
            p = p->next;
        }
    }
}

int main() {
    int n, arr[MAX_SIZE];
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    printf("Enter the elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    hash_sort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

首先定义了一个结构体`Node`，表示哈希表中的链表结点。每个结点包含一个数据成员和一个指向下一个结点的指针。同时定义了常量`MAX_SIZE`和`HASH_SIZE`，分别表示数组最大长度和哈希表大小。

定义了一个`insert`函数，用于将指定的数据插入到哈希表中。计算数据的哈希值并取模得到数组下标，然后将新结点插入到链表的头部。

定义了一个`hash_sort`函数，用于实现哈希排序。先创建一个哈希表数组`hash_table`，将所有元素插入到哈希表中。然后按照哈希表的顺序遍历哈希表，将链表中的元素依次存入原数组中。

最后在主函数中读入数组元素，调用`hash_sort`函数对其排序，并输出结果。