归并排序

归并排序(Merge sort) 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归(所有递归的方法都可以用迭代重写，所以就有了第 2 种方法).
  • 自下而上的迭代.

算法原理

归并排序算法原理：

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列.
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置.
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置.
  • 重复上一步直到某一指针达到序列尾；
  • 将另一序列剩下的所有元素直接复制到合并序列尾.

归并排序 - 图1

归并排序算法实现：

  1. func main() {
  2.     array := []int{55, 94, 87, 12, 4, 32, 11,8, 39, 42, 64, 53, 70, 12, 9}
  3.     fmt.Println("before MergeSort",array)
  4.     array = MergeSort(array)
  5.     fmt.Println("after MergeSort:",array)
  6. }
  8. func MergeSort(array []int) []int{
  9.     n := len(array)
  10.     if n < 2 {
  11.         return array
  12.     }
  13.     key := n / 2
  14.     left := MergeSort(array[0:key])
  15.     right := MergeSort(array[key:])
  16.     return merge(left, right)
  17. }
  19. func merge(left []int, right []int) []int{
  20.     tmp := make([]int, 0)
  21.     i, j := 0,0
  22.     for  i < len(left) && j < len(right) {
  23.         if left[i] < right[j]{
  24.             tmp = append(tmp, left[i])
  25.             i ++
  26.         }else{
  27.             tmp = append(tmp, right[j])
  28.             j ++
  29.         }
  30.     }
  31.     tmp = append(tmp, left[i:]...)
  32.     tmp = append(tmp, right[j:]...)
  33.     return tmp
  34. }

运行结果:

  1. before MergeSort [55 94 87 12 4 32 11 8 39 42 64 53 70 12 9]
  2. after MergeSort: [4 8 9 11 12 12 32 39 42 53 55 64 70 87 94]