forked from luox78/go-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge.go
62 lines (50 loc) · 851 Bytes
/
merge.go
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package sort
// MergeSort 归并排序
func MergeSort(nums []int) {
if len(nums) <= 1 {
return
}
mergeSort(nums, 0, len(nums)-1)
}
// 递归分治
func mergeSort(nums []int, p, r int) {
if p >= r {
return
}
// 求中间索引
q := p + (r-p)/2
mergeSort(nums, p, q)
mergeSort(nums, q+1, r)
merge(nums, p, q, r)
}
// 合并函数
func merge(nums []int, p, q, r int) {
// 临时存储
tmp := make([]int, r-p+1)
i, j, k := p, q+1, 0
// 比较并加入临时存储
for i <= q && j <= r {
if nums[i] < nums[j] {
tmp[k] = nums[i]
i++
} else {
tmp[k] = nums[j]
j++
}
k++
}
// 处理剩余的部分
start, end := i, q
if j <= r {
start = j
end = r
}
for ; start <= end; start++ {
tmp[k] = nums[start]
k++
}
// 数据搬移至原空间中
for i := 0; i <= r-p; i++ {
nums[p+i] = tmp[i]
}
}