按数字顺序排序N个数字

Question

给定N数范围Eg [1到100],按数字顺序对数字进行排序(即)对于数字1到100,排序的输出伤口为1 10 100 11 12 13...19 2 20 21 ..... 99

这就像Radix Sort一样,但只是数字按照与正常Radix Sort相反的顺序排序.

我试图将每个数字中的所有数字存储为链接列表,以便更快地操作,但这会导致很大的空间复杂度.

我需要一个有问题的工作算法.

从所有答案中,"转换为字符串"是一种选择,但是没有其他方法可以做到这一点吗？还可以给出如上所述的用于排序字符串的算法.

Answer 1

使用您喜欢的任何排序算法,但将数字作为字符串进行比较,而不是数字.这基本上是常规数字的lexiographic排序.这是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).