C 语言实现链式基数排序：对超 100000 随机序列排序并精准统计运行时间

以下是一个使用 C 语言实现链式基数排序的程序示例，并且对随机生成的 100000 个元素的序列进行排序并统计运行时间： ```c #include <stdio.h> #include <stdlib.h> #include <time.h> // 链表节点结构体 typedef struct Node { int data; struct Node* next; } Node; // 创建新节点 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = NULL; return newNode; } // 获取数字的指定位数的值 int getDigit(int num, int digit) { int div = 1; for (int i = 0; i < digit; i++) { div *= 10; } return (num / div) % 10; } // 基数排序函数 void radixSort(Node head, int numDigits) { Node* buckets[10]; Node* temp; for (int digit = 0; digit < numDigits; digit++) { // 初始化桶 for (int i = 0; i < 10; i++) { buckets[i] = NULL; } temp = *head; // 将元素分配到桶中 while (temp!= NULL) { int bucketIndex = getDigit(temp->data, digit); Node* newNode = createNode(temp->data); if (buckets[bucketIndex] == NULL) { buckets[bucketIndex] = newNode; } else { Node* curr = buckets[bucketIndex]; while (curr->next!= NULL) { curr = curr->next; } curr->next = newNode; } temp = temp->next; } // 重建链表 *head = NULL; for (int i = 0; i < 10; i++) { temp = buckets[i]; while (temp!= NULL) { Node* next = temp->next; temp->next = *head; *head = temp; temp = next; } } } } // 打印链表 void printList(Node* head) { Node* temp = head; while (temp!= NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } // 释放链表内存 void freeList(Node* head) { Node* temp; while (head!= NULL) { temp = head; head = head->next; free(temp); } } int main() { Node* head = NULL; Node* tail = NULL; // 随机数生成并创建链表 srand(time(NULL)); for (int i = 0; i < 100000; i++) { int num = rand(); Node* newNode = createNode(num); if (head == NULL) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } } clock_t start = clock(); radixSort(&head, 6); // 假设最大数字为 6 位数 clock_t end = clock(); printf("Sorted list: "); printList(head); double timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC; printf("Time taken: %f seconds\n", timeTaken); freeList(head); return 0; } ``` 这个程序首先随机生成 100000 个数字构建链表，然后进行基数排序，并统计排序所花费的时间。实际运行时间会受到计算机性能的影响。 ######[AI写代码神器 | 925点数解答 | 2024-10-13 22:10:29]