写出C加加 通过PickPivot 随机从数组中选出三个数并取中间值实现Quick Sort的代码

### 回答1：

C++代码：int pickPivot(int array[], int start, int end)
{
int mid = (start + end) / 2;
int median = array[start] + array[mid] + array[end];
if (median == array[start])
return start;
else if (median == array[mid])
return mid;
else
return end;
}void quickSort(int array[], int start, int end)
{
if (start < end)
{
int pivotIndex = pickPivot(array, start, end);
int middle = partition(array, start, end, pivotIndex); quickSort(array, start, middle - 1);
quickSort(array, middle + 1, end);
}
}

### 回答2：
C++代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

// 交换两个元素的值
void swap(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
}

// 找出中间值作为pivot
int findPivot(int arr[], int low, int high){
    int mid = low + (high - low) / 2;
    if(arr[low] > arr[mid]){
        swap(arr[low], arr[mid]);
    }
    if(arr[low] > arr[high]){
        swap(arr[low], arr[high]);
    }
    if(arr[mid] > arr[high]){
        swap(arr[mid], arr[high]);
    }
    return arr[mid];
}

// 通过Quick Sort排序数组
void quickSort(int arr[], int low, int high){
    if(low >= high){
        return;
    }
    int pivot = findPivot(arr, low, high); // 选取pivot值
    int left = low;
    int right = high;
    while(left <= right){
        while(arr[left] < pivot){ // 从左向右找到第一个大于等于pivot的元素
            left++;
        }
        while(arr[right] > pivot){ // 从右向左找到第一个小于等于pivot的元素
            right--;
        }
        if(left <= right){
            swap(arr[left], arr[right]); // 交换元素
            left++;
            right--;
        }
    }
    quickSort(arr, low, right); // 递归排序左半部分
    quickSort(arr, left, high); // 递归排序右半部分
}

int main(){
    int arr[] = {5, 2, 8, 4, 9, 3, 1, 7, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "原始数组：";
    for(int i=0; i<n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    quickSort(arr, 0, n-1);
    cout << "排序后数组：";
    for(int i=0; i<n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

这段代码实现了通过Quick Sort对数组进行排序。首先在`findPivot()`函数中使用`PickPivot`方法选择中间值作为pivot，然后在`quickSort()`函数中将数组分为两部分，通过交换元素使得左半部分的元素都小于等于pivot，右半部分的元素都大于等于pivot。最后再递归地对左右两部分进行排序。主函数中，我们提供了一个示例数组并输出排序前后的结果。

### 回答3：
下面是使用C++语言通过PickPivot，随机从数组中选出三个数并取中间值实现Quick Sort的代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int partition(int arr[], int low, int high) {
    // 选取中间值作为pivot
    int pivot = arr[low + (high - low) / 2];
    
    while (true) {
        // 从左侧找到第一个大于等于pivot的元素
        while (arr[low] < pivot) {
            low++;
        }
        // 从右侧找到第一个小于等于pivot的元素
        while (arr[high] > pivot) {
            high--;
        }
        // 若low大于等于high，则说明已经完成了一次划分
        if (low >= high) {
            return high;
        }
        // 交换low和high所指向的元素
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
        // 继续划分剩余部分
        low++;
        high--;
    }
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 通过PickPivot随机选取三个数，并取中间值作为pivot
        srand(time(NULL));
        int randomIndex1 = low + rand() % (high - low + 1);
        int randomIndex2 = low + rand() % (high - low + 1);
        int randomIndex3 = low + rand() % (high - low + 1);
        int pivot = (arr[randomIndex1] + arr[randomIndex2] + arr[randomIndex3]) / 3;
        if ((arr[randomIndex1] >= pivot && arr[randomIndex2] <= pivot) || (arr[randomIndex2] >= pivot && arr[randomIndex1] <= pivot)) {
            pivot = arr[randomIndex1];
        }
        else if ((arr[randomIndex3] >= pivot && arr[randomIndex2] <= pivot) || (arr[randomIndex2] >= pivot && arr[randomIndex3] <= pivot)) {
            pivot = arr[randomIndex2];
        }
        else {
            pivot = arr[randomIndex3];
        }
        
        // 进行划分
        int partitionIndex = partition(arr, low, high);
        
        // 分别对划分的左右两部分进行递归排序
        quickSort(arr, low, partitionIndex);
        quickSort(arr, partitionIndex + 1, high);
    }
}

int main() {
    int arr[] = {9, 5, 7, 3, 1, 6, 2, 8, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, n - 1);
    
    cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}

以上代码实现了从数组中通过PickPivot随机选取三个数，并取其中位数作为划分的基准值，然后使用快速排序算法对数组进行排序。运行结果将会输出排序后的数组。

请注意，在C++中，数组的下标从0开始计数。电脑生成的真正随机数通常是利用当前系统的时间作为种子值进行计算的，所以需要使用`srand`和`time`函数来保证每次运行程序所生成的随机数不同。