归并排序

最近受了不小的打击，又开始学习数据结构与算法了，不知道能坚持多久，写博客只为学习记录。

一、归并排序思想：归并排序用到了分治思想，假设要排序一个数组，先把这个数组从中间分成前后两个部分，然后对前后两个子数组分别排序，再将排序好的两个子数字合并再一起，整个数组就有序了。这种分治的问题可以用递归来解决。

二、递归实现分析：递归代码编写有两个重要的步骤：1.推到递推公式 2.递归结束条件，接下来就可以将递推公式翻译成代码了，根据数组划分的分析，递归公式可以表示为：mergeSort(a...b) = merge( mergeSort(a...mid) , mergeSort(mid+1, b)，这个mid是数组的中间位置，结束条件为a>=b，不需要再分解了。合并有序子数组的时候，需要申请原数组大小的临时空间。

三、代码实现：用go语言实现归并排序代码

 1 func sortArray(nums []int) []int {
 2     mergeSort(nums, 0, len(nums) - 1)
 3     return nums
 4 }
 5 
 6 //想用归并排序，递归实现
 7 func mergeSort(nums []int, i int, j int) {
 8     //递归终止条件
 9     if i >= j {
10         return
11     }
12 
13     //将当前序列划分为两个子序列
14     q := (i+j)/2
15     //递归的排序左右两个子序列
16     mergeSort(nums, i, q)
17     mergeSort(nums, q+1, j)
18 
19     //需要将排序好的数据合并
20     merge(nums, i, q, j)  
21 }
22 
23 func merge(nums []int, start int, mid int, end int) {
24     //申请一个合并两个子序列需要的临时数组
25     var numTemp []int
26     var index1, index2 = start, mid + 1
27     for index1 <= mid && index2 <= end {
28         //逐个对比两个子序列的值
29         if nums[index1] <= nums[index2] {
30             numTemp = append(numTemp, nums[index1])
31             index1++
32         } else {
33             numTemp = append(numTemp, nums[index2])
34             index2++
35         }
36     }
37 
38     //某一个子序列已经遍历完了，看看到底是哪个没完，直接把数据放到临时空间就好了
39     if index1 <= mid {
40         numTemp = append(numTemp, nums[index1: mid+1]...)
41     }
42     if index2 < end {
43         numTemp = append(numTemp, nums[index2: end+1]...)
44     }
45 
46     for index, data := range numTemp {
47         nums[start + index] = data
48     }
49 }

四、代码调试：代码写完跑的时候，发现Panic了，然后参考了网上的实现，才发现go的切片操作a[ i : j ] 是不包含j元素的，改了后就可以了。

学习参考：golang归并排序 - Go语言中文网 - Golang中文社区 (studygolang.com)

极客时间《数据结构与算法之美》