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

Question

这里是场景描述。

我有一个整数数组 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

Answer 1

可执行的伪代码（即Python）：thenumbers.sort(key=str)。是的，我知道使用Python有点像作弊——它实在是太强大了;-)。但说真的，这也意味着：如果你可以按词典顺序排序一个字符串数组，就像Python的sort内在地可以做到的那样，那么只需将每个数字制作成“关键字符串”，并对该辅助数组进行排序（然后可以通过str->int转换或通过间接排序索引等方式重建所需的数字数组）；这被称为DSU（Decorate, Sort, Undecorate），并且正是Python的sort实现的key=参数。

更详细地说（伪代码）：

1. 分配一个与numbers数组一样长的char**数组aux
2. 对于从0到numbers-1的每个i，aux[i]=stringify(numbers[i])
3. 分配一个与numbers数组长度相同的int数组indices
4. 对于从0到numbers-1的每个i，indices[i]=i
5. 使用strcmp(aux[i],aux[j])作为cmp(i,j)，对indices进行排序
6. 分配一个与numbers数组长度相同的int数组results
7. 对于从0到numbers-1的每个i，results[i]=numbers[indices[i]]
8. 将results复制到numbers上
9. 释放每个aux[i]，以及aux、indices和results

- Alex Martelli

---

很酷。然而，我正在寻找一种算法，而不是用特定语言实现它的方法。 :) - Skylark

...而且我在“更详细的说明”下列出的1到9步骤不足以成为你所说的“算法”吗？… - Alex Martelli

当我第一次留下评论时，我想只有前两行。 :) 你后来添加了伪代码算法，是吗？ :) 现在，这些步骤很有帮助。谢谢！ - Skylark

Answer 2

既然您提到Java是实际问题中的语言:

您不需要将其转换为字符串，然后再进行排序。相反，定义自己的比较器并在排序中使用它。

具体来说：

Comparator<Integer> lexCompare = new Comparator<Integer>(){
   int compareTo( Integer x, Integer y ) {
      return x.toString().compareTo( y.toString() );
   }
};

然后，您可以像这样对数组进行排序：

int[] array = /* whatever */;
Arrays.sort( array, lexCompare );

（注意：通过自动装箱，int/Integer 不匹配的问题会自动解决。）

- Jason Cohen

Answer 3

实际的排序可以使用任何你喜欢的算法。这个问题的关键在于找到比较函数，以便根据以下方案正确地确定哪些数字应该“小于”其他数字：

bool isLessThan(int a, int b)
{
    string aString = ToString(a);
    string bString = ToString(b);

    int charCount = min(aString.length(), bString.length())
    for (charIndex = 0; charIndex < charCount; charIndex++)
    {
        if (aString[charIndex] < bString[charIndex]) { return TRUE; }
    }

    // if the numbers are of different lengths, but identical
    // for the common digits (e.g. 123 and 12345)
    // the shorter string is considered "less"
    return (aString.length() < bString.length());
}

- e.James

---

那是一个很好的比较，谢谢。如果其他方法都无法解决问题，这个和将批处理转换为字符串，然后进行排序的组合可能是最佳方案。 - Skylark

好的，我会在收到所有回答后决定是否进行批量转换。 - Skylark

批量字符串转换应该会显著改善事情。我不知道是否有比O(n)更好的排序函数，这意味着每个节点都需要多次进行字符串转换。我的比较函数甚至会做两次！考虑到将整数转换为字符串所需的分割数量，如果字符串转换不是瓶颈，我会感到惊讶。 - e.James

Answer 4

我会将它们转换为字符串，然后使用strcmp进行字典序比较排序。

或者，您可以编写一个“lexcmp”函数，使用% 10和/ 10比较两个数字，但这基本上等同于多次调用atoi，因此不是一个好主意。

- Brian Postow

---

您的意思是将整个数组转换为字符串数组，还是在进行比较时进行转换？ - A. Levy

你可以选择将整个数组转换一次，也可以选择不转换。如果不转换，每个数字需要转换多次（log n），这样会很耗费资源。 - Brian Postow

如果您从 CPU 缓存或寄存器（如果您在一个具有寄存器丰富的架构上）读取数据，则对 log n 次进行转换并不昂贵。也许您是正确的，但我遇到过这样的情况：从缓存中的数据执行更多的工作要比预处理数组更好。 - A. Levy

Answer 5

你不需要填充结果。这样做不会改变字典比较的顺序，容易出错，并且会浪费CPU周期。最“空间有效”的方法是在比较时将数字转换为字符串。这样，你就不需要分配额外的数组，数字将在原地进行比较。

