纠错：C++随机快速排序

Question

C++随机快速排序，代码能跑，但是结果不对。

#include <iostream>
#include <vector>
#include <random>

using namespace std;

// 交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数
int partition(vector<int>& arr, int low, int high) {
    // 随机选择一个元素作为基准元素
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, high);
    int pivot = arr[dis(gen)];

    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {8, 45, 0, 30, 49, 16, 20, 20};
    int n = arr.size();

    cout << "排序前的数组：";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    quickSort(arr, 0, n - 1);

    cout << endl << "排序后的数组：";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

输出：

排序前的数组：8 45 0 30 49 16 20 20 
排序后的数组：8 0 16 20 45 20 30 49 

Answer 1

【以下回答由 GPT 生成】

问题：排序结果不正确。

解决方案： 问题出现在随机选择基准元素的部分。当前的代码在每次排序时都会重新生成随机数，导致基准元素的选择不准确。

为了解决这个问题，我们可以在排序开始前生成一个随机数，并将其作为 generateRandomPivot 函数的返回值，然后在 partition 函数中使用它作为基准元素。

下面是修复后的代码：

#include <iostream>
#include <vector>
#include <random>

using namespace std;

// 交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 生成随机基准元素
int generateRandomPivot(int low, int high) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(low, high);
    return dis(gen);
}

// 分区函数
int partition(vector<int>& arr, int low, int high) {
    int pivotIndex = generateRandomPivot(low, high);
    int pivot = arr[pivotIndex];

    swap(&arr[pivotIndex], &arr[high]);

    int i = low;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }

    swap(&arr[i], &arr[high]);
    return i;
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {8, 45, 0, 30, 49, 16, 20, 20};
    int n = arr.size();

    cout << "排序前的数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    quickSort(arr, 0, n - 1);

    cout << "\n排序后的数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

请测试一下这个修复后的代码，看看是否解决了问题。如果还有其他问题，请随时提问。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7769413
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：[C语言、C++]数据结构作业：用双向链表实现折返约瑟夫问题
• 您还可以看一下 王健伟老师的C++语言基础到进阶课程中的 成员函数、对象拷贝、私有成员小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 【C++】红黑树的插入实现中的 右单旋代码实现： 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^