用c➕➕编写代码任务（四）：实现排序算法 实验目的：掌握基数排序算法及其应用。 实验内容(1)：要求编写一个程序,采用基数排序方法将一组英文单词按字典序排列。假设单词均由小写字母或空格构成,最长的单词有MaxLen个字母,用相关数据进行测试并输出各趟的排序结果。要求如上

基数排序是一种非比较型整数排序算法，特别适合处理大量数值的排序。在C++中实现基数排序用于英文单词排序，我们可以先将其转换为整数，然后按照每个位置的数字进行分桶。以下是基本步骤：

1. 首先确定最大单词长度`MaxLen`，并将所有单词转换成等长的数组，通过填充空格。
2. 对每个位置（从最低位到最高位），进行以下操作：
- 分配足够大的桶数组，依据当前位的数字大小。
- 将所有单词分配到对应的桶中。
- 清空原数组，依次取出每桶中最左边的单词放入原数组，完成一轮排序。
3. 重复以上过程直到所有位都排完。

下面是一个简单的示例代码（注意，这只是一个基础框架，实际代码需要处理边界条件、输入输出等细节）：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

// 假设我们已经有一个函数str_to_num用于将单词转换为整数
int str_to_num(const std::string& word) {
    // 实现字符串转数字的具体逻辑
}

void radix_sort(std::vector<std::string>& words, int MaxLen) {
    int exp = 1;
    for (int i = MaxLen; i > 0; --i) {
        std::vector<int> buckets(26); // 假设只有小写字母，用26个桶
        for (std::string& word : words) {
            int digit = str_to_num(word.substr(i - 1, 1));
            buckets[digit + 'a']++; // 根据当前位调整桶中的计数
        }
        
        for (int i = 0; i < 26; ++i) {
            buckets[i] += buckets[i - 1]; // 更新桶的位置
        }

        std::vector<std::string> sorted_words(words.size());
        for (std::string& word : words) {
            int digit = str_to_num(word.substr(i - 1, 1));
            sorted_words[buckets[digit + 'a'] - 1] = word;
            buckets[digit + 'a']--;
        }
        words.swap(sorted_words);
    }
}

int main() {
    std::vector<std::string> words = {"apple", "banana", "cat", "dog", ...}; // 测试数据
    int MaxLen = /* 获取最长单词长度 */;
    
    radix_sort(words, MaxLen);

    // 输出排序后的单词列表
    for (const auto& word : words) {
        std::cout << word << " ";
    }
    std::cout << "\n";

    return 0;
}