Quickselect實施不起作用

Question

我想寫代碼來確定數組中的最小項。我很難過，爲此而苦苦掙扎。根據我大學教科書的算法，從今天起，這看起來是正確的。然而，顯然我做錯了，因爲它給我一個堆棧溢出異常。

我的做法是：

1. 設置樞軸是在開始+（端開始）/ 2（而不是啓動+結束/ 2，以防止溢出）
2. 使用整數在此位置是我比較一切
3. 迭代和交換解決這個支點一切，所以事情進行排序（排序相對於樞軸）樞
4. 如果n ==支點，那麼我想我做
5. 否則，如果我想要4個更小t元素和樞軸爲3，例如，那麼我需要看右側（或左側，如果我想第二小元素）。

-

public static void main(String[] args) { 
    int[] elements = {30, 50, 20, 10}; 
    quickSelect(elements, 3); 
} 

private static int quickSelect(int[] elements2, int k) { 
    return quickSelect(elements2, k, 0, elements2.length - 1); 
} 

private static int quickSelect(int[] elements, int k, int start, int end) { 
    int pivot = start + (end - start)/2; 
    int midpoint = elements[pivot]; 
    int i = start, j = end; 

    while (i < j) { 
     while (elements[i] < midpoint) { 
      i++; 
     } 

     while (elements[j] > midpoint) { 
      j--; 
     } 

     if (i <= j) { 
      int temp = elements[i]; 
      elements[i] = elements[j]; 
      elements[j] = temp; 
      i++; 
      j--; 
     } 
    } 
    // Guessing something's wrong here 
    if (k == pivot) { 
     System.out.println(elements[pivot]); 
     return pivot; 
    } else if (k < pivot) { 
     return quickSelect(elements, k, start, pivot - 1); 
    } else { 
     return quickSelect(elements, k, pivot + 1, end); 
    } 
} 

編輯：請至少懶得評論爲什麼如果你要downvote一個有效的問題。

Answer 1

好吧，我做的第一件事就是重做我的旋轉/分割點。正如T. Claverie指出的那樣，缺點是我使用的支點在技術上並不是技術上的支點，因爲在分區階段元素的位置發生了變化。

我實際上將分區代碼重寫爲它自己的方法，如下所示。這有些不同。

我選擇第一個元素（在開始處）作爲關鍵點，並在此之前創建一個「節」，其中的項小於此關鍵點。然後，我將數據透視表的值與<數據透視表部分的最後一項交換。我將這個最終索引作爲關鍵點返回。

這可以清理更多（創建單獨的交換方法）。

private static int getPivot(int[] elements, int start, int end) { 
    int pivot = start; 
    int lessThan = start; 

    for (int i = start; i <= end; i++) { 
     int currentElement = elements[i]; 
     if (currentElement < elements[pivot]) { 
      lessThan++; 
      int tmp = elements[lessThan]; 
      elements[lessThan] = elements[i]; 
      elements[i] = tmp; 
     } 
    } 
    int tmp = elements[lessThan]; 
    elements[lessThan] = elements[pivot]; 
    elements[pivot] = tmp; 

    return lessThan; 
} 

下面是是調用程序如下：

private static int quickSelect(int[] elements, int k, int start, int end) { 

    int pivot = getPivot(elements, start, end); 

    if (k == (pivot - start + 1)) { 
     System.out.println(elements[pivot]); 
     return pivot; 
    } else if (k < (pivot - start + 1)) { 
     return quickSelect(elements, k, start, pivot - 1); 
    } else { 
     return quickSelect(elements, k - (pivot - start + 1), pivot + 1, end); 
    } 
} 

Answer 2

這不會解決問題，但有幾個問題與您的代碼：

• 如果你不檢查我<末和j>開始在田地，你可能會碰到出在某些情況下邊界
• 您選擇您的數據透視表位於子數組的中間，但沒有任何證據表明它在分區過程中不會改變位置。然後，你檢查與舊的樞軸位置，這顯然不會工作的K ==樞軸

希望這有所幫助。