java - 在线性时间内找到未排序数组的中位数？

Question

经过仔细研究和思考，我决定发布这个问题，这是我今天早些时候提出的上一个问题的“续集”。

我制作了一个算法来查找 ArrayList 的中位数，基本上我所做的就是制作一个临时 ArrayList，然后在该 ArrayList 上使用 Collections.sort()，我可以轻松获得中位数。问题是对于较大的文件来说花费的时间太长，而且我正在尝试(没有运气)找到一种算法的实现来获取未排序的数组(或ArrayList)的中位数。

根据我读到的here ，使用 Median of Medians 算法，然后使用 QuickSelect，但我找不到足够容易理解的实际实现。

这是我的代码片段，用于查找大小为 filterSize 的 ArrayList 的中位数:

while(elements.size()-counter >= filterSize){
            for(int i = 0; i<filterSize; i++){
                tempElements.add(this.elements.get(i+counter));
                if(i==filterSize){
                    break;
                }
            }
            
            Collections.sort(tempElements); //Sort tempElements to find median
            outputElements.add(tempElements.get((filterSize-1)/2)); //Add median to an output ArrayList after calculating median index
            
            counter++;
            tempElements.clear(); //Removes all elements from the tempElements and start again
        }

基本上，我试图避免在代码中完全使用Collections.sort()和tempElements.clear()，因此需要找到更好的在线性时间内找到中位数的算法。

谢谢。

Answer 1

我觉得基本的Quickselect算法(来自此链接的以下代码)非常容易理解:您选择一个主元，应用快速排序的分区函数，然后查看该主元结束的位置，相应地仅递归到其中的一半。

 function partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  // Move pivot to end
     storeIndex := left
     for i from left to right-1
         if list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  // Move pivot to its final place
     return storeIndex

  // Returns the n-th smallest element of list within left..right inclusive
  // (i.e. left <= n <= right).
  // The size of the list is not changing with each recursion.
  // Thus, n does not need to be updated with each round.
  function select(list, left, right, n)
     if left = right        // If the list contains only one element,
         return list[left]  // return that element
     pivotIndex  := ...     // select a pivotIndex between left and right,
                            // e.g., left + floor(rand() * (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if n = pivotIndex
         return list[n]
     else if n < pivotIndex
         return select(list, left, pivotIndex - 1, n)
     else
         return select(list, pivotIndex + 1, right, n)

与中位数的中位数相比，这可能会退化为O(n^2)，但您可以通过随机选择主元来显着降低发生这种情况的可能性，如评论中所述。

如果您对您不完全理解的中位数中位数的实现不满意，我建议您采用类似的方法。