对数组进行排序是不必要且低效的。有一个 QuickSort ( QuickSelect ) 算法的变体，它的平均运行时间为 O(n)；如果你先排序，你会降到 O(n log n)。它实际上是在列表中找到第 n 个最小的项目；对于中位数，您只需使用 n = 列表长度的一半。我们称它为 quickNth (list, n)。
这个概念是要找到第 n 个最小的，选择一个“枢轴”值。（具体如何选择并不重要；如果您知道数据将是完全随机的，您可以选择列表中的第一项。）
将原始列表拆分为三个较小的列表：
- 一个值小于枢轴的值。
- 一个值等于枢轴。
- 一个值大于枢轴的值。
然后你有三种情况：
- “较小的”列表有 >= n 项。在这种情况下，您知道第 n 个最小的在该列表中。返回 quickNth(smaller, n)。
- 较小的列表有 < n 项，但较小且相等的列表的长度总和 >= n 项。在这种情况下，第 n 个等于 "equal" 列表中的任何项目；你完成了。
- n 大于较小且相等的列表的长度之和。在这种情况下，您基本上可以跳过这两个，并相应地调整 n。返回 quickNth（更大，n - 长度（更小） - 长度（等于））。
完毕。
如果您不确定数据是否完全随机，则需要更加复杂地选择枢轴。取列表中第一个值、列表中最后一个值以及两者中间的值的中值效果很好。
如果您对枢轴的选择非常不走运，并且总是选择最小值或最大值作为枢轴，则这需要 O(n^2) 时间；那很糟。但是，如果你用一个像样的算法来选择你的支点，这也是不太可能的。
示例代码：
import java.util.*;
public class Utility {
/****************
* @param coll an ArrayList of Comparable objects
* @return the median of coll
*****************/
public static <T extends Number> double median(ArrayList<T> coll, Comparator<T> comp) {
double result;
int n = coll.size()/2;
if (coll.size() % 2 == 0) // even number of items; find the middle two and average them
result = (nth(coll, n-1, comp).doubleValue() + nth(coll, n, comp).doubleValue()) / 2.0;
else // odd number of items; return the one in the middle
result = nth(coll, n, comp).doubleValue();
return result;
} // median(coll)
/*****************
* @param coll a collection of Comparable objects
* @param n the position of the desired object, using the ordering defined on the list elements
* @return the nth smallest object
*******************/
public static <T> T nth(ArrayList<T> coll, int n, Comparator<T> comp) {
T result, pivot;
ArrayList<T> underPivot = new ArrayList<>(), overPivot = new ArrayList<>(), equalPivot = new ArrayList<>();
// choosing a pivot is a whole topic in itself.
// this implementation uses the simple strategy of grabbing something from the middle of the ArrayList.
pivot = coll.get(n/2);
// split coll into 3 lists based on comparison with the pivot
for (T obj : coll) {
int order = comp.compare(obj, pivot);
if (order < 0) // obj < pivot
underPivot.add(obj);
else if (order > 0) // obj > pivot
overPivot.add(obj);
else // obj = pivot
equalPivot.add(obj);
} // for each obj in coll
// recurse on the appropriate list
if (n < underPivot.size())
result = nth(underPivot, n, comp);
else if (n < underPivot.size() + equalPivot.size()) // equal to pivot; just return it
result = pivot;
else // everything in underPivot and equalPivot is too small. Adjust n accordingly in the recursion.
result = nth(overPivot, n - underPivot.size() - equalPivot.size(), comp);
return result;
} // nth(coll, n)
public static void main (String[] args) {
Comparator<Integer> comp = Comparator.naturalOrder();
Random rnd = new Random();
for (int size = 1; size <= 10; size++) {
ArrayList<Integer> coll = new ArrayList<>(size);
for (int i = 0; i < size; i++)
coll.add(rnd.nextInt(100));
System.out.println("Median of " + coll.toString() + " is " + median(coll, comp));
} // for a range of possible input sizes
} // main(args)
} // Utility