按数字顺序对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--;
        }
    }
}

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

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

Answer 2

我有一个解决方案，但不完全是一个算法。您所需要做的就是将所有数字转换为字符串并转换为字符串。将它们排序为字符串..

Answer 3

下面是如何使用递归函数来实现它（代码是 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++ 翻译了我的代码 这里：

#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 大于最大值时，它会停止。

Answer 4

我认为如果你将数字转换为字符串，你可以使用字符串比较来对它们进行排序。
您可以使用 anny 排序算法。

“1”＜ “10”＜ “100”＜ “11”...

Answer 5

优化存储数字的方式：使用二进制编码的十进制 (BCD)< /a> 可以简单地访问特定数字的类型。 然后您可以使用当前的算法，Steve Jessop 正确地将其识别为 最高有效数字基数排序。

我尝试将所有数字存储在
每个数字作为一个链接列表
更快的操作，但它会导致
空间复杂度大。

将每个数字存储在链接列表中会以两种不同的方式浪费空间：

1. 数字 (0-9) 仅需要 4 位内存来存储，但您可能会使用 8 到 64 位之间的任何位置。 char 或 short 类型占用 8 位，int 最多可占用 64 位。这比最佳解决方案使用的内存多 2 倍到 16 倍！
2. 链接列表增加了额外的不需要的内存开销。对于每个数字，需要额外的 32 到 64 位来存储下一个链接的内存地址。同样，这会将每个数字所需的内存增加 8 倍到 16 倍。

内存效率更高的解决方案在内存中连续存储 BCD 位数字：

1. BCD 每个数字仅使用 4 位。
2. 将数字存储在连续的内存块中，就像数组一样。这消除了存储内存地址的需要。您不需要链表能够轻松地从中间插入/删除。如果您需要将数字增长到未知长度的能力，还有其他抽象数据类型可以以更少的开销实现这一点。例如，向量。

如果加法/乘法等其他操作不重要，一种选择是分配足够的内存来存储每个 BCD 数字加上一个 BCD 终止符。 BCD 终止符可以是不用于表示 BCD 数字的 4 位的任意组合（如二进制 1111）。不过，以这种方式存储将使其他操作（例如加法和乘法）变得更加棘手。

请注意，这与转换为字符串并按字典顺序对这些字符串进行排序的想法非常相似。整数在计算机内部以二进制（基数 2）形式存储。以 BCD 存储更像是基数 10（实际上是基数 16，但忽略了 6 个组合），而字符串就像基数 256。字符串将使用大约两倍的内存，但已经编写了高效的函数来对字符串进行排序。 BCD 可能需要开发自定义 BCD 类型来满足您的需求。

Answer 6

编辑：我错过了它是一个连续的范围。既然如此，所有谈论对数组进行排序的答案都是错误的（包括你在问题中所说的它就像基数排序的想法），而True Soft的答案是正确的。

就像基数排序，但只是数字以相反的顺序排序

很好看:-) 如果你真的这样做，有趣的是，它被称为 MSD 基数排序。

http://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit_radix_sorts

您可以实施一个非常简单，或者带有很多高科技和大张旗鼓的。在大多数编程语言中，您的特定示例面临着轻微的困难。从整数的自然存储格式中提取十进制数字并不是一个特别快的操作。您可以忽略这一点并查看它最终需要多长时间（推荐），或者您可以通过在排序之前将所有数字转换为十进制字符串来添加更多的宣传。

当然，您不必将其实现为基数排序：您可以使用带有适当比较器的比较排序算法。例如，在 C 中，以下内容适合与 qsort 一起使用（除非我把它搞砸了）：

int lex_compare(void *a, void *b) {
    char a_str[12];  // assuming 32bit int
    char b_str[12];
    sprintf(a_str, "%d", *(int*)a);
    sprintf(b_str, "%d", *(int*)b);
    return strcmp(a_str,b_str);
}

效率不是很高，因为它做了很多重复的工作，但很简单。

Answer 7

如果您不想将它们转换为字符串，但有足够的空间来存储列表的额外副本，我将存储副本中元素的十的最大幂。这可能是使用循环最容易做到的。现在调用您的原始数组 x 和 10 的幂 y。

int findPower(int x) {
   int y = 1;
   while (y * 10 < x) {
      y = y * 10;
   }
   return y;
}

您也可以直接计算它们

y = exp10(floor(log10(x)));

，但我怀疑迭代可能比浮点转换更快。

为了比较第 i 个元素和第 j 个元素，

bool compare(int i, int j) {
  if (y[i] < y[j]) {
    int ti = x[i] * (y[j] / y[i]);
    if (ti == x[j]) {
      return (y[i] < y[j]);  // the compiler will optimize this
    } else {
      return (ti < x[j]);
    }
  } else if (y[i] > y[j]) {
    int tj = x[j] * (y[i] / y[j]);
    if (x[i] == tj) {
      return (y[i] < y[j]);  // the compiler will optimize this
    } else {
      return (x[i] < tj);
    }
  } else {
     return (x[i] < x[j];
  }
}

我们将较小的数字乘以适当的 10 次方，使这两个数字具有位数相等，然后进行比较。如果修改后的两个数字相等，则比较数字长度。

如果您没有空间来存储 y 数组，您可以在每次比较时计算它们。

一般来说，使用预先优化的数字转换例程可能会更好。