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

Question

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

示例：

Input: 451467
Output: 144567

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

int number = 4214;

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

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

不用担心 IO class；这是教授给我们的习俗 class。

Answer 1

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

使用 (digit = number % 10) 获取数字的最后一位
除以最后一位数字（数字/= 10）
遍历数字（没有数字）的数字并检查数字是否最小
如果找到新的更小的数字则替换数字 = 最小的数字并继续寻找直到结束
在循环结束时你找到了最小的数字，存储它 (store = (store * 10) + digit
现在你知道这是最小的数字，从数字中删除这个数字并继续将上述步骤应用于余数，每次找到一个较小的数字然后将它添加到存储中并从数字中删除数字（如果数字重复编号，然后将它们全部删除并添加到存储中）

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

正在调试，知道它是如何对整数进行排序的：

号码的最后一位是：7，号码：451567
子块为 45156
子块为 4515
子块为 451
子块为 45
子块为 4
451567 中的小数位是 1
商店是：1
从 451567
中删除 1 减少的数字是：76554
最后一位数字是：号码的 4：76554
子块为 7655
子块为 765
子块为 76
子块为 7
76554 的小数位是 4
商店是：14
从 76554
中删除 4 减少的数字是：5567
最后一位数字是：号码的 7：5567
子块为 556
子块为 55
子块为 5
5567 中的小数位是 5
商店是：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

示例代码如下：

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

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

你取你要排序的数字的当前位（我们称它为N）
你遍历已排序数字中的所有数字（我们称之为 S）
如果S中的当前数字小于N中的当前数字，则将数字插入S中的当前位置。否则，直接转到S中的下一个数字。

那个版本的算法可以按asc in desc顺序排序，你只需要改变条件。

此外，我建议您看一下所谓的 Radix Sort, the solution here 从基数排序中获取一些想法，我认为基数排序是该解决方案的一般情况。

Answer 3

我假设您可以使用散列。

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

Answer 4

它是 4 行，基于 while 循环的 for 循环变体，带有一点 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 5

我的算法：

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

Answer 6

这是简单的解决方案：

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

Answer 7

由于数字中可能的元素（即数字）是已知的（0 到 9）并且很少（总共 10 个），您可以这样做：

为数字中的每个 0 打印一个 0。
为数字中的每个 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;
        }
    }

Answer 8

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

Answer 9

Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
int length = 0;
long tem = 1;
while (tem <= n) {
    length++;
    tem *= 10;
}

int  last=0;
int [] a=new int[length];
int i=0;
StringBuffer ans=new StringBuffer(4);
while(n!=0){
    last=n%10;
    a[i]=last;               
    n=n/10;
    i++;
}

int l=a.length;
 
for(int j=0;j<l;j++){
    for(int k=j;k<l;k++){
        if(a[k]<a[j]){
            int temp=a[k];
            a[k]=a[j];
            a[j]=temp;
        }
    }
}

for (int j :a) {
   ans= ans.append(j);
}
int add=Integer.parseInt(ans.toString());

System.out.println(add);

对于输入：

n=762941 ------->integer

我们得到输出：

149267      ------->integer

Answer 10

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

Answer 11

import java.util.Scanner;
public class asc_digits
{
    public static void main(String args[]){
    Scanner in= new Scanner(System.in);
    
        System.out.println("number");
        int n=in.nextInt();
        int i, j, p, r;
        for(i=0;i<10;i++)
        {
            p=n;
            while(p!=0)
            {
                r = p%10;
                if(r==i)
                {
                    System.out.print(r);
                }
                p=p/10;
                }
            }
        }
    }

Answer 12

Stream 也可以用于此：

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

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

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

java

sorting

modulo