题目描述
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 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$ 为数组长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | 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);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | 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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | /**
* @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;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | impl Solution {
pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
Self::quick_sort(&mut nums, 0, n - 1);
return nums;
}
fn quick_sort(nums: &mut Vec<i32>, left: usize, right: usize) {
if left >= right {
return;
}
let mut i = left as i32 - 1;
let mut j = right as i32 + 1;
let pivot = nums[left];
while i < j {
loop {
i += 1;
if nums[i as usize] >= pivot {
break;
}
}
loop {
j -= 1;
if nums[j as usize] <= pivot {
break;
}
}
if i < j {
nums.swap(i as usize, j as usize);
}
}
Self::quick_sort(nums, left, j as usize);
Self::quick_sort(nums, j as usize + 1, right);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution {
fun sortArray(nums: IntArray): IntArray {
fun quickSort(left: Int, right: Int) {
if (left >= right) {
return
}
var i = left - 1
var j = right + 1
val pivot = nums[left]
while (i < j) {
while (nums[++i] < pivot) ;
while (nums[--j] > pivot) ;
if (i < j) {
val temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
}
quickSort(left, j)
quickSort(j + 1, right)
}
quickSort(0, nums.size - 1)
return nums
}
}
|
方法二：归并排序
归并排序是一种分治算法，其思想是将待排序的数据序列不断地折半拆分，直到每个数据块只有一个元素为止，然后再按照拆分的顺序将每个数据块两两合并，在合并的过程中进行排序，最终得到一个有序的数据序列。
归并排序是一种稳定的排序算法，时间复杂度为 $O(n \times \log n)$，空间复杂度为 $O(n)$。其中 $n$ 为数组长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | 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]
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | /**
* @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;
};
|
方法三