使用随机轴点避免最坏情况

#include <iostream>

#include <cstdlib>  // 用于随机数生成

using namespace std;

int arr[100000];

// 改进：使用随机轴点避免最坏情况

int getpivot(int left, int right) {

    // 随机选择轴点 (避免有序数组导致性能下降)

    int random = left + rand() % (right - left + 1);

    swap(arr[left], arr[random]);  // 将随机元素换到最左位置

    int pivot = arr[left];

    while (left < right) {

        // 右指针找第一个小于pivot的元素

        while (arr[right] >= pivot && left < right) right--;

        arr[left] = arr[right];  // 移动到左端

        // 左指针找第一个大于等于pivot的元素

        while (arr[left] < pivot && left < right) left++;

        arr[right] = arr[left];  // 移动到右端

    }

    arr[left] = pivot;  // 轴点归位

    return left;

}

void quicksort(int left, int right) {

    if (left < right) {

        int pivot = getpivot(left, right);

        quicksort(left, pivot - 1);

        quicksort(pivot + 1, right);

    }

}

int main() {

    int n;

    cin >> n;

    for (int i = 0; i < n; i++) {

        cin >> arr[i];

    }

    quicksort(0, n-1);

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    cout << endl;

    return 0;

}