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

How to sort Integer digits in ascending order without Strings or Arrays?

提问by klayveR

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

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

Example:

例子：

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.

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

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

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

采纳答案by Timofey

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);

it will print out 1123447. The idea is simple:

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

1. you take the current digit of the number you want to sort(let's call it N)
2. you go through all digits in already sorted number(let's call it S)
3. if current digit in S is less than current digit in N, you just insert the digit in the current position in S. Otherwise, you just go to the next digit in S.

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

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 heretakes some ideas from radix sort, and I think the radix sort is the general case for that solution.

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

回答by Raf

How to sort a number without use of array, string or sorting api? Well, you can sort a number with following simple steps (if too much to read then see the debugging output below to get an idea of how the sorting is done):

如何在不使用数组、字符串或排序 API 的情况下对数字进行排序？好吧，您可以通过以下简单步骤对数字进行排序（如果阅读太多，请查看下面的调试输出以了解排序是如何完成的）：

1. Get the last digit of the number using (digit = number % 10)
2. Divide number so last digit is gone (number /= 10)
3. Loop through digits of number (that does not have digit) and check if digit is smallest
4. If new smaller digit found then replace the digit = smallest digit and keep looking until end
5. At the end of the loop you have found the smallest digit, store it (store = (store * 10) + digit
6. Now that you know this is smallest digit, remove this digit from number and keep applying the above steps to remainder number and every time a smaller digit is found then add it to the store and remove digit from number (if digit is repeated in number, then remove them all and add them to store)

1. 使用 (digit = number % 10) 获取数字的最后一位
2. 除以最后一位数字（数字/= 10）
3. 循环数字的数字（没有数字）并检查数字是否最小
4. 如果找到新的较小数字，则替换数字 = 最小数字并继续查找直到结束
5. 在循环结束时，您找到了最小的数字，将其存储 (store = (store * 10) + digit
6. 既然您知道这是最小的数字，请从数字中删除该数字并继续将上述步骤应用于余数，每次找到较小的数字时，将其添加到商店并从数字中删除数字（如果数字在数字中重复，然后将它们全部删除并将它们添加到存储中）

I provided a code with two while loops in the main method and one function. The function does nothing but, builds a new integer excluding the digit that is passed to for example I pass the function 451567 and 1 and the function returns me 45567 (in any order, doesn't matter). If this function is passed 451567 and 5 then, it finds both 5 digits in number and add them to store and return number without 5 digits (this avoid extra processing).

我在 main 方法和一个函数中提供了一个带有两个 while 循环的代码。该函数什么都不做，但会构建一个不包括传递给的数字的新整数，例如我传递函数 451567 和 1 并且该函数返回我 45567（以任何顺序，无关紧要）。如果此函数传递 451567 和 5，那么它会找到数字中的 5 位数字并将它们添加到存储和返回数字，而不是 5 位数字（这避免了额外的处理）。

Debugging, to know how it sorts the integer:

调试，了解它如何对整数进行排序：

Last digit is : 7 of number : 451567
Subchunk is 45156
Subchunk is 4515
Subchunk is 451
Subchunk is 45
Subchunk is 4
Smalled digit in 451567 is 1
Store is : 1
Remove 1 from 451567
Reduced number is : 76554
Last digit is : 4 of number : 76554
Subchunk is 7655
Subchunk is 765
Subchunk is 76
Subchunk is 7
Smalled digit in 76554 is 4
Store is : 14
Remove 4 from 76554
Reduced number is : 5567
Last digit is : 7 of number : 5567
Subchunk is 556
Subchunk is 55
Subchunk is 5
Smalled digit in 5567 is 5
Store is : 145
Remove 5 from 5567
Repeated min digit 5 found. Store is : 145
Repeated min digit 5 added to store. Updated store is : 1455
Reduced number is : 76
Last digit is : 6 of number : 76
Subchunk is 7
Smalled digit in 76 is 6
Store is : 14556
Remove 6 from 76
Reduced number is : 7
Last digit is : 7 of number : 7
Smalled digit in 7 is 7
Store is : 145567
Remove 7 from 7
Reduced number is : 0
Ascending order of 451567 is 145567

最后一位数字是：数字的7：451567 子块
是45156 子块
是4515 子块
是451 子块
是45 子块
是4
451567 中的小数字是1
存储是：
1 从451567 中删除1 4 的最后7 位5
减少的
数字是4： ：76554
子块7655
子块765
子块76
子块7
在76554 Smalled位数是4
店铺是：14
从76554除去器4
减少数目是：5567
最后位是：数的7：5567
子块556
的子块是55
子块5
5567 中的小数位是 5
Store is : 145
从 5567 中删除
5 找到重复的最小数字 5。存储为：145
重复的最小数字 5 添加到存储中。更新的存储是：1455
减少的数字是：76
最后一位数字是：数字的 6：76 子块
是 7 76 中的
小数字是 6
存储是：14556
从 76 中删除 6
减少的数字是：7
最后一位数字是：数字的 7：7
7 中的小数字是 7
存储是：145567
从 7 中删除 7
减少的数字是：0
451567 的升序是 145567

The sample code is as follow:

示例代码如下：

//stores our sorted number
     static int store = 0; 

     public static void main(String []args){
        int number = 451567; 
        int original = number; 

        while (number > 0) {
            //digit by digit - get last most digit
            int digit = number % 10;

            System.out.println("Last digit is : " + digit + " of number : " + number); 

            //get the whole number minus the last most digit 
            int temp = number / 10; 

            //loop through number minus the last digit to compare
            while(temp > 0) {
                System.out.println("Subchunk is " + temp); 
                //get the last digit of this sub-number
                int t = temp % 10; 

                //compare and find the lowest
                //for sorting descending change condition to t > digit
                if(t < digit)   
                    digit = t; 

                //divide the number and keep loop until the smallest is found
                temp = temp / 10;
            }
            System.out.println("Smalled digit in " + number  + " is " + digit); 

            //add the smallest digit to store 
            store = (store * 10) + digit; 

            System.out.println("Store is : " + store); 

            //we found the smallest digit, we will remove that from number and find the 
            //next smallest digit and keep doing this until we find all the smallest 
            //digit in sub chunks of number, and keep adding the smallest digits to 
            //store
            number = getReducedNumber(number, digit); 
        }
        System.out.println("Ascending order of " + original + " is " + store); 
     }


     /*
     * A simple method that constructs a new number, excluding the digit that was found
     * to b e smallest and added to the store. The new number gets returned so that 
     * smallest digit in the returned new number be found.
     */
     public static int getReducedNumber(int number, int digit) {
        System.out.println("Remove " + digit + " from " + number); 
        int newNumber = 0; 

        //flag to make sure we do not exclude repeated digits, in case there is 44
        boolean repeatFlag = false; 
        while(number > 0) {
            int t = number % 10; 
            //assume in loop one we found 1 as smallest, then we will not add one to the new number at all
            if(t != digit) {
                newNumber = (newNumber * 10) + t; 
            } else if(t == digit) {
                if(repeatFlag) {
                    System.out.println("Repeated min digit " + t + "found. Store is : " + store);
                    store = (store * 10) + t; 
                    System.out.println("Repeated min digit " + t + "added to store. Updated store is : " + store);
                    //we found another value that is equal to digit, add it straight to store, it is 
                    //guaranteed to be minimum
                } else {
                    //skip the digit because its added to the store, in main method, set flag so 
                    // if there is repeated digit then this method add them directly to store
                    repeatFlag = true; 
                }
            }
            number /= 10; 
        }
        System.out.println("Reduced number is : " + newNumber); 
        return newNumber; 
     }
}

回答by tharindu_DG

I assume you're allowed to use hashing.

我假设您可以使用散列。

public static void sortDigits(int x) {
    Map<Integer, Integer> digitCounts = new HashMap<>();

    while (x > 0) {
        int digit = x % 10;
        Integer currentCount = digitCounts.get(digit);
        if (currentCount == null) {
            currentCount = 0;
        }
        digitCounts.put(x % 10, currentCount + 1);
        x = x / 10;
    }

    for (int i = 0; i < 10; i++) {
        Integer count = digitCounts.get(i);
        if (count == null) {
            continue;
        }
        for (int j = 0; j < digitCounts.get(i); j++) {
            System.out.print(i);
        }
    }
}

回答by Bohemian

It's 4 lines, based on a forloop variant of your while loop with a little java 8 spice:

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

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)

回答by Abbas

My algorithm of doing it:

我的算法：

int ascending(int a)
{
    int b = a;
    int i = 1;
    int length = (int)Math.log10(a) + 1;   // getting the number of digits
    for (int j = 0; j < length - 1; j++)
    {
        b = a;
        i = 1;
        while (b > 9)
        { 
            int s = b % 10;                // getting the last digit
            int r = (b % 100) / 10;        // getting the second last digit
            if (s < r)
            {
                a = a + s * i * 10 - s * i - r * i * 10 + r * i; // switching the digits
            }
            b = a;
            i = i * 10;
            b = b / i;                     // removing the last digit from the number
        }
    }
    return a;
}

回答by Pushparaj Dhole

Here is the simple solution :

这是简单的解决方案：

    public class SortDigits
    {
        public static void main(String[] args)
        {
            sortDigits(3413657);
        }

        public static void sortDigits(int num)
        {
            System.out.println("Number  : " + num);
            String number = Integer.toString(num);
            int len = number.length(); // get length of the number
            int[] digits = new int[len];
            int i = 0;
            while (num != 0)
            {
                int digit = num % 10;
                digits[i++] = digit; // get all the digits
                num = num / 10;
            }
            System.out.println("Digit before sorting: ");
            for (int j : digits)
            {
                System.out.print(j + ",");
            }
            sort(digits);
            System.out.println("\nDigit After sorting: ");
            for (int j : digits)
            {
                System.out.print(j + ",");
            }
        }
        //simple bubble sort 
        public static void sort(int[] arr)
        {
            for (int i = 0; i < arr.length - 1; i++)
                for (int j = i + 1; j < arr.length; j++)
                {
                    if (arr[i] > arr[j])
                    {
                        int tmp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = tmp;
                    }
                }
        }
    }

回答by Raimund Kr?mer

Adding a very simple algorithm that does not need any datastructures or fancy math, as the others do.

添加一个非常简单的算法，它不需要任何数据结构或花哨的数学，就像其他算法一样。

int number = 65356;
for (int i = 0; i <= 9; i++) { // the possible elements are known, 0 to 9
    int tempNumber = number;
    while (tempNumber > 0) {
        int digit = tempNumber % 10;
        IO.print(digit);
        tempNumber = number / 10;
    }
}

In words:
1. Print a 0 for every 0 in the number.
2. Print a 1 for every 1 in the number.
...

用文字表示：
1. 为数字中的每一个 0 打印一个 0。
2. 为数字中的每 1 打印一个 1。
...

回答by Arun Singh

class SortDigits {
    public static void main(String[] args) {
        int inp=57437821;
        int len=Integer.toString(inp).length();
        int[] arr=new int[len];
        for(int i=0;i<len;i++)
        {
            arr[i]=inp%10;
            inp=inp/10;
        }
        Arrays.sort(arr);
        int num=0;
        for(int i=0;i<len;i++)
        {
            num=(num*10)+arr[i];
        }
        System.out.println(num);
    }    
}