如何在不使用字符串或数组的情况下按升序排序整数位数？

Question

我将尝试对任意长度的整数进行升序排列，但不使用字符串、数组或递归。

示例：

Input: 451467
Output: 144567

我已经弄清了如何使用模运算获取整数的每个数字：

int number = 4214;

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

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

不用担心IO类，它是我们教授给我们的自定义类。

- What

---

你可以使用列表吗？如果可以，你可以将数字放入一个列表中，使用“Collections.sort（list）”对其进行排序并输出结果。 - moonlight

抱歉，这不够。 当您发布一道作业问题时，必须展示您自己尝试解决问题的步骤，并说明您遇到的问题。 请阅读[帮助/主题]。 - RealSkeptic

无论如何。值得一试。 - What

看我的回答，我提供了解释、调试输出和完全注释的代码。只需查看调试输出，您就可以了解如何在没有数组、字符串、递归、排序API的情况下对整数进行排序。希望这有所帮助。 - Raf

根据我对问题的理解，提问者希望通过循环纯粹地进行字符操作来解决问题。这类问题是给学生们的，以提高他们对循环和相关主题的理解。例如，我的第一个C编程作业是仅使用加法（+）操作求出x的n次方。我们不允许使用乘法、除法或任何内置函数。我想我和@Timofey的看法一样，即解决方案不使用数组、集合、递归或任何其他内置支持。 - Raf

Answer 1

以下是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

---

我认为作者的意思是他不想使用任何类型的“类似列表”的结构。此外，任务的目的也不清楚：如果他想学习算法，那么我的假设是正确的，因为当Java有实现用于排序大量列表和集合时，任务的意义何在。如果任务的目的是学习Java，那么限制自己根本没有意义。 - Timofey

@tagir - 声明已删除！ - Bohemian

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中的下一个数字。

该算法版本可以按升序或降序排序，您只需更改条件即可。

此外，我建议您看一下所谓的基数排序，此方案借鉴了一些基数排序的思想，而且我认为基数排序是该方案的通用情况。

- Timofey

---

问题要求按升序排列 - Aamir

如果您想按降序获取答案，则应尝试此链接http://stackoverflow.com/questions/22720895/sorting-a-numbers-digits-without-using-an-array，也许@klayveR。 - Aamir

我修改了条件，现在它可以按升序排序。实际上，我的算法可以按任意顺序排序。 - Timofey

Answer 3

我的做法算法如下：

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

- Abbas

Answer 4

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

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

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

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

数字 451567 的最后一位是 7
子块为 45156
子块为 4515
子块为 451
子块为 45
子块为 4
451567 中最小的数字是 1
存储值为：1
从 451567 中删除 1
缩减后的数字为：76554
数字 76554 的最后一位是 4
子块为 7655
子块为 765
子块为 76
子块为 7
76554 中最小的数字是 4
存储值为：14
从 76554 中删除 4
缩减后的数字为：5567
数字 5567 的最后一位是 7
子块为 556
子块为 55
子块为 5
5567 中最小的数字是 5
存储值为：145
从 5567 中删除 5
发现重复的最小数字 5。存储值为：145
将重复的最小数字 5 添加到存储中。更新后的存储值为：1455
缩减后的数字为：76
数字 76 的最后一位是 6
子块为 7
76 中最小的数字是 6
存储值为：14556
从 76 中删除 6
缩减后的数字为：7
数字 7 的最后一位是 7
7 中最小的数字是 7
存储值为：145567
从 7 中删除 7
缩减后的数字为：0
数字 451567 的升序为 145567

示例代码如下：

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

- Raf

Answer 5

我想您可以使用哈希。

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

- tharindu_DG

---

我真的很好奇，你的解决方案中哈希在哪里？ - Timofey

如果你正在使用 HashMap，那么你基本上是在使用数组，但问题的提出者想要一种没有数组的解决方案。因此，TreeMap 的解决方案更为正确 :) - Timofey

@Timofey：哈希桶与数组有很大的不同，而TreeMap内部使用compareTo方法，更可能使用数组结构。 - tharindu_DG

刚刚看了TreeMap的源代码，它使用相互连接的Node对象。关于HashMap你是对的，它使用类似于“动态大小”的数组。但我觉得这个问题应该问OP：是否完全禁止使用Java的Array、List和Set？ - Timofey

Answer 6

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

- Arun Singh

Answer 7

由于数字中可能的元素（即数字）已知且很少（总共10个，从0到9），因此可以执行以下操作：

1. 对于数字中的每个0，打印一个0。
   
2. 对于数字中的每个1，打印一个1。
   

    int number = 451467;

    // the possible elements are known, 0 to 9
    for (int i = 0; i <= 9; i++) {
        int tempNumber = number;

        while (tempNumber > 0) {
            int digit = tempNumber % 10;
            if (digit == i) {
                IO.print(digit);
            }
            tempNumber = tempNumber / 10;
        }
    }

- Raimund Krämer

Answer 8

这里是简单的解决方案：

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

- Pushparaj Dhole

---

如果我需要按降序排序怎么办？ - Lily

@Lily，请将冒泡排序的条件更改为以下内容： if (arr[i] < arr[j]) { int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } - Pushparaj Dhole

Answer 9

import java.util.*;
class EZ
{
public static void main (String args [] )
{
    Scanner sc = new Scanner (System.in);
    System.out.println("Enter the number - ");
    int a=sc.nextInt();
    int b=0;
for (int i=9;i>=0;i--)
{
int c=a;
while (c>0)
{
    int d=c%10;             
    if (d==i)
    {
        b=(b*10)+d;
    }
    c/=10;                
}               
}
System.out.println(b);
}
}

- Apoorv Singh

Answer 10

流也可以用于此：

public static int sortDesc(final int num) {
    List<Integer> collect = Arrays.stream(valueOf(num).chars()
       .map(Character::getNumericValue).toArray()).boxed()
       .sorted(Comparator.reverseOrder()).collect(Collectors.toList());

    return Integer.valueOf(collect.stream()
        .map(i->Integer.toString(i)).collect(Collectors.joining()));
    
}

- Christophe Bédanne