如何在不使用数组的情况下对数字进行排序？

Question

如何在不使用任何数组的情况下找到使用给定数字（例如 485735）的数字可以组成的最大和最小数字？

我正在研究冒泡排序算法（使用数组），我试图弄清楚如何在没有数组的情况下编写算法，但我的问题是计算每个数字的索引

我唯一想到的是计算输入中数字位数的算法（朋友帮我解决了这个问题），但到目前为止，我已经花了 4 天的时间来解决这个问题这是一道有我作业成绩的题目

规则是最小的数字不能从零开始例如：

Input: 3134059 
The largest number is: 9543310
The smallest number is: 1033459

Answer 1

public static void main(String[] args) {

    StringBuilder s = new StringBuilder("4857035");
    char aux;

    for (int i = 0; i < s.length() - 1; i++) {
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) > (s.charAt(j))) {
                aux = s.charAt(i);
                s.setCharAt(i, s.charAt(j));
                s.setCharAt(j, aux);
            }
        }
    }
    //output 0345578

    while (s.charAt(0) == '0') {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                aux = s.charAt(0);
                s.setCharAt(0, s.charAt(i));
                s.setCharAt(i, aux);
                break;
            }
        }
    }
    //output 3045578
}

这是针对最小的数字，对于最大的数字更改 if 语句 ( if (s.charAt(i) < (s.charAt(j))) 上的符号并删除 while 语句。

Answer 2

TL;DR：请参阅 IDEONE 处的以下逻辑演示。

假装这个数字是一个数字数组，例如命名为 d[]，并假设索引 0 是最右边的数字。

冒泡排序会将较高的值移动到较高的索引，因此如果我们保持该逻辑，排序 d 将产生所需的 largestNumber，例如1357924 变为 9754321.

假设你有一个计算 10ⁿ 的方法 pow10(n)，然后你可以在任何索引处得到数字：

d[i] = number / pow10(i) % 10

示例：

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924

d[4] = 1357924 / pow10(4) % 10
     = 1357924 / 10000 % 10
     = 135 % 10
     =   5

在冒泡排序中，如果索引较低的元素较大，则交换相邻元素，因此首先我们需要这两个值。假设我们这样做是为了 i = 3:

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924
i = 3

a = d[i] = d[3] = 7
b = d[i+1] = d[4] = 5

因为 a > b 我们需要交换值。我们可以这样做：

 1357924
-   7000   Clear digit at i=3
-  50000   Clear digit at i=4
=1300924   Value with digits cleared
+  70000   Set digit at i=4
+   5000   Set digit at i=3
=1375924   Value with digits at index 3 and 4 swapped

计算公式为：

number = number - a * pow10(i) - b * pow10(i+1)
                + a * pow10(i+1) + b * pow10(i)

可以重构为：

number += ((a - b) * 10 - (a - b)) * pow10(i)

现在你知道如何使用上面的公式得到 "array element value"，又名 d[i]，以及如何 "swap array elements"，你可以将它写到一个普通的冒泡排序算法中，所以你可以：

largestNumber = sortDigits(number)

您现在已经计算出最大值。要计算最小值，您需要简单地将数字反转，但在此之前，您需要确保 d[0] != 0:

n = largestNumber, i = 0
while (n % 10 == 0) { // locate least non-zero digit
    n /= 10
    i++
}
if (i != 0) {
    // clear least digit and add at index 0
    n = n / 10 * pow10(i + 1) + n % 10
}

示例：

n = 97500
After loop: n = 975, i = 2
n / 10 = 97
            * pow10(i + 1) = 97000
                                   + n % 10 = 97005

现在您可以计算出您需要的其他值：

smallestNumber = reverse(n)

参见例如Java reverse an int value without using array 如何做到这一点。

如何在不使用数组的情况下对数字进行排序？

how can I sorting a number without using array?

java

algorithm

bubble-sort