提示：您可在线编辑运行本教程的实例 - 运行实例，去试试！
计算数组的中位数。
//package com.nowjava;/**来 自 时 代 Java - nowjava.com**/ public class Main { public static void main(String[] argv) throws Exception { double[] v = new double[] { 34.45, 35.45, 36.67, 37.78, 37.0000, 37.1234, 67.2344, 68.34534, 69.87700 }; System.out.println(median(v)); } /** * Computes the median of an array. * If the array contains an even number of elements, * then the mean of the lower and upper medians is returned. */ public static double median(double[] v) { if (v.length == 3) { return median3(copy(v)); } else if (v.length == 5) { return median5(copy(v)); } else if (v.length == 7) { return median7(copy(v)); } else if (v.length % 2 == 1) { // odd return quickSelect(copy(v), false); } else { // even// from 时 代 J a v a - N o w J a v a . c o m double[] tmp = copy(v); double lowerMedian = quickSelect(tmp, false); double upperMedian = quickSelect(tmp, true); return (lowerMedian + upperMedian) / 2.0; } } /** * Computes the median of an array. * If the array contains an even number of elements, * the lower median is returned. */ public static int median(int[] v) { if (v.length == 3) { return median3(copy(v)); } else if (v.length == 5) { return median5(copy(v)); } else if (v.length == 7) { return median7(copy(v)); } else { return quickSelect(copy(v)); } } private static double median3(double[] v) { sortInPlace(v, 0, 1); sortInPlace(v, 1, 2); sortInPlace(v, 0, 1); return v[1]; } private static int median3(int[] v) { sortInPlace(v, 0, 1); sortInPlace(v, 1, 2); sortInPlace(v, 0, 1); return v[1]; } /** * Returns a copy of the array. */ //a call to array.clone() may also work although this is a primitive type. I haven't checked //it even may be faster public static int[] copy(int[] array) { int[] result; result = new int[array.length]; System.arraycopy(array, 0, result, 0, array.length); return result; } /** * Returns a copy of the array. */ //a call to array.clone() may also work although this is a primitive type. I haven't checked //it even may be faster public static long[] copy(long[] array) { long[] result; result = new long[array.length]; System.arraycopy(array, 0, result, 0, array.length); return result; } /** * Returns a copy of the array. */ //a call to array.clone() may also work although this is a primitive type. I haven't checked //it even may be faster public static float[] copy(float[] array) { float[] result; result = new float[array.length]; System.arraycopy(array, 0, result, 0, array.length); return result; } /** * Returns a copy of the array. */ //a call to array.clone() may also work although this is a primitive type. I haven't checked //it even may be faster public static double[] copy(double[] array) { double[] result; result = new double[array.length]; System.arraycopy(array, 0, result, 0, array.length); return result; } /** * Returns a copy of the array. */ public static double[][] copy(double[][] v) { double[][] ans = new double[v.length][]; for (int k = 0; k < v.length; k++) ans[k] = copy(v[k]); return (ans); } /** * Returns a copy of the array. */ public static int[][] copy(int[][] v) { int[][] ans = new int[v.length][]; for (int k = 0; k < v.length; k++) ans[k] = copy(v[k]); return (ans); } private static double median5(double[] v) { sortInPlace(v, 0, 1); sortInPlace(v, 3, 4); sortInPlace(v, 0, 3); sortInPlace(v, 1, 4); sortInPlace(v, 1, 2); sortInPlace(v, 2, 3); sortInPlace(v, 1, 2); return v[2]; } private static int median5(int[] v) { sortInPlace(v, 0, 1); sortInPlace(v, 3, 4); sortInPlace(v, 0, 3); sortInPlace(v, 1, 4); sortInPlace(v, 1, 2); sortInPlace(v, 2, 3); sortInPlace(v, 1, 2); return v[2]; } private static double median7(double[] v) { sortInPlace(v, 0, 5); sortInPlace(v, 0, 3); sortInPlace(v, 1, 6); sortInPlace(v, 2, 4); sortInPlace(v, 0, 1); sortInPlace(v, 3, 5); sortInPlace(v, 2, 6); sortInPlace(v, 2, 3); sortInPlace(v, 3, 6); sortInPlace(v, 4, 5); sortInPlace(v, 1, 4); sortInPlace(v, 1, 3); sortInPlace(v, 3, 4); return v[3]; } private static int median7(int[] v) { sortInPlace(v, 0, 5); sortInPlace(v, 0, 3); sortInPlace(v, 1, 6); sortInPlace(v, 2, 4); sortInPlace(v, 0, 1); sortInPlace(v, 3, 5); sortInPlace(v, 2, 6); sortInPlace(v, 2, 3); sortInPlace(v, 3, 6); sortInPlace(v, 4, 5); sortInPlace(v, 1, 4); sortInPlace(v, 1, 3); sortInPlace(v, 3, 4); return v[3]; } private static double quickSelect(double[] v, boolean upperMedian) { int low = 0, high = v.length - 1; final int median = upperMedian ? high / 2 + 1 : high / 2; int middle, ll, hh; for (;;) { if (high <= low) { /* One element only */ return v[median]; } if (high == low + 1) { /* Two elements only */ if (v[low] > v[high]) swap(v, low, high); return v[median]; } /* Find median of low, middle and high items; swap into position low */ middle = (low + high) / 2; if (v[middle] > v[high]) swap(v, middle, high); if (v[low] > v[high]) swap(v, low, high); if (v[middle] > v[low]) swap(v, middle, low); /* Swap low item (now in position middle) into position (low+1) */ swap(v, middle, low + 1); /* Nibble from each end towards middle, swapping items when stuck */ ll = low + 1; hh = high; for (;;) { do ll++; while (v[low] > v[ll]); do hh--; while (v[hh] > v[low]); if (hh < ll) break; swap(v, ll, hh); } /* Swap middle item (in position low) back into correct position */ swap(v, low, hh); /* Re-set active partition */ if (hh <= median) low = ll; if (hh >= median) high = hh - 1; } } private static int quickSelect(int[] v) { int low = 0, high = v.length - 1; final int median = high / 2; int middle, ll, hh; for (;;) { if (high <= low) { /* One element only */ return v[median]; } if (high == low + 1) { /* Two elements only */ if (v[low] > v[high]) swap(v, low, high); return v[median]; } /* Find median of low, middle and high items; swap into position low */ middle = (low + high) / 2; if (v[middle] > v[high]) swap(v, middle, high); if (v[low] > v[high]) swap(v, low, high); if (v[middle] > v[low]) swap(v, middle, low); /* Swap low item (now in position middle) into position (low+1) */ swap(v, middle, low + 1); /* Nibble from each end towards middle, swapping items when stuck */ ll = low + 1; hh = high; for (;;) { do ll++; while (v[low] > v[ll]); do hh--; while (v[hh] > v[low]); if (hh < ll) break; swap(v, ll, hh); }