選擇：中位數

Question

當我被分配到寫算法，從無序組數字的發現K-階數一門功課的中位數。作爲一種方法，已經提出了算法median of medians。

不幸的是，我學嘗試已經失敗。如果有人發現錯誤 - 請糾正我。

private int find(int[] A, int size, int k) { 
    if (size <= 10) { 
     sort(A, 0, size); 
     return A[k]; 
    } else { 
     int[] M = new int[size/5]; 
     for (int i = 0; i < size/5; i++) { 
      sort(A, i*5, (i+1) * 5); 
      M[i] = A[i*5 + 2]; 
     } 

     int m = find(M, M.length, M.length/2); 

     int[] aMinus = new int[size]; 
     int aMinusIndex = 0; 
     int[] aEqual = new int[size]; 
     int aEqualIndex = 0; 
     int[] aPlus = new int[size]; 
     int aPlusIndex = 0; 
     for (int j = 0; j < size; j++) { 
      if (A[j] < m) { 
       aMinus[aMinusIndex++] = A[j]; 
      } else if (A[j] == m) { 
       aEqual[aEqualIndex++] = A[j]; 
      } else { 
       aPlus[aPlusIndex++] = A[j]; 
      } 
     } 

     if (aMinusIndex <= k) { 
      return find(aMinus, aMinusIndex, k); 
     } else if (aMinusIndex + aEqualIndex <= k) { 
      return m; 
     } else { 
      return find(aPlus, aPlusIndex, k - aMinusIndex - aEqualIndex); 
     } 
    } 
} 

private void sort(int[] t, int begin, int end) { //simple insertion sort 
    for (int i = begin; i < end; i++) { 
     int j = i; 
     int element = t[i]; 
     while ((j > begin) && (t[j - 1] > element)) { 
      t[j] = t[j - 1]; 
      j--; 
     } 
     t[j] = element; 
    } 
} 

我跑的測試是把數字{200，199，198，...，1），並得到有序排列的第一個數字。我越來越：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -13 

這是在return A[k]行拋出，因爲遞歸調用，：

return find(aPlus, aPlusIndex, k - aMinusIndex - aEqualIndex); 

Answer 1

我不知道你到底是什麼問題，但你絕對應該不是這樣做：

sort(A, i*5, (i+1) * 5); 

此外，你不應該做這麼多的複製，當你這樣做時你不會獲得任何性能。該算法應該在適當的位置完成。

檢查這個維基百科：Selection algorithm

Answer 2

的遞歸步驟您的分支邏輯是倒退。你試圖找到第k個最小的數，你已經發現有aMinusIndex數小於m，aEqualIndex等於m，並且aPlusIndex大於m。

如果aMinusIndex> = k，而不是aMinusIndex < = k等，則應該在aMinus中搜索。 （通過查看極端情況可以很容易地看到：假設零數小於m，那麼顯然你不應該在空數組中尋找任何東西，但是因爲0 < = k，所以你會這樣）。

Answer 3

我明白，這是家庭作業，讓您的選擇可能會受到限制，但我沒有看到中位數的中位數是如何那麼有用這裏。只需使用標準算法對整個數組進行排序，然後選擇第k個元素。中位數的中位數有助於找到一個非常好的支點。對於長度爲200的數據，您不會節省太多時間。

據我所知，您不能準確地獲得中位數，百分位數或第k個元素，而不能最終排序整個輸入數組。使用子集產生估計值。如果這是錯誤的，我真的很想知道，正如我最近研究的代碼中的數百萬數組中的百分位數！

p.s.這可能是因爲我不完全理解你的代碼...