Median in O(n)

quickselect.java

  	public static int median(Vector a, int lo, int hi) {
  		if (lo == hi) {
  			return a.get(lo);
  		}
  		
  		int n = a.size() / 2;
  		
  		for (;;) {
  			int pivotIndex = randomPivot(lo, hi);
  			pivotIndex = partition(a, lo, hi, pivotIndex);
  			
  			if (n == pivotIndex) {
  				return a.get(n);
  			} else if (n < pivotIndex) {
  				hi = pivotIndex - 1;
  			} else {
  				lo = pivotIndex + 1;
  			}
  		}
	}

	private static int partition(Vector a, int left, int right, int pivotIndex) {
		int pivotValue = a.get(pivotIndex);
		a.swap(pivotIndex, right); // move pivot to end
		int storeIndex = left;
		for (int i = left; i < right; i++) {
			if (a.get(i) < pivotValue) {
				a.swap(storeIndex, i);
				storeIndex++;
			}
		}
		a.swap(right, storeIndex); // Move pivot to its final place
		return storeIndex;
	}

	private static int randomPivot(int left, int right) {
		return left + (int) Math.floor(Math.random() * (right - left + 1));
	}