按链式基数排序的方法实现对整数表的排序。用C++写

链式基数排序是基数排序的一种实现方式，它使用链表来存储数据，可以避免基数排序中需要开辟大量空间的问题。下面是C++实现：

#include <iostream>
#include <cstring>

using namespace std;

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

void radixSort(int arr[], int n) {
    // 找到最大值
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    
    // 计算最大值的位数
    int digits = 0;
    while (maxVal) {
        digits++;
        maxVal /= 10;
    }
    
    // 初始化链表数组
    Node **buckets = new Node*[10];
    for (int i = 0; i < 10; i++) {
        buckets[i] = nullptr;
    }
    
    // 按位数排序
    for (int d = 1; d <= digits; d++) {
        // 将数据分配到桶中
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / (int)pow(10, d - 1)) % 10;
            Node *node = new Node{arr[i], nullptr};
            if (buckets[digit] == nullptr) {
                buckets[digit] = node;
            } else {
                Node *p = buckets[digit];
                while (p->next) {
                    p = p->next;
                }
                p->next = node;
            }
        }
        
        // 将桶中的数据合并
        int k = 0;
        for (int i = 0; i < 10; i++) {
            Node *p = buckets[i];
            while (p) {
                arr[k++] = p->data;
                Node *q = p;
                p = p->next;
                delete q;
            }
            buckets[i] = nullptr;
        }
    }
    
    // 释放内存
    delete[] buckets;
}

int main() {
    int arr[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

在该实现中，我们首先找到最大值，并计算出最大值的位数。然后，我们初始化一个链表数组，并对每个数按位数进行桶排序。最后，我们将桶中的数据合并到原数组中，并释放内存。

需要注意的是，在该实现中我们使用了指针和动态内存分配。由于链表节点需要在不同桶之间移动，因此我们需要使用指针来表示链表。同时，由于桶的数量取决于数据中最大的数字，因此我们需要使用动态内存分配来初始化链表数组。