未排序数组中位数代码的时间复杂度分析及优化咨询

一、当前代码的时间复杂度：O(n²) #

拆解代码里的关键操作：

• 子数组复制：循环执行high-low次，对应O(n)时间（n是子数组长度high-low+1），属于线性开销。
• 冒泡排序：这是代码的核心耗时点。冒泡排序在最坏场景（数组完全逆序）下，需要进行n-1轮遍历，每轮最多执行n-1次比较和交换，总操作数为O(n²)。这部分的增长速度远快于复制操作的O(n)，所以整体时间复杂度由它主导，是O(n²)，并非你以为的O(n)。
• 取中位数：直接访问数组下标，属于O(1)的常数时间操作，不影响整体复杂度。

二、优化方案：用快速选择实现O(n)平均时间复杂度 #

找中位数不需要完全排序数组——我们只需要找到数组中第n/2位的元素（n为子数组长度），快速选择算法就是专门解决这类“第k大/小元素”问题的，能做到平均O(n)的时间复杂度：

快速选择的核心逻辑 #

1. 选一个基准元素（pivot），把数组分成两部分：左边是≤pivot的元素，右边是>pivot的元素。
2. 检查pivot的位置是否等于目标中位数的下标：
   • 相等的话直接返回pivot；
   • 若pivot位置小于目标下标，递归处理右半部分；
   • 若大于，递归处理左半部分。

优化后的代码实现 #

import java.util.Random;

public class MedianFinder {
    private static final Random random = new Random();

    public static int medianElement(int[] array, int low, int high) {
        int subArrayLength = high - low + 1;
        int targetIndex = low + subArrayLength / 2;
        return quickSelect(array, low, high, targetIndex);
    }

    private static int quickSelect(int[] array, int low, int high, int targetIndex) {
        if (low == high) {
            return array[low];
        }

        // 随机选基准，避免极端情况导致的O(n²)最坏复杂度
        int pivotIndex = low + random.nextInt(high - low + 1);
        pivotIndex = partition(array, low, high, pivotIndex);

        if (pivotIndex == targetIndex) {
            return array[pivotIndex];
        } else if (pivotIndex < targetIndex) {
            return quickSelect(array, pivotIndex + 1, high, targetIndex);
        } else {
            return quickSelect(array, low, pivotIndex - 1, targetIndex);
        }
    }

    private static int partition(int[] array, int low, int high, int pivotIndex) {
        int pivotVal = array[pivotIndex];
        // 先把基准移到数组末尾，方便后续划分
        swap(array, pivotIndex, high);
        int storePos = low;

        // 将所有≤基准的元素移到左边
        for (int i = low; i < high; i++) {
            if (array[i] <= pivotVal) {
                swap(array, storePos, i);
                storePos++;
            }
        }
        // 把基准移到它的正确位置
        swap(array, storePos, high);
        return storePos;
    }

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

复杂度说明 #

• 平均时间复杂度：O(n)。每次递归处理的数组长度大致是原数组的一半，总操作数为n + n/2 + n/4 + ... ≈ 2n，属于线性增长。
• 最坏时间复杂度：理论上是O(n²)（极端情况每次选的pivot都是最小/最大元素），但通过随机选择pivot，这种情况的概率极低，实际运行中几乎不会碰到。

严格O(n)最坏复杂度的方案：BFPRT算法 #

如果需要保证最坏情况下也是O(n)，可以使用BFPRT算法。它通过“中位数的中位数”策略选择pivot，确保每次划分都能将数组分成大致均等的两部分，彻底避免O(n²)的最坏情况。不过BFPRT的实现逻辑比快速选择更复杂，一般场景下快速选择已经足够用。

内容的提问来源于stack exchange，提问作者programmer