如何在没有字符串或数组的情况下按升序对整数数字进行排序？

Question

我试图在不使用字符串、数组或递归的情况下按升序对任意长度的整数的数字进行排序。

例子：

 Input: 451467
Output: 144567

我已经想出如何用模数除法得到整数的每一位：

 int number = 4214;

while (number > 0) {
    IO.println(number % 10);
    number = number / 10;
}

但我不知道如何在没有数组的情况下对数字进行排序。

不要担心 IO 类；这是我们教授给我们的定制课程。

原文由 What 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

实际上有一个非常简单的算法， _只使用整数_：

 int number = 4214173;
int sorted = 0;
int digits = 10;
int sortedDigits = 1;
boolean first = true;

while (number > 0) {
    int digit = number % 10;

    if (!first) {

        int tmp = sorted;
        int toDivide = 1;
        for (int i = 0; i < sortedDigits; i++) {
            int tmpDigit = tmp % 10;
            if (digit >= tmpDigit) {
                sorted = sorted/toDivide*toDivide*10 + digit*toDivide + sorted % toDivide;
                break;
            } else if (i == sortedDigits-1) {
                sorted = digit * digits + sorted;
            }
            tmp /= 10;
            toDivide *= 10;
        }
        digits *= 10;
        sortedDigits += 1;
    } else {
        sorted = digit;
    }

    first = false;
    number = number / 10;
}
System.out.println(sorted);

它将打印出 1123447 。这个想法很简单：

1. 你取你想要排序的数字的当前数字（我们称之为 N）
2. 你遍历已经排序的数字中的所有数字（我们称之为 S）
3. 如果 S 中的当前数字小于 N 中的当前数字，则只需将数字插入 S 中的当前位置。否则，只需转到 S 中的下一个数字。

该算法的版本可以按 asc 和 desc 顺序排序，您只需更改条件即可。

另外，我建议你看看所谓的 Radix Sort ， 这里 的解决方案采用了 radix sort 的一些想法，我认为 radix sort 是该解决方案的一般情况。

原文由 Timofey 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

它是 4 行，基于 while 循环的 for 循环变体，带有一点 java 8 香料：

 int number = 4214;

List<Integer> numbers = new LinkedList<>(); // a LinkedList is not backed by an array
for (int i = number; i > 0; i /= 10)
    numbers.add(i % 10);
numbers.stream().sorted().forEach(System.out::println); // or for you forEach(IO::println)

原文由 Bohemian 发布，翻译遵循 CC BY-SA 3.0 许可协议