Java--使10个整数排序程序递归

Question

我有一个简单的问题 - 我需要订购 10 个号码。我有一个想法如何递归地执行此操作:创建一个包含 10 个数字的数组，取这 10 个数字中的最大值，将其从数组中取出，并对剩下的 9 个数字重复相同的函数。问题是我不知道如何实现。我编写了该程序，并且它可以工作，只是它有一个部分一直重复，但是使用新数组，因为您无法更改数组的大小。

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
        int[] sortedArray = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

        Scanner input = new Scanner(System.in);
        int in0 = input.nextInt();
        int in1 = input.nextInt();
        int in2 = input.nextInt();
        int in3 = input.nextInt();
        int in4 = input.nextInt();
        int in5 = input.nextInt();
        int in6 = input.nextInt();
        int in7 = input.nextInt();
        int in8 = input.nextInt();
        int in9 = input.nextInt();

        int[] numArray = new int[]{in0, in1, in2, in3, in4, in5, in6, in7, in8, in9};

        int numArrayLength = numArray.length;
        recursiveSort(numArray);
        for (int i=0;i<numArrayLength;i++) {
            System.out.print(numArray[i]+",");
        }
        sortedArray[0] = numArray[0];
        System.out.println(" ");

        int[] numArray2 = Arrays.copyOfRange(numArray, 1, numArrayLength);
        int numArray2Length = numArray2.length;
        recursiveSort(numArray2);
        for (int j=0;j<numArray2Length;j++) {
            System.out.print(numArray2[j]+",");
        }
        sortedArray[1] = numArray2[0];
        System.out.println(" ");

        int[] numArray3 = Arrays.copyOfRange(numArray2, 1, numArray2Length);
        int numArray3Length = numArray3.length;
        recursiveSort(numArray3);
        for (int k=0;k<numArray3Length;k++) {
            System.out.print(numArray3[k]+",");
        }
        sortedArray[2] = numArray3[0];
        System.out.println(" ");

        int[] numArray4 = Arrays.copyOfRange(numArray3, 1, numArray3Length);
        int numArray4Length = numArray4.length;
        recursiveSort(numArray4);
        for (int k=0;k<numArray4Length;k++) {
            System.out.print(numArray4[k]+",");
        }
        sortedArray[3] = numArray4[0];
        System.out.println(" ");

        int[] numArray5 = Arrays.copyOfRange(numArray4, 1, numArray4Length);
        int numArray5Length = numArray5.length;
        recursiveSort(numArray5);
        for (int k=0;k<numArray5Length;k++) {
            System.out.print(numArray5[k]+",");
        }
        sortedArray[4] = numArray5[0];
        System.out.println(" ");

        int[] numArray6 = Arrays.copyOfRange(numArray5, 1, numArray5Length);
        int numArray6Length = numArray6.length;
        recursiveSort(numArray6);
        for (int k=0;k<numArray6Length;k++) {
            System.out.print(numArray6[k]+",");
        }
        sortedArray[5] = numArray6[0];
        System.out.println(" ");

        int[] numArray7 = Arrays.copyOfRange(numArray6, 1, numArray6Length);
        int numArray7Length = numArray7.length;
        recursiveSort(numArray7);
        for (int k=0;k<numArray7Length;k++) {
            System.out.print(numArray7[k]+",");
        }
        sortedArray[6] = numArray7[0];
        System.out.println(" ");

        int[] numArray8 = Arrays.copyOfRange(numArray7, 1, numArray7Length);
        int numArray8Length = numArray8.length;
        recursiveSort(numArray8);
        for (int k=0;k<numArray8Length;k++) {
            System.out.print(numArray8[k]+",");
        }
        sortedArray[7] = numArray8[0];
        System.out.println(" ");

        int[] numArray9 = Arrays.copyOfRange(numArray8, 1, numArray8Length);
        int numArray9Length = numArray9.length;
        recursiveSort(numArray9);
        for (int k=0;k<numArray9Length;k++) {
            System.out.print(numArray9[k]+",");
        }
        sortedArray[8] = numArray9[0];
        System.out.println(" ");

        int[] numArray10 = Arrays.copyOfRange(numArray9, 1, numArray9Length);
        int numArray10Length = numArray10.length;
        recursiveSort(numArray10);
        for (int k=0;k<numArray10Length;k++) {
            System.out.print(numArray10[k]+",");
        }
        sortedArray[9] = numArray10[0];
        System.out.println(" ");

        sortedArray[2] = numArray3[0];
        for (int dasdasd=0;dasdasd<sortedArray.length;dasdasd++) {
            System.out.print(sortedArray[dasdasd]+",");
        }
    }
    private static int[] recursiveSort(int numArray[]) {
        int numArrayLength = numArray.length;
        int maximum = 0;
        for (int i=0;i<numArrayLength;i++) {
            if (numArray[i] > maximum) {
                maximum = numArray[i];
            }
        }

        int indexOfMaximum = -1;

        for (int j=0;j<numArrayLength;j++) {
            if (numArray[j] == maximum) {
                indexOfMaximum = j;
                break;
            }
        }

        int temporary = numArray[0];
        numArray[0] = numArray[indexOfMaximum];
        numArray[indexOfMaximum] = temporary;
        return numArray;
    }
}

如您所见，

int[] numArray(n) = Arrays.copyOfRange(numArray(n-1), 1, numArray(n-1)Length);
int numArray(n)Length = numArray(n).length;
recursiveSort(numArray(n));
for (int k=0;k<numArray(n)Length;k++) {
    System.out.print(numArray(n)[k]+",");
}
sortedArray[(n-1)] = numArray(n)[0];
System.out.println(" ");

不断重复，因此可能有一个可以很好地工作的递归解决方案。也许我可以使用 ArrayList 做一些事情，因为它们的大小可以改变......

任何帮助将不胜感激!谢谢你!

Answer 1

我建议使用一个递归例程，对仍待排序的部分使用显式起始索引:

private static void recursiveSort(int[] array, int start) {
    if (start < array.length - 1) {
        int maximum = array[start];
        int maximumIndex = start;
        for (int i = start + 1; i < array.length; ++i) {
            if (array[i] > maximum) {
                maximum = array[i];
                maximumIndex = i;
            }
        }
        if (maximumIndex != start) {
            int tmp = array[start];
            array[start] = array[maximumIndex];
            array[maximumIndex] = tmp;
        }
        recursiveSort(array, start + 1);
    }
}

这实际上执行递归(与您的代码不同，它迭代调用名为“recursiveSort”的例程，但根本不是递归的)。整个过程将通过调用来启动:

recursiveSort(numArray, 0);

返回时，数组将按降序排序。

作为一般启发式，当您正在努力解决如何使方法递归时，您应该考虑向该方法添加参数以帮助簿记。