快速排序随机化算法c++

快速排序随机化算法是一种改进的快速排序算法，它通过随机选择基准元素来避免最坏情况的发生，从而提高了算法的平均性能。下面是快速排序随机化算法的C++代码实现：

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

void Init_Random(int arr[], int n) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100;
    }
}

void Show_Array(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int Partition(int arr[], int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

void Quick_Sort(int arr[], int left, int right) {
    if (left < right) {
        int pivot_pos = Partition(arr, left, right);
        Quick_Sort(arr, left, pivot_pos - 1);
        Quick_Sort(arr, pivot_pos + 1, right);
    }
}

int main() {
    const int n = 10;
    int arr[n];
    Init_Random(arr, n);
    cout << "Original array:" << endl;
    Show_Array(arr, n);
    Quick_Sort(arr, 0, n - 1);
    cout << "Sorted array:" << endl;
    Show_Array(arr, n);
    return 0;
}