只需按需将它们转换为字符串，就可以快速获得相当好的实现。将数字转换为字符串并不特别昂贵，而且由于你一次只处理两个字符串，因此它们很可能始终保留在CPU缓存中。因此，与将整个数组转换为字符串的情况相比，比较将快得多，因为它们不需要从主内存加载到缓存中。人们往往会忘记CPU具有缓存，而那些在小的本地内存区域执行大量工作的算法将从更快的缓存访问中获益匪浅。在某些体系结构上，缓存比内存快得多，您可以在从主内存加载数据所需的时间内对数据执行数百个操作。因此，在比较函数中执行更多的工作实际上可能比预处理数组要快得多。特别是如果您有一个大数组。

尝试在比较器函数中执行字符串序列化和比较，并对其进行基准测试。我认为这将是一个相当好的解决方案。以下是类似Java的伪代码示例：

public static int compare(Number numA, Number numB) {
    return numA.toString().compare(numB.toString());
}

我认为，任何你可以做的花哨的位比较都必须大致相当于将数字转换为字符串所涉及的工作。因此，你可能不会得到显着的好处。你不能直接进行逐位比较，那会给你一个不同于字典排序的顺序。你仍然需要能够找出每个数字的每一位，因此最直接的方法是将它们变成字符串。可能有一些巧妙的技巧，但我脑海中想到的每条路都很棘手、容易出错，而且比它值得的工作要多得多。

- A. Levy

---

作为一个附带说明，这也可能在您使用的编程语言上有很大关系。在 C 语言中，这可能是正确的。在更动态的语言中，调用比较函数的开销可能足以压倒缓存的好处。 - A. Levy

Answer 6

我的建议是，将整数转换为字符串的操作放在比较器代码中而不是批量处理中。虽然从代码角度来看这可能更加优雅，但我认为执行效果会更差，因为每个数字可能会被多次比较。

我倾向于创建一个新数组，其中包含整数和字符串表示（我不确定是否需要为字符串比较填充版本以产生您给出的顺序），按字符串对其进行排序，然后将整数值复制回原始数组。

我想不到一种聪明的数学方法来对此进行排序，因为根据您自己的陈述，您想按字典顺序排序，所以您需要将数字转换为字符串来进行排序。

- Lazarus

Answer 7

伪代码：

sub sort_numbers_lexicographically (array) {
    for 0 <= i < array.length:
        array[i] = munge(array[i]);
    sort(array);  // using usual numeric comparisons
    for 0 <= i < array.length:
        array[i] = unmunge(array[i]);
}

那么，munge和unmunge是什么？

munge根据整数大小而异。例如：

sub munge (4-bit-unsigned-integer n) {
    switch (n):
        case 0:  return 0
        case 1:  return 1
        case 2:  return 8
        case 3:  return 9
        case 4:  return 10
        case 5:  return 11
        case 6:  return 12
        case 7:  return 13
        case 8:  return 14
        case 9:  return 15
        case 10:  return 2
        case 11:  return 3
        case 12:  return 4
        case 13:  return 5
        case 14:  return 6
        case 15:  return 7
}

实际上，munge所做的就是在按字典顺序排序时指定4位整数的顺序。我相信你可以看到这里有一个模式---我不需要使用switch---而且你可以很容易地编写一个处理32位整数的版本。如果你不能立即看到模式，请考虑如何编写5、6和7位整数的版本。

unmunge是munge的反向操作。

因此，你可以避免将任何东西转换为字符串---你不需要任何额外的内存。

- dave4420

Answer 8

如果您想尝试更好的预处理-排序-后处理方法，请注意一个整数最多有10个十进制数字（暂时忽略符号）。

因此，它的二进制编码十进制数据适合64位。将数字0->1、1->2等映射，并使用0作为NUL终止符（以确保“1”小于“10”）。从最小的数字开始，依次将每个数字移位到长整型的顶部。对长整型进行排序，这将按字典顺序输出原始整数。然后通过逐个将数字从每个长整型的顶部移回来进行转换：

uint64_t munge(uint32_t i) {
    uint64_t acc = 0;
    while (i > 0) {
        acc = acc >> 4;
        uint64_t digit = (i % 10) + 1;
        acc += (digit << 60);
        i /= 10;
    }
    return acc;
}

uint32_t demunge(uint64_t l) {
    uint32_t acc = 0;
    while (l > 0) {
        acc *= 10;
        uint32_t digit = (l >> 60) - 1;
        acc += digit;
        l << 4;
    }
}

或者类似的东西。由于Java没有无符号整数，您需要稍微修改一下。它使用了大量的工作内存（输入大小的两倍），但仍然比您的初始方法少。它可能比在比较器中动态转换为字符串更快，但它使用更多的峰值内存。根据GC的情况，它可能会通过更少的总内存运行，并且需要更少的收集。

- Steve Jessop

Answer 9

这个问题没有说明如何处理字典排序中的负整数。之前介绍的基于字符串的方法通常会将负值排在前面;例如，{-123，-345，0，234，78}将保持这个顺序。但是，如果减号应该被忽略，则输出顺序应为{0，-123，234，-345，78}。可以通过一些繁琐的额外测试来调整基于字符串的方法以产生该顺序。

