求double数组中位数时，先检查是否有序比直接排序效率更高？

首先你当前的实现存在几个逻辑错误，建议先修复再考虑性能优化：

• sortedVals 变量没有声明类型，需要补全为 double[] sortedVals，否则会编译不通过
• 奇数长度数组的中位数计算逻辑错误：一是索引取错，长度为n的奇数数组，中间元素的索引应为n/2而非n/2 -1；二是你额外加了1的操作完全无逻辑依据，仅在连续整数数组的场景下会巧合返回正确结果，非连续数组的计算结果会完全错误
• 没有做空数组、单元素数组的边界校验，输入空数组会直接抛出数组越界异常
• 最后的else分支永远不会触发，整数模2只有0和1两种结果，这段逻辑属于冗余代码

要不要先校验数组有序再排序？ #

完全属于冗余操作。校验数组是否有序的时间复杂度是O(n)，只有当数组本身已经有序的场景下能省下后续O(nlogn)的排序开销，其余场景你不仅要多花O(n)做校验，还要继续花O(nlogn)排序，反而比直接排序性能更差。除非你的业务场景中90%以上的输入都是有序数组，否则完全没必要做这个校验。如果确实有大量有序输入的场景，建议直接拆分两个API，让调用方根据自己的数据情况选择对应方法，比自动校验效率更高。

当前的排序方式是不是推荐方案？ #

不是最优。你用的Arrays.stream(vals).sorted().toArray()有额外的流处理开销，对于基本类型数组来说，直接复制原数组后调用Arrays.sort()性能更好，示例代码：

double[] sortedVals = Arrays.copyOf(vals, vals.length);
Arrays.sort(sortedVals);

有没有更优的实现思路？ #

有两种常见的优化方向，适配不同的业务场景：

• 单次求中位数的场景：不需要全量排序数组，用*快速选择（Quickselect）*算法即可，平均时间复杂度O(n)，远优于排序的O(nlogn)，工业界成熟实现会通过中位数 pivot 选择策略把最坏时间复杂度也优化到O(n)，适合处理大规模无序数组的单次中位数计算
• 数组频繁更新、多次求中位数的场景：用双堆方案，维护一个大顶堆存储数组中较小的一半元素，一个小顶堆存储较大的一半元素，每次插入元素的时间复杂度是O(logn)，取中位数的时间复杂度是O(1)，适合流式数据、高频查询的场景

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