排序之归并排序｜Go主题月

归并排序简述

归并排序是使用分治策略的一种递归算法，每次将一个切片数组(下面简称列表)一分为二。

1. 如果列表为空或只有一个元素，那么从定义上来说它就是有序的（递归结束的基本情况）。
2. 如果列表不止一个元素，就将列表一分为二，并对两部分都递归调用归并排序。
3. 当两部分都有序后，就进行归并这一基本操作。

归并是指将两个较小的有序列表归并为一个有序列表的过程。
下图a展示了示例列表[10, 1, 5, 3]被拆分后的情况，图b展示了归并过程中的有序列表

Golang代码实现

使用Golang实现的归并排序算法代码如下：

1. package main
2. 
3. import "fmt"
4. 
5. func mergeSort(numList []int) {
6. 	// 归并排序算法：先拆分再合并。
7. 	fmt.Println("拆分：", numList)
8. 	if len(numList) > 1 {
9. 		mid := len(numList) / 2
10. 		// 左右列表需要完全独立
11. 		// 如果直接使用切片因为使用的是同一个底层数组，
12.             // 原始数据将同时会受影响
13. 		leftHalf := make([]int, len(numList[:mid]))
14. 		copy(leftHalf, numList[:mid])
15. 		rightHalf := make([]int, len(numList[mid:]))
16. 		copy(rightHalf, numList[mid:])
17. 		fmt.Println("归并排序前的左：", leftHalf)
18. 		fmt.Println("归并排序前的右：", rightHalf)
19. 		// 对左右列表也进行归并排序
20. 		mergeSort(leftHalf)
21. 		mergeSort(rightHalf)
22. 
23. 		leftHalfIndex := 0
24. 		rightHalfIndex := 0
25. 		numListIndex := 0
26. 		fmt.Println("归并排序后的左：", leftHalf)
27. 		fmt.Println("归并排序后的右：", rightHalf)
28. 
29. 		// 依次取有序左列表和有序右列表数据进行两两比较，取较小值放于原列表对应的位置上
30. 		for leftHalfIndex < len(leftHalf) && rightHalfIndex < len(rightHalf) {
31. 			if leftHalf[leftHalfIndex] < rightHalf[rightHalfIndex] {
32. 				numList[numListIndex] = leftHalf[leftHalfIndex]
33. 				leftHalfIndex += 1
34. 			} else {
35. 				numList[numListIndex] = rightHalf[rightHalfIndex]
36. 				rightHalfIndex += 1
37. 			}
38. 			numListIndex += 1
39. 		}
40. 
41. 		// 当右列表全部数据已放到原列表同时左列表还有剩余数据时
42. 		// 需要把左列表剩余的有序数据放入到原列表
43. 		for leftHalfIndex < len(leftHalf) {
44. 			numList[numListIndex] = leftHalf[leftHalfIndex]
45. 			leftHalfIndex += 1
46. 			numListIndex += 1
47. 		}
48. 
49. 		// 当左列表所有数据已放到原列表同时右列表还有剩余数据时
50. 		// 需要把右列表剩余的有序数据放入到原列表
51. 		for rightHalfIndex < len(rightHalf) {
52. 			numList[numListIndex] = rightHalf[rightHalfIndex]
53. 			rightHalfIndex += 1
54. 			numListIndex += 1
55. 		}
56. 
57. 	}
58. 	// 这已经是有序的数据了
59. 	fmt.Println("合并：", numList)
60. }
61. 
62. func main() {
63. 	numList := []int{10, 1, 5, 3, 7}
64. 	mergeSort(numList)
65. 	fmt.Println(numList)
66. }
复制代码

在上面的代码中，mergeSort函数判断是否已经是递归基本情况。

1. 如果列表的长度小于或等于 1，说明它已经是有序列表，因此不需要做额外的处理。
2. 如果列表的长度大于 1，则通过copy函数得到左半部分和右半部分。

在第 20~21 行对左右子列表调用 mergeSort 函数后，就假设它们已经排好序了;
第 23~55 行负责将两个小的有序列表归并为一个大的有序列表:
归并思路：归并操作每次从左右有序列表中取出最小值，放回初始列表

时间复杂度

分析 mergeSort 函数时，要考虑它的拆分和合并两个独立的构成部分。

1. 拆分过程：列表被一分为二，当列表的长度为 n 时，能切分 log2n 次。
2. 归并过程：列表中的每个元素最终都得到处理，并被放到有序列表中。所以，得到长度为 n 的列表需要进行 n 次操作。
3. 由此可知，需要进行logn 次拆分，每一次需要进行 n 次操作，所以一共是 nlogn次操作。
4. 所以，归并排序算法的时间复杂度是O(nlogn)。

注意点

mergeSort 函数需要额外的空间来存储copy函数得到的左右两半部分。
当列表规模较大时，需要注意内存溢出问题。