#include <iostream>  
#include <vector>  
#include <cstdlib>  
#include <ctime>  

// 快速排序的分区函数  
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];    // 选择最右边的元素作为枢轴  
    int i = (low - 1);  // 小于枢轴的元素索引  

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

// 快速排序 
void quickSort(std::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);
    }
}

// 生成随机数据集  
std::vector<int> generateRandomArray(int size, int range) {
    std::vector<int> arr(size);
    srand(time(0)); // 初始化随机数生成器  
    for (int i = 0; i < size; ++i) {
        arr[i] = rand() % range; // 生成0到range-1之间的随机整数  
    }
    return arr;
}

// 测试快速排序  
void testQuickSort() {
    const int SIZE = 30;
    const int RANGE = 200;
    std::vector<int> arr = generateRandomArray(SIZE, RANGE);

    // 打印原始数组  
    std::cout << "Original array:" << std::endl;
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 进行快速排序  
    quickSort(arr, 0, SIZE - 1);

    // 打印排序后的数组  
    std::cout << "Sorted array:" << std::endl;
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    testQuickSort();
    return 0;
}