每日一题
912. 排序数组

给你一个整数数组 `nums`，请你将该数组升序排列。



**示例 1：**

```
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
```

**示例 2：**

```
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
```

解法一：快排

时间复杂度：O(nlogn)

空间复杂度：O(1)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand(time(NULL));
quick_sort(nums, 0, nums.size() - 1);
return nums;
}
void quick_sort(vector<int>& arr, int l, int r)
{
if(l >= r) return;
int key = arr[rand() % (r - l + 1) + l];
int left = l - 1, right = r + 1;
for(int i = l; i < right; )
{
if(arr[i] > key) swap(arr[i], arr[--right]);
else if(arr[i] < key) swap(arr[i++], arr[++left]);
else i++;
}
quick_sort(arr, l, left);
quick_sort(arr, right, r);
}
};