给你一个整数数组 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]
提示：
- 1 <= nums.length <= $5 \times 10^4$
- $-5 \times 10^4$ <= nums[i] <= $5 \times 10^4$
解析
使用快速排序（随机选择基准元素避免最坏情况）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| var sortArray = function (nums) {
function quickSort(arr, left, right) {
if (left >= right) return;
const pivotIdx = left + Math.floor(Math.random() * (right - left + 1));
[arr[pivotIdx], arr[right]] = [arr[right], arr[pivotIdx]];
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
quickSort(nums, 0, nums.length - 1);
return nums;
};
|
随机快排平均时间复杂度 O(n log n)，空间复杂度 O(log n)。