使用在java中實現的中值選擇快速選擇樞軸？

Question

我發現這個代碼在github中的quickselect算法，否則被稱爲order-statistics。此代碼工作正常。

我不明白medianOf3方法，它應該按排序順序排列第一個，中間和最後一個索引。但在調用medianof3方法後輸出數組時實際上不會。 我可以按照這個方法去做，除了最後一次呼叫swap(list, centerIndex, rightIndex - 1);。有人可以解釋爲什麼這被稱爲？

import java.util.Arrays; 



/** 
* This program determines the kth order statistic (the kth smallest number in a 
* list) in O(n) time in the average case and O(n^2) time in the worst case. It 
* achieves this through the Quickselect algorithm. 
* 
* @author John Kurlak <john@kurlak.com> 
* @date 1/17/2013 
*/ 
public class Quickselect { 
    /** 
* Runs the program with an example list. 
* 
* @param args The command-line arguments. 
*/ 
    public static void main(String[] args) { 
     int[] list = { 3, 5, 9, 10, 7, 40, 23, 45, 21, 2 }; 
     int k = 6; 
     int median = medianOf3(list, 0, list.length-1); 
     System.out.println(median); 
     System.out.println("list is "+ Arrays.toString(list)); 
     Integer kthSmallest = quickselect(list, k); 

     if (kthSmallest != null) { 
      System.out.println("The kth smallest element in the list where k=" + k + " is " + kthSmallest + "."); 
     } else { 
      System.out.println("There is no kth smallest element in the list where k=" + k + "."); 
     } 
     System.out.println(Arrays.toString(list)); 
    } 

    /** 
* Determines the kth order statistic for the given list. 
* 
* @param list The list. 
* @param k The k value to use. 
* @return The kth order statistic for the list. 
*/ 
    public static Integer quickselect(int[] list, int k) { 
     return quickselect(list, 0, list.length - 1, k); 
    } 

    /** 
* Recursively determines the kth order statistic for the given list. 
* 
* @param list The list. 
* @param leftIndex The left index of the current sublist. 
* @param rightIndex The right index of the current sublist. 
* @param k The k value to use. 
* @return The kth order statistic for the list. 
*/ 
    public static Integer quickselect(int[] list, int leftIndex, int rightIndex, int k) { 
     // Edge case 
     if (k < 1 || k > list.length) { 
      return null; 
     } 

     // Base case 
     if (leftIndex == rightIndex) { 
      return list[leftIndex]; 
     } 

     // Partition the sublist into two halves 
     int pivotIndex = randomPartition(list, leftIndex, rightIndex); 
     int sizeLeft = pivotIndex - leftIndex + 1; 

     // Perform comparisons and recurse in binary search/quicksort fashion 
     if (sizeLeft == k) { 
      return list[pivotIndex]; 
     } else if (sizeLeft > k) { 
      return quickselect(list, leftIndex, pivotIndex - 1, k); 
     } else { 
      return quickselect(list, pivotIndex + 1, rightIndex, k - sizeLeft); 
     } 
    } 

    /** 
* Randomly partitions a set about a pivot such that the values to the left 
* of the pivot are less than or equal to the pivot and the values to the 
* right of the pivot are greater than the pivot. 
* 
* @param list The list. 
* @param leftIndex The left index of the current sublist. 
* @param rightIndex The right index of the current sublist. 
* @return The index of the pivot. 
*/ 
    public static int randomPartition(int[] list, int leftIndex, int rightIndex) { 
     int pivotIndex = medianOf3(list, leftIndex, rightIndex); 
     int pivotValue = list[pivotIndex]; 
     int storeIndex = leftIndex; 

     swap(list, pivotIndex, rightIndex); 

     for (int i = leftIndex; i < rightIndex; i++) { 
      if (list[i] <= pivotValue) { 
       swap(list, storeIndex, i); 
       storeIndex++; 
      } 
     } 

     swap(list, rightIndex, storeIndex); 

     return storeIndex; 
    } 

    /** 
* Computes the median of the first value, middle value, and last value 
* of a list. Also rearranges the first, middle, and last values of the 
* list to be in sorted order. 
* 
* @param list The list. 
* @param leftIndex The left index of the current sublist. 
* @param rightIndex The right index of the current sublist. 
* @return The index of the median value. 
*/ 
    public static int medianOf3(int[] list, int leftIndex, int rightIndex) { 
     int centerIndex = (leftIndex + rightIndex)/2; 

     if (list[leftIndex] > list[rightIndex]) { 
      swap(list, leftIndex, centerIndex); 
     } 

     if (list[leftIndex] > list[rightIndex]) { 
      swap(list, leftIndex, rightIndex); 
     } 

     if (list[centerIndex] > list[rightIndex]) { 
      swap(list, centerIndex, rightIndex); 
     } 

     swap(list, centerIndex, rightIndex - 1); 

     return rightIndex - 1; 
    } 

    /** 
* Swaps two elements in a list. 
* 
* @param list The list. 
* @param index1 The index of the first element to swap. 
* @param index2 The index of the second element to swap. 
*/ 
    public static void swap(int[] list, int index1, int index2) { 
     int temp = list[index1]; 
     list[index1] = list[index2]; 
     list[index2] = temp; 
    } 
} 

Answer 1

因此，我寫了原始代碼，但我做了一個糟糕的工作，使它可讀。

回想起來，我不認爲這行代碼是必要的，但我認爲這是一個小的優化。如果我們刪除代碼行並返回centerIndex，它似乎沒有任何問題。

不幸的是，它所執行的優化應該被重構爲medianOf3()，並且被轉移到randomPartition()。

本質上，最優化是我們希望在對其進行分區之前儘可能地對子數組進行「部分排序」。原因是：我們的數據排序越多，我們未來的分區選擇就越好，這意味着我們的運行時間將比O（n^2）更接近O（n）。在randomPartition()方法中，我們將樞軸值移動到我們正在查看的子陣列的最右側。這將最右邊的值移動到子陣列的中間。這是不希望的，因爲最右邊的值應該是「較大的值」。我的代碼試圖通過將樞軸索引放置在最右邊的索引旁邊來防止這種情況。然後，當樞軸索引與randomPartition()中最右邊的索引交換時，「較大」的最右邊的值不會移動到子陣列的中間，但會保持在右邊。

Answer 2

功能medianOf3是定義左中位數和右位數的順序。最後聲明

swap(list, centerIndex, rightIndex - 1)

用於實現了幾分以下前提：

然而， 而不是遞歸到雙方，如快速排序，quickselect 只有遞歸到一個端 - 與元素一起它是 搜索。這將平均複雜度從O（n log n）（在 快速排序中）降低到O（n）（在快速選擇中）。

然後算法繼續：

for (int i = leftIndex; i < rightIndex; i++) { 
     if (list[i] <= pivotValue) { 
      swap(list, storeIndex, i); 
      storeIndex++; 
     } 
    } 

爲了

這些值到樞軸的左邊是小於或等於 樞軸和所述值，以該樞紐的權利大於 。