给你一个整数数组 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(nlogn)。
快速排序：
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quick_sort(nums, left, right):
if left >= right:
return
i, j = left - 1, right + 1
x = nums[(left + right) >> 1]
while i < j:
while 1:
i += 1
if nums[i] >= x:
break
while 1:
j -= 1
if nums[j] <= x:
break
if i < j:
nums[i], nums[j] = nums[j], nums[i]
quick_sort(nums, left, j)
quick_sort(nums, j + 1, right)
quick_sort(nums, 0, len(nums) - 1)
return nums归并排序：
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge_sort(nums, left, right):
if left >= right:
return
mid = (left + right) >> 1
merge_sort(nums, left, mid)
merge_sort(nums, mid + 1, right)
i, j = left, mid + 1
tmp = []
while i <= mid and j <= right:
if nums[i] <= nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
while i <= mid:
tmp.append(nums[i])
i += 1
while j <= right:
tmp.append(nums[j])
j += 1
for i in range(left, right + 1):
nums[i] = tmp[i - left]
merge_sort(nums, 0, len(nums) - 1)
return nums快速排序：
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int i = left - 1, j = right + 1;
int x = nums[(left + right) >> 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;
}
}
quickSort(nums, left, j);
quickSort(nums, j + 1, right);
}
}归并排序：
class Solution {
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
int i = left, j = mid + 1, k = 0;
int[] tmp = new int[right - left + 1];
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
for (i = left; i <= right; ++i) {
nums[i] = tmp[i - left];
}
}
}快速排序：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
quick_sort(nums, 0, nums.size() - 1);
return nums;
}
void quick_sort(vector<int>& nums, int left, int right) {
if (left >= right) return;
int i = left - 1, j = right + 1;
int x = nums[left + right >> 1];
while (i < j) {
while (nums[++i] < x)
;
while (nums[--j] > x)
;
if (i < j) swap(nums[i], nums[j]);
}
quick_sort(nums, left, j);
quick_sort(nums, j + 1, right);
}
};归并排序：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
merge_sort(nums, 0, nums.size() - 1);
return nums;
}
void merge_sort(vector<int>& nums, int left, int right) {
if (left >= right) return;
int mid = left + right >> 1;
merge_sort(nums, left, mid);
merge_sort(nums, mid + 1, right);
int i = left, j = mid + 1, k = 0;
vector<int> tmp(right - left + 1);
while (i <= mid && j <= right)
{
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= right) tmp[k++] = nums[j++];
for (i = left; i <= right; ++i) nums[i] = tmp[i - left];
}
};快速排序：
func sortArray(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}
func quickSort(nums []int, left, right int) {
if left >= right {
return
}
i, j := left-1, right+1
x := nums[(left+right)>>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, left, j)
quickSort(nums, j+1, right)
}归并排序：
func sortArray(nums []int) []int {
mergeSort(nums, 0, len(nums)-1)
return nums
}
func mergeSort(nums []int, left, right int) {
if left >= right {
return
}
mid := (left + right) >> 1
mergeSort(nums, left, mid)
mergeSort(nums, mid+1, right)
i, j, k := left, mid+1, 0
tmp := make([]int, right-left+1)
for i <= mid && j <= right {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
i++
} else {
tmp[k] = nums[j]
j++
}
k++
}
for i <= mid {
tmp[k] = nums[i]
i++
k++
}
for j <= right {
tmp[k] = nums[j]
j++
k++
}
for i = left; i <= right; i++ {
nums[i] = tmp[i-left]
}
}快速排序：
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
function quickSort(left, right) {
if (left >= right) {
return;
}
let i = left - 1;
let j = right + 1;
const x = nums[(left + right) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
quickSort(left, j);
quickSort(j + 1, right);
}
const n = nums.length;
quickSort(0, n - 1);
return nums;
};归并排序：
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
function mergetSort(left, right) {
if (left >= right) {
return;
}
const mid = (left + right) >> 1;
mergetSort(left, mid);
mergetSort(mid + 1, right);
let [i, j, k] = [left, mid + 1, 0];
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
for (i = left, j = 0; i <= right; ++i, ++j) {
nums[i] = tmp[j];
}
}
const n = nums.length;
let tmp = new Array(n).fill(0);
mergetSort(0, n - 1);
return nums;
};