如何在没有字符串或数组的情况下按升序排序整数数字？ [英] How to sort Integer digits in ascending order without Strings or Arrays?

问题描述

我正在尝试按升序对任意长度的整数进行排序，而不使用字符串，数组或递归。

I'm trying to sort the digits of an integer of any length in ascending order without using Strings, arrays or recursion.

示例：

Input: 451467
Output: 144567

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

I have already figured out how to get each digit of the integer with modulus division:

int number = 4214;

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

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

but I don't know how to order the digits without an array.

不要担心 IO 类;这是我们教授给我们的一个自定义课程。

Don't worry about the IO class; it's a custom class our professor gave us.

推荐答案

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

There's actually a very simple algorithm, that uses only integers:

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 。
这个想法很简单：

it will print out 1123447. The idea is simple:

1. 你取得你想要排序的数字的当前数字（我们称之为N）


2. 你浏览已经排序的数字中的所有数字（我们称之为S）


3. 如果S中的当前数字小于N中的当前数字，只需将数字插入S中的当前位置。否则，您只需转到S中的下一位数。

该版本的算法可以在desc命令的asc中进行排序，你只需要改变条件。

That version of the algorithm can sort in both asc in desc orders, you just have to change the condition.

另外，我建议你看一下所谓的基数排序，解决方案这里从基数排序中获取一些想法，我认为基数排序是该解决方案的一般情况。

Also, I suggest you to take a look at so-called Radix Sort, the solution here takes some ideas from radix sort, and I think the radix sort is the general case for that solution.

这篇关于如何在没有字符串或数组的情况下按升序排序整数数字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！