我的選擇算法有什麼問題？

Question

所以我花了一個星期的時間，並問我的同齡人，但我們無法做到。我按原樣打開它，只是爲了透明。我只想知道我的缺點和錯誤，並理解爲什麼這不起作用。我盡力而爲，追蹤它，但遞歸越深入，我越感到困惑。希望有比我更好的見解的人可以幫助我。

此外，我知道這個代碼不是最好的。我正在採取寶貝步驟，而我只是想在優化之前讓它工作。

我的代碼：

public static int select(int[] array, int left, int right, int k) { 

    if(array.length <= 1) { 
     return array[0]; 
    } 
    double proccessedLength = (right-left)+1; // The part of the array we're working with 
    int numberOfGroups = (int) proccessedLength/5; 
    if(((double)proccessedLength%5) > 0) { 
     numberOfGroups++; 
    } 
    int numberOfRemainders = (int) (proccessedLength%5); 
    int[] mediansOfEachGroup = new int[numberOfGroups]; 

    // Finds the medians of the input array 
    for(int x = 0; x < numberOfGroups; x++) { 
     if((numberOfRemainders > 0) && x==(numberOfGroups-1)) { // Last Remainder group 
      int[] tempArrayForInsertionSorting = new int[numberOfRemainders]; 
      int start=(int) (left+proccessedLength-numberOfRemainders); 
      System.out.println(numberOfRemainders); 
      for(int y=0; y < numberOfRemainders; y++) { 
       tempArrayForInsertionSorting[y] = array[start]; 
       start++; 
      } 
      int[] sortedTempArray = insertionSort(tempArrayForInsertionSorting,tempArrayForInsertionSorting.length-1); 
      if(numberOfRemainders%2 == 0) { 
       mediansOfEachGroup[numberOfGroups-1] = sortedTempArray[(numberOfRemainders/2)-1]; 
      } else { 
       mediansOfEachGroup[numberOfGroups-1] = sortedTempArray[(int)numberOfRemainders/3]; 
      } 
     } else { // Groups of 5 
      int[] tempArrayForInsertionSorting = new int[5]; 
      int start=left+(x*5); 
      for(int y=0; y < 5; y++) { 
       tempArrayForInsertionSorting[y] = array[start]; 
       start++; 
      } 
      int[] sortedTempArray = insertionSort(tempArrayForInsertionSorting,tempArrayForInsertionSorting.length-1); 
      mediansOfEachGroup[x] = sortedTempArray[2]; 
     } 
    } 


    int medianOfMedians = select(mediansOfEachGroup, left, mediansOfEachGroup.length-1, (int) mediansOfEachGroup.length/2); 

    int[] arrayCopyForPartition = new int[array.length]; 
    System.arraycopy(array,0,arrayCopyForPartition,0,array.length); 
    int positionOfMedianOfMedians = partitionForSelect(arrayCopyForPartition, left, right, medianOfMedians); 



    if(positionOfMedianOfMedians == k) { 
     return medianOfMedians; 
    } else if(positionOfMedianOfMedians < k){ 
     return select(array, left, k+1, positionOfMedianOfMedians); 
    } else { 
     return select(array, k, right, positionOfMedianOfMedians-k); 
    } 
} 

public static void insertionSort(int array[], int n) { 
    for (int x = 1; x < n; x++){ 
     int y = x; 
     int temp = array[x]; 
     while ((y > 0) && (array[y-1] > temp)){ 
      array[y] = array[y-1]; 
      y--; 
     } 
     array[y] = temp; 
    } 
} 

public static int partitionForSelect(int anArray[], int left, int right, int pivot) { 
    int x = pivot; 
    int i = left-1; 

    for(int j = left; j < right; j++) { 
     comparisons++; 
     if(anArray[j] <= x) { 
      i = i + 1; 
      int temp = anArray[i]; 
      anArray[i] = anArray[j]; 
      anArray[j] = temp; 
     } 

    } 


    return i+1; 
} 

Answer 1

這是什麼樣的問題，其中unit tests是真正有用的。先寫下你的insertionSort()和partitionForSelect()，當你確定它們正常工作時，請寫select()。對於每種方法，寫一些涵蓋不同情況的測試，從非常小的數組開始，然後使用一些不同的較大的測試用例。

最重要的好處是，當你發現算法中的問題並解決它，你會立刻知道它現在是否打破了一些其他的情況。

另一個有用的是添加asserts檢查invariants和中間結果。