在理论和代码上，使用比较两个整数的公共对数的小数部分的比较器可能更简单。也就是说，它将比较两个数字的以10为底的对数的尾数。基于对数的比较器将根据CPU的浮点性能规格和实现质量而运行得更快或更慢。

本答案末尾显示的Java代码包括两个基于对数的比较器：alogCompare和slogCompare。前者忽略符号，因此将从{ -123，-345，0，234，78 }产生{ 0，-123，234，-345，78 }。

接下来显示的数字组是Java程序生成的输出。

“dar rand” 部分显示了随机数据数组 dar 的生成情况。它从左到右读取，每行 5 个元素。请注意，数组 sar、lara 和 lars 最初是未排序的 dar 的副本。

“dar sort” 部分是通过 Arrays.sort(dar); 排序后的 dar。

“sar lex” 部分显示了使用 Arrays.sort(sar,lexCompare); 进行排序后的数组 sar，其中 lexCompare 类似于 Jason Cohen 的答案中所示的 Comparator。

“lar s log” 部分显示了使用 Arrays.sort(lars,slogCompare); 进行排序后的数组 lars，演示了一种基于对数的方法，该方法与 lexCompare 和其他基于字符串的方法给出相同的顺序。

“lar a log” 部分显示了使用 Arrays.sort(lara,alogCompare); 进行排序后的数组 lara，演示了一种基于对数的方法，该方法忽略负号。

dar rand    -335768    115776     -9576    185484     81528
dar rand      79300         0      3128      4095    -69377
dar rand     -67584      9900    -50568   -162792     70992

dar sort    -335768   -162792    -69377    -67584    -50568
dar sort      -9576         0      3128      4095      9900
dar sort      70992     79300     81528    115776    185484

 sar lex    -162792   -335768    -50568    -67584    -69377
 sar lex      -9576         0    115776    185484      3128
 sar lex       4095     70992     79300     81528      9900

lar s log    -162792   -335768    -50568    -67584    -69377
lar s log      -9576         0    115776    185484      3128
lar s log       4095     70992     79300     81528      9900

lar a log          0    115776   -162792    185484      3128
lar a log    -335768      4095    -50568    -67584    -69377
lar a log      70992     79300     81528     -9576      9900

下面展示了Java代码。

// Code for "How can I sort numbers lexicographically?" - jw - 2 Jul 2014
import java.util.Random;
import java.util.Comparator;
import java.lang.Math;
import java.util.Arrays;
public class lex882954 {
// Comparator from Jason Cohen's answer
    public static Comparator<Integer> lexCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            return x.toString().compareTo( y.toString() );
        }
    };
// Comparator that uses "abs." logarithms of numbers instead of strings
    public static Comparator<Integer> alogCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
            Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
            Double xf=xl-xl.intValue();
            return xf.compareTo(yl-yl.intValue());
        }
    };
// Comparator that uses "signed" logarithms of numbers instead of strings
    public static Comparator<Integer> slogCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
            Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
            Double xf=xl-xl.intValue()+Integer.signum(x);
            return xf.compareTo(yl-yl.intValue()+Integer.signum(y));
        }
    };
// Print array before or after sorting
    public static void printArr(Integer[] ar, int asize, String aname) {
        int j;
        for(j=0; j < asize; ++j) {
            if (j%5==0)
                System.out.printf("%n%8s ", aname);
            System.out.printf(" %9d", ar[j]);
        }
        System.out.println();
    }
// Main Program -- to test comparators
    public static void main(String[] args) {
        int j, dasize=15, hir=99;
        Random rnd = new Random(12345);
        Integer[] dar = new Integer[dasize];
        Integer[] sar = new Integer[dasize];
        Integer[] lara = new Integer[dasize];
        Integer[] lars = new Integer[dasize];

        for(j=0; j < dasize; ++j) {
            lara[j] = lars[j] = sar[j] = dar[j] = rnd.nextInt(hir) * 
                rnd.nextInt(hir) * (rnd.nextInt(hir)-44);
        }
        printArr(dar, dasize, "dar rand");
        Arrays.sort(dar);
        printArr(dar, dasize, "dar sort");
        Arrays.sort(sar, lexCompare);
        printArr(sar, dasize, "sar lex");
        Arrays.sort(lars, slogCompare);
        printArr(lars, dasize, "lar s log");
        Arrays.sort(lara, alogCompare);
        printArr(lara, dasize, "lar a log");
    }
}

- James Waldby - jwpat7

Answer 10

如果所有数字都小于1E+18，您可以将每个数字转换为UINT64，乘以十并加一，然后乘以十，直到它们至少达到1E+19。 然后对这些数字进行排序。 要恢复原始数字，请将每个数字除以十，直到最后一位非零（应该是一），然后再除以十。

- supercat