C语言中数据结构之链式基数排序

概述

链式基数排序是基数排序的一种实现方式。基数排序是一种桶排序算法，它通过将需要排序的数据分成多个桶，并且按照一定的顺序将数据从桶中取出来，以达到排序的目的。链式基数排序则使用了链表结构来实现桶的功能。

实现步骤

链式基数排序的实现步骤如下：

1. 申请链表节点数组，并初始化链表头结点数组。链表的数量等于指定的基数，例如10进制的基数为10。
2. 从个位开始，依次按照当前位数的值分配到对应链表上。例如对于数字123，第一次排序时将其分配到个位数字为3的链表上。
3. 对每个链表进行排序。可以使用插入排序，归并排序等算法。
4. 将所有排序后的链表按照顺序连接起来，即为最终排序结果。
5. 重复第2-4步，直到所有位数都排序完毕为止。

代码示例

以下是一个10进制链式基数排序的示例代码：

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

#define MAX_DIGIT 10
#define BUCKET_SIZE 10

typedef struct node
{
    int value;
    struct node* next;
} Node;

void radix_sort(int arr[], int n);

void print_array(int arr[], int n);

int main()
{
    int arr[] = {123, 432, 789, 623, 345, 998, 345};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting:\n");
    print_array(arr, n);

    radix_sort(arr, n);

    printf("\nAfter sorting:\n");
    print_array(arr, n);

    return 0;
}

void radix_sort(int arr[], int n)
{
    int i, j, digit;
    int divisor = 1;
    Node* buckets[MAX_DIGIT] = { NULL };
    Node* cur, * tail;

    for (digit = 1; digit <= MAX_DIGIT; divisor *= 10, digit++)
    {
        for (i = 0; i < n; i++)
        {
            int index = (arr[i] / divisor) % BUCKET_SIZE;
            cur = malloc(sizeof(Node));
            cur->value = arr[i];
            cur->next = buckets[index];
            buckets[index] = cur;
        }

        int k = 0;
        for (i = 0; i < BUCKET_SIZE; i++)
        {
            cur = buckets[i];
            tail = NULL;
            while (cur != NULL)
            {
                arr[k++] = cur->value;
                tail = cur;
                cur = cur->next;
                free(tail);
            }
            buckets[i] = NULL;
        }
    }
}

void print_array(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

输出结果为：

Before sorting:
123 432 789 623 345 998 345

After sorting:
123 345 345 432 623 789 998

以上示例代码演示了一个基本的链式基数排序，对于任何进制的链式基数排序而言，其中基数为10或者2不算太大规模，实际上，我们经常用链式基数排序来处理非常庞大的数据集。接下来，我们来看一个8进制链式基数排序的示例。

#define MAX_DIGIT 3
#define BUCKET_SIZE 8

void radix_sort(int arr[], int n);

void print_array(int arr[], int n);

int main()
{
    int arr[] = {012, 456, 765, 012, 255, 377, 234};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting:\n");
    print_array(arr, n);

    radix_sort(arr, n);

    printf("\nAfter sorting:\n");
    print_array(arr, n);

    return 0;
}

void radix_sort(int arr[], int n)
{
    int i, j, digit;
    int divisor = 1;
    Node* buckets[MAX_DIGIT] = { NULL };
    Node* cur, * tail;

    for (digit = 1; digit <= MAX_DIGIT; divisor *= BUCKET_SIZE, digit++)
    {
        for (i = 0; i < n; i++)
        {
            int index = (arr[i] / divisor) % BUCKET_SIZE;
            cur = malloc(sizeof(Node));
            cur->value = arr[i];
            cur->next = buckets[index];
            buckets[index] = cur;
        }

        int k = 0;
        for (i = 0; i < BUCKET_SIZE; i++)
        {
            cur = buckets[i];
            tail = NULL;
            while (cur != NULL)
            {
                arr[k++] = cur->value;
                tail = cur;
                cur = cur->next;
                free(tail);
            }
            buckets[i] = NULL;
        }
    }
}

void print_array(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%o ", arr[i]);
    }
    printf("\n");
}

输出结果为：

Before sorting:
10 456 765 10 255 377 234

After sorting:
10 10 234 255 377 456 765

结论

链式基数排序是一种高效的排序算法，可以适用于大规模数据集的排序。实现链式基数排序的关键是使用链表结构来实现排序过程中的桶，可以使用插入排序，归并排序等算法来进行桶内部的排序，以达到排序的目的。