应用场景

  1. 求小和
  2. 求逆序对的个数

几个注意点:

mid := l + (r-l)>>1 避免数组越界

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来

具体实现

思路:数组减半,两部分都有序之后进行合并

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
func MergeSort(nums []int) {
//如果输入不合法并且数组中只有1个数字直接返回
if nums == nil || len(nums) < 2 {
return
}
mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, l, r int) {
//递归结束条件
if l == r {
return
}

//注意这个写法:可以避免越界同时使用>>1加速运算
mid := l + (r-l)>>1
//分治
mergeSort(nums, l, mid)
mergeSort(nums, mid+1, r)

//合并两部分[l,mid] [mid+1,r]
merge(nums, l, mid, r)
}

func merge(nums []int, l, mid, r int) {
i, j := l, mid+1
//申请一个辅助数组
help := make([]int, r-l+1)
index := 0
//谁小填谁移谁
for i <= mid && j <= r {
if nums[i] > nums[j] {
help[index] = nums[j]
j++
} else {
help[index] = nums[i]
i++
}
index++
}

//移动剩下的一部分
//注意下面两个是for循环,不是if
//另外注意的是下面两个for循环有且只有一个可以被执行
for i <= mid {
help[index] = nums[i]
index++
i++
}

for j <= r {
help[index] = nums[j]
index++
j++
}

//此时help已经填充好我们排序后的数字了,我们需要将且拷贝到原数组的l->r
for i := l; i <= r; i++ {
nums[i] = help[i-l]
}
}

总结

归并排序涉及到了我们算法中的分治思想。

<<大话数据结构>>:不断分治,最终得到一颗完全二叉树,由完全二叉树的深度得知,整个归并排序需要进行log2N次,每次都需要扫描待排序的记录,时间复杂度为O(N),因此总时间复杂度为O(NlogN)。归并算法前后有比较,不存在跳跃,因此归并排序是一种稳定的排序算法。归并排序是一种比较占用内存但却效率高且稳定的算法。

评论