LeetCode 「中等」912.排序数组
题目描述
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解答
快速排序
Code
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
if (nums.length < 2) return nums;
const left = [], right = [];
const pivot = nums[0];
for (let i = 1; i < nums.length; ++i) {
if (nums[i] < pivot) {
left.push(nums[i]);
} else {
right.push(nums[i]);
}
}
return [...sortArray(left), pivot, ...sortArray(right)];
};
Code
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
var partition = function(nums, left, right) {
const pivot = nums[right];
let i = left;
for (let j = left; j < right; ++j) {
if (nums[j] < pivot) {
[nums[j], nums[i]] = [nums[i], nums[j]];
++i
}
}
[nums[i], nums[right]] = [nums[right], nums[i]];
return i;
};
var quickSort = function(nums, left, right) {
if (left >= right) return;
const pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
};
quickSort(nums, 0, nums.length - 1);
return nums;
};