归并排序代码

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
func MergeSort(array []int64) {
middle := len(array) >> 1
leftIndex := 0
rightIndex := middle
tempLeftIndex := 0
// 递归合并左边子数组的无序部分
for a := 0; a < middle-1; a++ {
if array[a] > array[a+1] {
MergeSort(array[:middle])
break
}
}
// 递归合并右边子数组的无序部分
for b := middle; b < len(array)-1; b++ {
if array[b] > array[b+1] {
MergeSort(array[middle:])
break
}
}
tempArray := make([]int64, len(array))
// 左右两个子数组完成排序后进行合并
for leftIndex < middle && rightIndex < len(array) {
// 此处判断时,在值相等的情况下先插入左边子数组的值
// 这时算法稳定性为稳定,否则为不稳定
if array[leftIndex] <= array[rightIndex] {
tempArray[tempLeftIndex] = array[leftIndex]
leftIndex++
tempLeftIndex++
} else {
tempArray[tempLeftIndex] = array[rightIndex]
rightIndex++
tempLeftIndex++
}
}
// 插入左边子数组的所有剩余值至临时数组
for leftIndex < middle {
tempArray[tempLeftIndex] = array[leftIndex]
leftIndex++
tempLeftIndex++
}
// 插入右边子数组的所有剩余值至临时数组
for rightIndex < len(array) {
tempArray[tempLeftIndex] = array[rightIndex]
rightIndex++
tempLeftIndex++
}
// 修改后的数组覆盖原数组
copy(array, tempArray)
}

归并排序算法平均时间复杂度O(nlog2n),最好时间复杂度为O(nlog2n),最差时间复杂度为O(nlog2n)
空间复杂度O(n),稳定性为稳定