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

Question

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

我做了一个算法，可以找到ArrayList的中值，基本上我所做的就是创建一个临时ArrayList，然后使用集合。在那个ArrayList上，我可以很容易地得到中值。问题是，对于较大的文件来说需要花费太长的时间，我正在尝试（运气不佳）找到一种算法的实现，以获得未排序数组（或ArrayList）的中值。

从我在这里读到的，中间值算法的中间值被使用，然后是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
        }

基本上，我试图避免在代码中完全使用< code>Collections.sort()和< code > tempelements . clear()，因此需要找到一种更好的算法来寻找线性时间中的中值。

谢了。

Answer 1

为了补充另一个答案，如果您随机选择每个支点，即“几乎确定”的线性时间，则用于查找中值的“快速选择”具有非常严格的运行时间保证，这意味着当常数c增大时，当n变大时，获得大于cn的运行时间的概率非常快变为0。因此，除非你担心中奖的几率比中奖的可能性还要小，否则在所有的意图和目的中，都有一个常数c，这样你永远不会看到运行时间大于cn，而不管n。

Answer 2

我认为基本的快速选择算法（下面的代码来自这个链接）很容易理解：你选择一个支点，应用快速排序的分区函数，然后看看支点的最终位置，相应地只递归到其中一半。

 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)

与中位数相比，这可能退化为＜code＞O（n^2），但通过随机选择轴心，可以显著降低发生这种情况的可能性，如注释中所述。

如果你对中位数的实现不满意，而你又不完全理解，我建议你这样做。