归并排序

归并算法思想
Merge_sort_animation2.gif

上面的 gif 来自维基百科

Data Structure Visualization 这个万丈是一个很好的学习数据结构的网站，将数据结构可视化，可以直观的看到插入、删除、旋转、搜索、排序等效果。

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 归并排序 - 图2（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

归并

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

递归法（Top-down）

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

  5. 将另一序列剩下的所有元素直接复制到合并序列尾

    迭代法（Bottom-up）

    原理如下（假设序列共有 归并排序 - 图3 个元素）：

  6. 将序列每相邻两个数字进行归并操作，形成 归并排序 - 图4 个序列，排序后每个序列包含两/一个元素

  7. 若此时序列数不是1个则将上述序列再次归并，形成 归并排序 - 图5 个序列，每个序列包含四/三个元素
  8. 重复步骤2，直到所有元素排序完毕，即序列数为1

递归法通过两个指针的移动来完成归并排序。迭代法则利用了分治思想。

Go

迭代法

  1. func MergeSort(array []int) []int{
  2.     n := len(array)
  3.     if n < 2 {
  4.         return array
  5.     }
  6.     key := n / 2
  7.     left := MergeSort(array[0:key])
  8.     right := MergeSort(array[key:])
  9.     return merge(left, right)
  10. }
  12. func merge(left []int, right []int) []int{
  13.     newArr := make([]int, len(left)+len(right))
  14.     i, j, index :=0,0,0
  15.     for {
  16.         if left[i] > right[j] {
  17.             newArr[index] = right[j]
  18.             index++
  19.             j++
  20.             if j == len(right) {
  21.                 copy(newArr[index:], left[i:])
  22.                 break
  23.             }
  25.         }else{
  26.             newArr[index] = left[i]
  27.             index++
  28.             i++
  29.             if i == len(left) {
  30.                 copy(newArr[index:], right[j:])
  31.                 break
  32.             }
  33.         }
  34.     }
  35.     return newArr
  36. }
  1. func merge(data []int) []int {
  2.     sum := len(data)
  3.     if sum <= 1 {
  4.         return data
  5.     }
  6.     left := data[0 : sum/2]
  7.     lSize := len(left)
  8.     if lSize >= 2 {
  9.         left = merge(left)
  10.     }
  11.     right := data[sum/2:]
  12.     rSize := len(right)
  13.     if rSize >= 2 {
  14.         right = merge(right)
  15.     }
  16.     j := 0
  17.     t := 0
  18.     arr := make([]int, sum)
  19.     fmt.Println(left, right, data)
  20.     for i := 0; i < sum; i++ {
  21.         if j < lSize && t < rSize {
  22.             if left[j] <= right[t] {
  23.                 arr[i] = left[j]
  24.                 j++
  25.             } else {
  26.                 arr[i] = right[t]
  27.                 t++
  28.             }    
  29.         }  else if j >= lSize{
  30.             arr[i] = right[t]
  31.             t++
  32.         }  else if t >= rSize{
  33.             arr[i] = left[j]
  34.             j++
  35.         }
  36.     }
  37.     return arr
  38. }

上述代码来自维基百科，我在想，这不是相同的算法么？这两段程序有什么区别？同样都是递归