我该如何按字典顺序排序数字？

Question

我该如何按字典顺序排序数字？

algorithmsortingbig-o

16

这里是场景描述。

我有一个整数数组 A，数组的大小不固定。我需要编写的函数可能会被调用多次，每次传入的整数数量不同，有时可能只有几个，有时甚至可能包含成千上万个整数。此外，每个整数的位数也不必相同。

我需要将数组中的数字“排序”，使得结果数组中的整数按字典顺序排列（即基于它们的字符串表示进行排序。例如，"123" 是 123 的字符串表示）。请注意，输出应仅包含整数，而不是它们的字符串等效项。

例如：如果输入为：

[12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000]

则输出应为：

[1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654]

我的初始思路：我将每个整数转换为其字符串格式，然后添加右侧的零以使所有整数包含相同的位数（这是一步很麻烦的操作，因为它涉及跟踪等内容，使得解决方案非常低效），然后进行基数排序。

最后，我删除了填充的零，将字符串转换回它们的整数形式，并将它们放入结果数组中。这是一种非常低效的解决方案。

我听说这个问题并不需要填充等操作，而且有一种简单的方法可以处理数字（某些位运算？）以获得结果。

您能想到的在空间效率和时间效率上最高效的解决方案是什么？

如果您要提供代码，我更喜欢 Java 或伪代码。但如果不适合您，请使用任何编程语言都可以。

- Skylark

哦，只有在我进行基数排序（希望我没有弄错）时才需要零填充，因为这样更容易。在基数排序中，我只需在迭代过程中检查每个整数的特定位置。如果我使用简单的“strcmp”，我想这将不需要。 - Skylark

实际上，如果你从s[0]开始进行基数排序，则不需要填充。 - Brian Postow

啊..没错，我为什么要这样做呢？ :D 希望我没有忘记什么。 - Skylark

可能会有一些技巧，但是为了达到正确的效果所需付出的努力可能不值得。如果你的目标只是获得一个表现良好的解决方案，请使用比较函数。如果你想要最佳性能，那么你可能需要采用“技巧”。 - A. Levy

取决于你的目标。如果这只是一个有趣的面试问题/谜题，那么当然可以尝试去解决它。但如果这是一个真正需要解决的问题，或者作业任务，我建议直接采用简单明了的方法去解决。 - Brian Postow

显示剩余2条评论

14个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lou Franco · Answer 1

如果你想追求空间效率，我建议在排序的比较函数中完成工作。

int compare(int a, int b) {
   // convert a to string
   // convert b to string
   // return -1 if a < b, 0 if they are equal, 1 if a > b
}

如果速度太慢（肯定比预处理慢），请在某个地方跟踪转换，以便比较函数不必一直执行它们。

- Sinan Ünür · Answer 2

#!/usr/bin/perl

use strict;
use warnings;

my @x = ( 12, 2434, 23, 1, 654, 222, 56, 100000 );

print $_, "\n" for sort @x;

__END__

一些时间...首先，使用空的@x：

C:\Temp> timethis s-empty
TimeThis :  Elapsed Time :  00:00:00.188

现在，有10,000个随机生成的元素：

TimeThis :  Elapsed Time :  00:00:00.219

这包括生成10,000个元素所需的时间，但不包括将它们输出到控制台的时间。输出需要大约一秒钟。

因此，节省一些程序员的时间；-）

- Phil H · Answer 3

一种非常巧妙的方法（使用C语言）是：

生成一个新的数组，其中包含所有转换为浮点数的值
使用尾数（有效数字）位进行比较进行排序

在Java中（来自这里）：

long bits = Double.doubleToLongBits(5894.349580349);

boolean negative = (bits & 0x8000000000000000L) != 0; 
long exponent = bits & 0x7ff0000000000000L >> 52;
long mantissa = bits & 0x000fffffffffffffL;

所以你会在这里对长的mantissa进行排序。

- Igor · Answer 4

可能的优化方案：不要这样做：

我将每个整数转换为其字符串格式，然后添加零到右侧，使所有整数包含相同数量的数字

你可以将每个数字乘以（10^N - log10(number)），其中N是大于任何数字的log10的数字。