中值快速排序，先从a[leftEnd],a[(leftEnd+rightEnd)/2],a[rightEnd］中挑一个大小适中的元素，以他为支点进行中值快速排序。以此类推，最终序列会变成有序。写出算法思想，c+＋实现，以及第一趟中值快速排序的结果 给定序列：1，4，2，9，0，5

中值快速排序（Median-Of-Three Quick Sort），也称为三数取中快速排序，是一种改进版的快速排序算法。它的基本思想是：

1. **选择基准**：每次从待排序区间的首、中、尾三个位置分别取出一个元素，然后找到这三个元素的中间值作为当前的基准（pivot）。

2. **分区操作**：将数组划分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于等于基准的元素。这个过程通过一趟扫描完成。

3. **递归排序**：对划分出的两个子区间分别应用同样的排序步骤，直到每个子区间只剩下一个元素，整个排序结束。

以下是简单的C++实现：

#include <vector>
using namespace std;

int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[(left + right) / 2]; // 选取中位数作为基准
    while (left <= right) {
        while (arr[left] < pivot) left++; // 找到第一个大于或等于pivot的元素
        while (arr[right] > pivot) right--; // 找到第一个小于或等于pivot的元素
        if (left <= right) { // 如果找到了合适的交换位置
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
    return left; // 返回基准的新位置
}

void quickSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1); // 对左侧子数组排序
        quickSort(arr, pivotIndex + 1, right); // 对右侧子数组排序
    }
}

// 示例
void printArray(const vector<int>& arr) {
    for (int num : arr)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> nums = {1, 4, 2, 9, 0, 5};
    quickSort(nums, 0, nums.size() - 1);
    printArray(nums);
    return 0;
}

**第一趟中值快速排序结果**：
原始序列：1, 4, 2, 9, 0, 5
第一次分区后的结果（假设基准是2）：2, 1, 0, 5, 9, 4

注意：实际运行中，每一步划分后结果都会改变，直到完全排序。但是这里只展示了划分一次的效果。