为何快速排序lPartition函数取中间值交换到高位的代码能大幅提升性能

你提到的两行代码是快速排序的基准选择优化逻辑，核心作用是避免普通固定基准快排在特殊数据集下的性能退化，具体原理如下：

核心代码说明 #

int mi = low+(high-low)/2;
swap(arr,high,mi);   

• 第一行代码计算当前待排序区间的中点下标，使用low+(high-low)/2的写法是为了避免low+high超出整数存储范围导致的溢出问题。
• 第二行代码将中点位置的元素交换到区间最右端，相当于把原本固定选右端点作为分区基准的逻辑，修改为选中点作为分区基准。

性能提升的原因 #

普通固定端点基准的快排存在明显的性能短板：当待排序数组为有序、逆序或者接近有序的状态时，每次分区只会把数组拆成1个元素和剩余n-1个元素的两个子区间，此时算法时间复杂度会从平均的O(nlogn)退化为O(n²)，递归深度也会达到*O(n)*级别，不仅运行速度暴跌，还存在栈溢出的风险。
改成中点作为基准之后：

• 对于有序/接近有序的数据集，每次分区都能将数组近似拆分为两个大小相等的子区间，时间复杂度稳定维持在O(nlogn)，递归深度控制在O(logn)，这是性能提升的最主要来源。
• 对于随机分布的数据集，中点基准的分区均匀性也远好于固定端点基准，能有效减少比较和交换的总次数，运行效率也会有稳定的提升。
  这个优化属于快排最经典的基准选择优化方案之一，实现成本极低但收益极高，工业界的快排实现基本都会包含类似的基准选择逻辑。尤其在算法题的测试场景中，通常会包含有序/逆序的极端测试用例，所以这个优化带来的性能提升会表现得格外明显。

完整实现逻辑参考 #

你提供的完整快速排序实现如下：

class Solution {
    public void swap(int[] arr, int i, int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    public void qSort(int[] arr, int low, int high){
        if(low<high){
            int pi = lPartition(arr,low,high);
            qSort(arr,low,pi-1);
            qSort(arr,pi+1,high);
        }
    }
    public Integer lPartition(int[] arr, int low, int high){
        int mi = low+(high-low)/2;
        swap(arr,high,mi);
        int pi = high;
        int i = low-1;
        for(int j=low;j<high;j++){
            if(arr[j]<arr[pi]){
                i++;
                swap(arr,i,j);
            }
        }
        swap(arr,pi,i+1);
        return (i+1);
    }
    public int[] sortArray(int[] arr) {
        qSort(arr,0,arr.length-1);
        return arr;
    }
}

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