C++快速排序运行结果不稳定，修改代码后正常，求原理说明

原代码的核心缺陷 #

原代码的问题根源在于基准值会在分区过程中被意外修改，逻辑完全失效：

• 原代码中mid = (i + j) / 2存储的是数组中间位置的索引，你初始的基准值是a[mid]，但在循环执行swap(a[i], a[j])时，极有可能把mid位置的元素交换到其他位置，后续循环的while(a[i] < a[mid])、while(a[j] > a[mid])比较的就不再是最初选择的基准值，分区逻辑彻底混乱。
• 混乱的分区逻辑会触发指针越界、分区错误等问题，是否触发bug完全取决于当前排序的数组分布，因此会出现有时结果正确、有时结果错误的现象。

举个简单的复现场景：
当前排序区间为[0,3]，数组元素是[4,3,2,1]，初始mid=1，基准值为a[1]=3。第一次交换a[0]和a[3]后数组变为[1,3,2,4]，第二次交换a[1]和a[2]后数组变为[1,2,3,4]，此时mid位置（索引1）的元素已经变成2，后续所有比较的基准值都从3变成了2，分区完全错误。

修改后代码的修复原理 #

你做的三处修改的核心作用是把基准值提前固化到局部变量中，不受数组元素交换的影响：

• 修改后的mid不再是索引，而是直接存储固定的基准值（这里是左右端点元素的平均值，本质只是选基准的一种策略），后续所有比较都是和这个固定值对比，无论数组怎么交换，基准值都不会变，分区逻辑全程正确。

需要补充说明：你修改后的基准值选择（左右端点平均）不是修复的核心，只要把基准值提前存到局部变量即可，下面的写法和你修改后的版本效果完全一致：

void foo(int* a, int left, int right)
{
    int j = right;
    int i = left;
    // 核心：提前存储基准值，不是存索引
    int pivot = a[(left + right) / 2];
    while (i < j)
    {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j)
        {
            swap(a[i], a[j]); i++; j--;
        }
    }
    if (i < right)
        foo(a, i, right);
    if (left < j) foo(a, left, j);
}

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