按数字顺序对N个数字进行排序
给定N个数字范围，例如1到100，按数字顺序(即)对数字1到100进行排序，排序后的输出将是1 10 100 11 12 13。。。19 2 20 21.....99
这就像基数排序一样，只是数字的排序顺序与正常基数排序的顺序相反。
我试图将每个数字中的所有数字存储为一个链表，以便更快地操作，但这会导致很大的空间复杂性。
我需要一个有效的算法来解决这个问题。
从所有的答案中，“转换为字符串”是一个选项，但没有其他方法可以做到这一点吗？此外，还可以给出如上所述的字符串排序算法。
回答 6
Stack Overflow用户
发布于 2010-08-01 21:05:36
使用您喜欢的任何排序算法，但将数字作为字符串进行比较，而不是作为数字进行比较。这基本上是对常规数字的词法排序。下面是一个用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--;
}
}
}当然，这要求stdlib.h中存在非标准的itoa函数。一种更标准的替代方法是使用sprintf，但这会使代码变得更加混乱。您最好先将整个数组转换为字符串，然后排序，然后再转换回来。
编辑：供参考，这里相关的位是strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0，它取代了*iter >= *(iter-1)。
Stack Overflow用户
发布于 2010-08-01 21:06:10
我有一个解决方案，但并不完全是一个算法。您所需要做的就是将所有数字转换为字符串，并将它们作为字符串进行排序。
Stack Overflow用户
发布于 2010-08-01 21:34:34
下面是如何使用递归函数(代码是用Java编写的)：
void doOperation(List<Integer> list, int prefix, int minimum, int maximum) {
for (int i = 0; i <= 9; i++) {
int newNumber = prefix * 10 + i;
if (newNumber >= minimum && newNumber <= maximum) {
list.add(newNumber);
}
if (newNumber > 0 && newNumber <= maximum) {
doOperation(list, newNumber, minimum, maximum);
}
}
}你可以这样称呼它：
List<Integer> numberList = new ArrayList<Integer>();
int min=1, max =100;
doOperation(numberList, 0, min, max);
System.out.println(numberList.toString());编辑：
我用C++ here翻译了我的代码
#include <stdio.h>
void doOperation(int list[], int &index, int prefix, int minimum, int maximum) {
for (int i = 0; i <= 9; i++) {
int newNumber = prefix * 10 + i;
if (newNumber >= minimum && newNumber <= maximum) {
list[index++] = newNumber;
}
if (newNumber > 0 && newNumber <= maximum) {
doOperation(list, index, newNumber, minimum, maximum);
}
}
}
int main(void) {
int min=1, max =100;
int* numberList = new int[max-min+1];
int index = 0;
doOperation(numberList, index, 0, min, max);
printf("[");
for(int i=0; i<max-min+1; i++) {
printf("%d ", numberList[i]);
}
printf("]");
return 0;
}基本上，其思想是:对于每个数字(0-9)，如果它在minimum和maximum之间，我将其添加到数组中。然后，我使用这个数字作为前缀调用相同的函数。它执行相同的操作:对于每个数字，它将其添加到前缀(prefix * 10 + i)中，如果它在限制之间，则将其添加到数组中。当newNumber大于maximum时，它会停止。
https://stackoverflow.com/questions/3382103
复制相似问题
腾讯云开发者
