【C++算法】44.分治_快排_排序数组-C++ 算法代码：

class Solution 
{
    public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(NULL)); // 使用当前时间作为随机数生成的种子，以确保每次运行程序时 rand() 生成的随机数序列不同。
        qsort(nums, 0, nums.size() - 1); // 调用快速排序函数对数组进行排序
        return nums; // 返回排序后的数组
    }
    // 快排
    void qsort(vector<int>& nums, int l, int r) // 快速排序函数，对数组 nums 的子区间 [l, r] 进行排序
    {
        if(l >= r) return; // 如果子区间的起始索引大于或等于结束索引，则无需排序，直接返回
        // 数组分三块
        int key = getRandom(nums, l, r); // 选择一个随机的基准值 key
        int i = l, left = l - 1, right = r + 1; // 初始化指针 i, left, right
        // 使用三路快排的思路，将数组分为三部分：
        // 1. 小于 key 的部分
        // 2. 等于 key 的部分
        // 3. 大于 key 的部分
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        // [l, left] [left + 1, right - 1] [right, r]
        qsort(nums, l, left); // 递归地对小于 key 的部分进行排序
        qsort(nums, right, r); // 递归地对大于 key 的部分进行排序
    }
    
    int getRandom(vector<int>& nums, int left, int right) // 随机选择一个基准值，用于快速排序
    {
        int r = rand(); // 生成一个随机数
        return nums[r % (right - left + 1) + left]; // 计算随机数在数组中的索引，确保在 [left, right] 范围内
    }
};