如何按字典顺序对数字进行排序？

Question

这是场景.

我得到一个整数数组'A'.数组的大小不固定.我应该写的函数可以用一个只有几个整数的数组调用一次,而另一个时间,甚至可能包含数千个整数.另外,每个整数不需要包含相同数量的数字.

我应该对数组中的数字进行"排序",使得结果数组具有以字典方式排序的整数(即,它们基于它们的字符串表示进行排序.这里"123"是123的字符串表示).请注意,输出应仅包含整数,而不是它们的字符串等效项.

例如:如果输入是:

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

那么输出应该是:

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

我的初始方法:我将每个整数转换为其字符串格式,然后在其右侧添加零以使所有整数包含相同数量的数字(这是一个混乱的步骤,因为它涉及跟踪等使得解决方案非常低效)然后做了基数排序.最后,我删除了填充的零,将字符串转换回它们的整数并将它们放入生成的数组中.这是一个非常低效的解决方案.

我一直认为解决方案不需要填充等,并且有一个简单的解决方案,你只需要以某种方式处理数字(一些位处理？)来获得结果.

您能想到的空间最有效的解决方案是什么？浪费时光？

如果你要提供代码,我更喜欢Java或伪代码.但如果这不适合你,任何这样的语言应该没问题.

Answer 1

可执行的伪代码(又名的Python) thenumbers.sort(key=str).是的,我知道使用Python有点像作弊 - 它太强大了;-).但严重的是,这也意味着:如果您可以按字典顺序对字符串数组进行排序,就像Python本身可以排序的那样,那么只需从每个数字中取出"关键字符串"并对该辅助数组进行排序(然后您可以通过以下方式重新构建所需的数字数组) str-> int转换,或通过间接等对索引进行排序等); 这被称为DSU(装饰,排序,未装饰),它是key=Python的排序实现的参数.

更详细(伪代码):

1. aux只要数组就分配一个char**numbers数组
2. 从0到0 length of numbers-1,aux[i]=stringify(numbers[i])
3. 分配一个indices相同长度的int数组
4. 从0到0 length of numbers-1,indices[i]=i
5. 排序indices,使用ascmp(i,j) strcmp(aux[i],aux[j])
6. 分配一个results相同长度的int数组
7. 从0到0 length of numbers-1,results[i]=numbers[indices[i]]
8. memcpy results结束numbers
9. 每一个自由aux[i],而且aux,indices,results

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/ Integermismatch通过自动装箱自动工作)