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

不斷重複的，因此有可能是一個遞歸的解決方案，將很好地工作。也許我可以使用ArrayLists做些事情，因爲它們的大小可以改變...

任何幫助將不勝感激！ 謝謝！

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

當它返回時，數組將按降序排序。

作爲一般的啓發式方法，當您在如何使方法遞歸時遇到困難時，應該考慮向方法中添加參數以幫助記帳。

Answer 2

這是功課還是您只需要訂購數字？如果你使用ArrayList()而不是array[]，Java有一個簡單的方法來做到這一點。你只需要撥打Collections.sort(yourArrayList);

Answer 3

我建議不要試圖做出自己的排序算法。許多聰明人已經爲你做了這些艱苦的工作。

你試圖實現的「遞歸」排序（又名Ted向你展示如何真正遞歸遞歸的泡泡排序）將會起作用，但它效率非常低。查看排序算法0​​的比較。

下面是您嘗試實現的算法與殼排序相比較的演示，它是可用的最快排序算法之一。我使用的實現取自here。運行它，你會發現shell排序比泡泡排序平均快7到8倍。

public class SortingDemo { 
    // Methods required for Shell sort 
    public static void shellSort(Comparable[] a) { 
     int N = a.length; 
     int h = 1; 
     while (h < N/3) h = 3*h + 1; 

     while (h >= 1) { 
      for (int i = h; i < N; i++) { 
       for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) { 
        exch(a, j, j-h); 
       } 
      } 
      assert isHsorted(a, h); 
      h /= 3; 
     } 
     assert isSorted(a); 
    } 

    private static boolean less(Comparable v, Comparable w) { 
     return (v.compareTo(w) < 0); 
    } 

    private static void exch(Object[] a, int i, int j) { 
     Object swap = a[i]; 
     a[i] = a[j]; 
     a[j] = swap; 
    } 

    private static boolean isSorted(Comparable[] a) { 
     for (int i = 1; i < a.length; i++) 
      if (less(a[i], a[i-1])) return false; 
     return true; 
    } 

    private static boolean isHsorted(Comparable[] a, int h) { 
     for (int i = h; i < a.length; i++) 
      if (less(a[i], a[i-h])) return false; 
     return true; 
    } 

    // Method required for "recursive" sort 
    private static void recursiveSort(Integer[] 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); 
     } 
    } 

    public static void main(String[] args) { 
     int desiredArraySize = 1000; 
     int minSizeOfNumberInArray = 0; 
     int maxSizeOfNumberInArray = 100; 
     Integer[] array = new Integer[desiredArraySize]; // Used Integer instead of int to utilize Comparable interface 
     for(int i = 0; i < array.length; i++) { 
      int randomInt = (int) Math.random() * (maxSizeOfNumberInArray - minSizeOfNumberInArray); 
      array[i] = randomInt; 
     } 

     long startTime = System.nanoTime(); 
     recursiveSort(array, 0); 
     long endTime = System.nanoTime(); 
     long recursiveSortTime = endTime - startTime; 
     System.out.println(String.format("\"Recursive\" sort completed in %d ns", recursiveSortTime)); 

     startTime = System.nanoTime(); 
     shellSort(array); 
     endTime = System.nanoTime(); 
     long shellSortTime = endTime - startTime; 
     System.out.println(String.format("Shell sort completed in %d ns", shellSortTime)); 

     System.out.println(String.format("\"Recursive\" sort took %f times longer", (float)recursiveSortTime/(float)shellSortTime)); 
    } 
} 

Answer 4

在學習編程，既寫自己的排序算法和自己的遞歸算法是鞏固你的東西是如何工作的認識極大鍛鍊。即使有人已經做得更好，也是時間充足的投入。

您注意到重複的模式，並將其與遞歸相關聯。在評估遞歸是否合適時，我鼓勵你用「分而治之」的概念來調整思維過程。如果每個遞歸只解決一個元素，那麼你的堆棧將變得非常深，應該避免。如果你可以將你的問題分成幾乎大塊，並遞歸處理每個塊，那麼遞歸將是一個很好的選擇。否則，循環已經非常適合重複模式。