代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
给你一个整数数组 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 * 104-5 * 104 <= nums[i] <= 5 * 104快速排序是一种高效的排序算法。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quick_sort(l, r):
if l >= r:
return
x = nums[randint(l, r)]
i, j, k = l - 1, r + 1, l
while k < j:
if nums[k] < x:
nums[i + 1], nums[k] = nums[k], nums[i + 1]
i, k = i + 1, k + 1
elif nums[k] > x:
j -= 1
nums[j], nums[k] = nums[k], nums[j]
else:
k = k + 1
quick_sort(l, i)
quick_sort(j, r)
quick_sort(0, len(nums) - 1)
return nums
class Solution {
private int[] nums;
public int[] sortArray(int[] nums) {
this.nums = nums;
quikcSort(0, nums.length - 1);
return nums;
}
private void quikcSort(int l, int r) {
if (l >= r) {
return;
}
int x = nums[(l + r) >> 1];
int i = l - 1, j = r + 1;
while (i < j) {
while (nums[++i] < x) {
}
while (nums[--j] > x) {
}
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
quikcSort(l, j);
quikcSort(j + 1, r);
}
}
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
function<void(int, int)> quick_sort = [&](int l, int r) {
if (l >= r) {
return;
}
int i = l - 1, j = r + 1;
int x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x) {
}
while (nums[--j] > x) {
}
if (i < j) {
swap(nums[i], nums[j]);
}
}
quick_sort(l, j);
quick_sort(j + 1, r);
};
quick_sort(0, nums.size() - 1);
return nums;
}
};
func sortArray(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}
func quickSort(nums []int, l, r int) {
if l >= r {
return
}
i, j := l-1, r+1
x := nums[(l+r)>>1]
for i < j {
for {
i++
if nums[i] >= x {
break
}
}
for {
j--
if nums[j] <= x {
break
}
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
quickSort(nums, l, j)
quickSort(nums, j+1, r)
}
function sortArray(nums: number[]): number[] {
function quickSort(l: number, r: number) {
if (l >= r) {
return;
}
let i = l - 1;
let j = r + 1;
const x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
const n = nums.length;
quickSort(0, n - 1);
return nums;
}
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
function quickSort(l, r) {
if (l >= r) {
return;
}
let i = l - 1;
let j = r + 1;
const x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
const n = nums.length;
quickSort(0, n - 1);
return nums;
};
归并排序是一种分治算法，其思想是将待排序的数据序列不断地折半拆分，直到每个数据块只有一个元素为止，然后再按照拆分的顺序将每个数据块两两合并，在合并的过程中进行排序，最终得到一个有序的数据序列。
归并排序是一种稳定的排序算法，时间复杂度为 $O(n \times \log n)$，空间复杂度为 $O(n)$。其中 $n$ 为数组长度。
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge_sort(l, r):
if l >= r:
return
mid = (l + r) >> 1
merge_sort(l, mid)
merge_sort(mid + 1, r)
i, j = l, mid + 1
tmp = []
while i <= mid and j <= r:
if nums[i] <= nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
if i <= mid:
tmp.extend(nums[i : mid + 1])
if j <= r:
tmp.extend(nums[j : r + 1])
for i in range(l, r + 1):
nums[i] = tmp[i - l]
merge_sort(0, len(nums) - 1)
return nums
class Solution {
private int[] nums;
public int[] sortArray(int[] nums) {
this.nums = nums;
quickSort(0, nums.length - 1);
return nums;
}
private void quickSort(int l, int r) {
if (l >= r) {
return;
}
int i = l - 1, j = r + 1, k = l;
int x = nums[(l + r) >> 1];
while (k < j) {
if (nums[k] < x) {
swap(++i, k++);
} else if (nums[k] > x) {
swap(--j, k);
} else {
++k;
}
}
quickSort(l, i);
quickSort(j, r);
}
private void swap(int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
function<void(int, int)> merge_sort = [&](int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
int tmp[r - l + 1];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (i = l; i <= r; ++i) {
nums[i] = tmp[i - l];
}
};
merge_sort(0, nums.size() - 1);
return nums;
}
};
func sortArray(nums []int) []int {
mergeSort(nums, 0, len(nums)-1)
return nums
}
func mergeSort(nums []int, l, r int) {
if l >= r {
return
}
mid := (l + r) >> 1
mergeSort(nums, l, mid)
mergeSort(nums, mid+1, r)
i, j, k := l, mid+1, 0
tmp := make([]int, r-l+1)
for i <= mid && j <= r {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
i++
} else {
tmp[k] = nums[j]
j++
}
k++
}
for ; i <= mid; i++ {
tmp[k] = nums[i]
k++
}
for ; j <= r; j++ {
tmp[k] = nums[j]
k++
}
for i = l; i <= r; i++ {
nums[i] = tmp[i-l]
}
}
function sortArray(nums: number[]): number[] {
function mergetSort(l: number, r: number) {
if (l >= r) {
return;
}
const mid = (l + r) >> 1;
mergetSort(l, mid);
mergetSort(mid + 1, r);
let [i, j, k] = [l, mid + 1, 0];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (i = l, j = 0; i <= r; ++i, ++j) {
nums[i] = tmp[j];
}
}
const n = nums.length;
let tmp = new Array(n).fill(0);
mergetSort(0, n - 1);
return nums;
}
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
function mergetSort(l, r) {
if (l >= r) {
return;
}
const mid = (l + r) >> 1;
mergetSort(l, mid);
mergetSort(mid + 1, r);
let [i, j, k] = [l, mid + 1, 0];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (i = l, j = 0; i <= r; ++i, ++j) {
nums[i] = tmp[j];
}
}
const n = nums.length;
let tmp = new Array(n).fill(0);
mergetSort(0, n - 1);
return nums;
};
class Solution {
private int[] nums;
public int[] sortArray(int[] nums) {
this.nums = nums;
mergeSort(0, nums.length - 1);
return nums;
}
private void mergeSort(int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
mergeSort(l, mid);
mergeSort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
int[] tmp = new int[r - l + 1];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (i = l; i <= r; ++i) {
nums[i] = tmp[i - l];
}
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。