c - O(n) 内对字符串指针数组进行排序的算法

Question

这是我的算法作业，我不知道如何继续。

给定一个包含 m 个字符串的数组 A，其中不同的字符串可能有不同数量的个字符，但数组中所有字符串的字符总数为 n。展示如何在 O(n) 时间内对字符串进行排序。请注意，此处所需的顺序是标准的按字母顺序;例如，a < ab < b。从技术上讲，A 是一个指针数组，每个指针都指向一个字符串(即另一个字符数组)；你可以想想C语言中是如何使用字符串的。另外，我们假设每个字符都可以被视为0到255之间的整数。

Answer 1

由于这是一项作业，我不会提供完整的答案，只是提供一些有关如何进行的想法。

由于字符串可以是任意长度，因此您需要使用 O(n) 排序算法。

其中一种算法是桶排序。

那么我们如何安排可变长度字符串的存储桶呢？

为第一个字符创建 256 个存储桶。让每个桶有一个计数器+一组256个桶用于第二个字符，依此类推。

重要提示:除非需要，否则不要创建任何存储桶集，否则内存消耗将是无限的。让空桶设置为NULL

当我们设置好存储桶系统时。我们如何将单词排序到存储桶系统中？

假设我们有单词是。

第一个字符是Y，所以我们进入顶级存储桶集。该集合为NULL，因此我们创建顶层并选择存储桶'Y'。

下一个字符是e。 Y 下的存储桶集是 NULL，因此我们创建该集并选择存储桶 'e'。

下一个字符是s。 Ye 下的存储桶集是 NULL，因此我们创建该集并选择存储桶 's'。

字符串结束。增加当前存储桶的计数Y->e->s。

请注意，如果您使用unsigned char，任务会更简单，因为这样您可以直接使用该值作为长度为256的数组的索引。

bucket 结构可能如下所示:

typedef struct bucket {
    int count;
    struct bucket *next;  // points to NULL or array of 256 buckets.
} bucket;

时间复杂度:

每个角色的最大工作量是:

字符串结束检查 + NULL 检查 + ((256 个存储桶的数组的分配和初始化(我将使用 calloc 为此)或(增加一个存储桶计数)) + 增加循环变量。

内存使用情况

桶排序的缺点来了。如果您需要很多存储桶，它会使用大量内存，并且此解决方案将使用相当多的内存。