algorithm - 按数字顺序对 N 个数字进行排序

Question

给定 N 个数字范围[1 到 100]，按数字顺序对数字进行排序(即)对于数字 1 到 100，排序后的输出将是1 10 100 11 12 13 。 . . 19 2 20 21 ..... 99

这就像基数排序，只是数字的排序顺序与正常基数排序中的顺序相反。

我试图将每个数字中的所有数字存储为链表以加快操作速度，但它会导致很大的空间复杂度。

我需要一个可以解决这个问题的算法。

从所有答案来看，“转换为字符串”是一个选项，但是没有其他方法可以做到这一点吗？还可以给出如上所述的字符串排序算法。

Answer 1

使用您喜欢的任何排序算法，但比较数字作为字符串，而不是数字。这基本上是常规数字的字典排序。这是 C 中的 gnome 排序示例:

#include <stdlib.h>
#include <string.h>

void sort(int* array, int length) {
    int* iter = array;
    char buf1[12], buf2[12];
    while(iter++ < array+length) {
        if(iter == array || (strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0) {
            iter++;
        } else {
            *iter ^= *(iter+1);
            *(iter+1) ^= *iter;
            *iter ^= *(iter+1);
            iter--;
        }
    }
}

当然，这需要非标准的itoa 函数出现在stdlib.h 中。一个更标准的替代方法是使用 sprintf，但这会使代码更加困惑。您最好先将整个数组转换为字符串，然后排序，然后再将其转换回来。

编辑: 作为引用，这里的相关位是 strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0，它取代了 *iter >= *(iter-1)。