7

给定一个 N 数字范围，例如 [1 到 100]，按数字顺序对数字进行排序（即）对于数字 1 到 100，排序后的输出缠绕为 1 10 100 11 12 13 。. . 19 2 20 21 ..... 99

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

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

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

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

4

7 回答 7

11

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

于 2010-08-01T13:05:35.837 回答
4

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

于 2010-08-01T13:06:09.503 回答
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大于最大值时停止。

于 2010-08-01T13:34:34.243 回答
2

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

“1” < “10” < “100” < “11” ...

于 2010-08-01T13:06:01.157 回答
2

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

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

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

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

一种更节省内存的解决方案将BCD数字连续存储在内存中：

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

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

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

于 2010-08-01T14:48:46.393 回答
1

编辑：我错过了它是一个连续的范围。在这种情况下，所有关于对数组进行排序的答案都是错误的（包括您在问题中陈述的类似于基数排序的想法），而 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);
}

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

于 2010-08-01T13:14:44.027 回答
1

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

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

您也可以直接计算它们

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

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

为了比较第ith 和jth 元素

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];
  }
}

这里所做的是我们将较小的数字乘以十的适当幂，以使两个数字具有相同的位数，然后将它们进行比较。如果两个修改后的数字相等，则比较数字长度。

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

一般来说，您最好使用预先优化的数字转换例程。

于 2010-08-01T13:47:27.570 回答