排序技术:示例基数排序

Question

挑战如何做到这点？

对以下内容应用基数排序：

A = {cat,bat,cow,sit,may,why}

Answer 1

要执行基数排序，必须首先了解每个阶段的预期结果。

当您开始基数排序时，将按如下方式分配元素：

{cat,bat,cow,sit,may,why}

在第一次迭代中，我们将从上到下按字母顺序按最后一个字母排序。这将导致：

{cat,bat,sit,cow,may,why}

在下一次迭代中，我们将从上到下，按照字母顺序按倒数第二个字母排序。这将导致：

{cat,bat,may,why,sit,cow}

最后，我们用第一个字母重复这个方法。这将导致您排序的单词：

{bat,cat,cow,may,sit,why}

当你实现的时候，你必须考虑你将要获得的数据。你保证每个字符串的长度都是一样的吗？基数只适用于所有长度都相同的集合。如果不总是这样，您可以考虑允许程序以这样一种方式向字符串添加字符，以使长度相等，并以适当的方式比较字符串。

此外，这种基数排序的运行时将是O(L(n+k))，其中L表示字符串的长度，n表示要排序的字符串的数量。K表示您可以拥有的值的范围。如果您的字符串只使用字符"A“到"D"，那么它将是4。假设您正在计算整个字母表，k将由26表示。

希望这能帮助你更好地理解基数排序。如果您可以自由使用任何算法，我建议您使用您正在使用的语言中内置的任何字母排序算法。