Java计算中位数的实现方法

中位数是一个集合中的中间值。把所有数值按照大小排序，把这个序列的数学中间值称为中位数。对于有偶数个数的序列，不存在中间值，此时中位数为中间两个数的平均数。

在Java编程中，计算中位数可以使用以下两种方法：

方法一：暴力计算法

该方法是最直观的计算中位数的方法，但是时间复杂度较高，对于大量数据处理效率并不高。步骤如下：

1. 对集合进行排序；
2. 判断集合的长度，如果是偶数，则中位数为中间两个数的平均值；如果是奇数，则中位数为中间的那个数。

参考代码如下：

import java.util.Arrays;

public class Median {

    public static double getMedian(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        // 判断集合长度为奇偶数
        if (len % 2 == 0) {
            return (nums[len / 2] + nums[len / 2 - 1]) / 2.0;
        } else {
            return nums[len / 2];
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 6, 5, 4};
        int[] nums2 = {2, 3, 1, 6, 5};
        System.out.println(getMedian(nums1)); // 输出 3.5
        System.out.println(getMedian(nums2)); // 输出 3
    }
}

方法二：快速选择算法

快速选择算法（QuickSelect）是一种从无序列表找到第k小元素的选择算法。它类似于快速排序算法：首先在数据集合中任选一个枢轴值（pivot），然后将所有小于枢轴值的元素移动到枢轴值左侧，所有大于枢轴值的元素移动到右侧，接着判断枢轴值所在的位置，如果枢轴值所在的位置为k，则枢轴值为所求的第k小的元素，如果k小于枢轴值所在的位置，则第k小的元素在枢轴值左侧，否则在右侧，递归进行此过程直到达到目标。

参考代码如下：

public class Median2 {

    public static double quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int pivotIdx = partition(nums, left, right, left + (right - left) / 2);
        if (k == pivotIdx) {
            return nums[k];
        } else if (k < pivotIdx) {
            return quickSelect(nums, left, pivotIdx - 1, k);
        } else {
            return quickSelect(nums, pivotIdx + 1, right, k);
        }
    }

    public static int partition(int[] nums, int left, int right, int pivotIdx) {
        int pivotValue = nums[pivotIdx];
        // 将枢轴值移动到队尾
        swap(nums, pivotIdx, right);
        int storeIdx = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIdx, i);
                storeIdx++;
            }
        }
        // 将枢轴值移动到正确的位置
        swap(nums, storeIdx, right);
        return storeIdx;
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static double getMedian(int[] nums) {
        int len = nums.length;
        // 判断集合长度为奇偶数
        if (len % 2 == 0) {
            return (quickSelect(nums, 0, len - 1, len / 2 - 1) + quickSelect(nums, 0, len - 1, len / 2)) / 2.0;
        } else {
            return quickSelect(nums, 0, len - 1, len / 2);
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 6, 5, 4};
        int[] nums2 = {2, 3, 1, 6, 5};
        System.out.println(getMedian(nums1)); // 输出 3.5
        System.out.println(getMedian(nums2)); // 输出 3
    }
}

上述代码中，快速选择算法的时间复杂度是O(n)，相比于暴力计算法能够更快速地计算中位数。