04.排序
# 归并排序
相关题目
题解
func sortArray(nums []int) []int {
return mergeSort(nums, 0, len(nums) - 1)
}
func mergeSort(nums []int, begin, end int) []int {
if begin >= end {
return nums
}
mid := (begin + end) /2
mergeSort(nums, begin,mid)
mergeSort(nums, mid + 1,end)
merge(nums, begin,mid,end)
return nums
}
func merge (nums []int, begin,mid,end int) {
tmpArr := make([]int, end - begin + 1)
i := begin
j := mid + 1
k := 0
for ;i<= mid && j <= end;k++ {
if nums[i] <= nums[j]{
tmpArr[k] = nums[i]
i++
}else {
tmpArr[k] = nums[j]
j++
}
}
for ; i<=mid;i++{
tmpArr[k] = nums[i]
k++
}
for ; j<=end;j++{
tmpArr[k] = nums[j]
k++
}
copy(nums[begin:end+1],tmpArr)
}
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
37
38
39
40
41
42
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
37
38
39
40
41
42
# 快速排序
相关思路链接
func sortArr(nums []int) []int {
n := len(nums)
if n <= 1 {
return nums
}
return quickSort(nums, 0,n-1)
}
func quickSort(nums []int, start, end int) []int {
if start >= end {
return nums
}
i := partition(nums, start, end)
quickSort(nums, start, i-1)
quickSort(nums, i+1, end)
return nums
}
func partition(nums []int, start, end int) int {
randPivot := rand.Intn(end-start+1) + start // 随机取一个中点
pivot := nums[randPivot]
nums[end], nums[randPivot] = nums[randPivot], nums[end]
i := start
for j := start; j <= end; j++ {
if nums[j] > pivot {
if i != j {
nums[i], nums[j] = nums[j], nums[i]
}
i++
}
}
nums[i], nums[end] = nums[end], nums[i]
return i
}
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
37
38
39
40
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
37
38
39
40
编辑 (opens new window)
上次更新: 2023/03/13, 15:10:41