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

Question

我试图按升序排序任何长度的整数的数字,而不使用字符串,数组或递归.

例:

Input: 451467
Output: 144567

我已经弄清楚如何用模数除法得到整数的每个数字:

int number = 4214;

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

但我不知道如何在没有数组的情况下订购数字.

不要担心IO上课; 这是我们教授给我们的定制课程.

Answer 1

这是4行,基于forwhile循环的循环变体,带有一点java 8 spice:

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)

Answer 2

实际上有一个非常简单的算法,它只使用整数:

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命令中进行排序,您只需要更改条件.

另外,我建议你看一下所谓的Radix Sort,这里的解决方案从基数排序中得到一些想法,我认为基数排序是该解决方案的一般情况.