学习回顾算法（归并排序算法）

以你之姓@ 2022-06-05 07:27 184阅读 0赞

## 归并排序概述 ##

归并排序（merge-sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个应用。将已有序的自序合并，得到完全有序的序列；即先使每个子序列有序，再使子序列间断有序。再将两个有序表合并成一个有序表。

**归并排序算法原理**  
归并过程为：比较a\[i\]和b\[j\]的大小，若a\[i\]<=b\[j\],则将第一个有序列表中的元素a\[i\]复制到r\[k\]中，并将i和k分别加上1；否则将第二个有序表中的元素b\[j\]复制到r\[k\]中，并将j和k分别加上1，如此循环下去，知道其中一个有序表去完，然后再将另外一个忧郁表中剩余的元素复制到r中从下标k到下标t的单元。  
归并排序的算法通常使用递归实现，先吧待排序区间\[s,t\]以中点二分，接着把左边的子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间\[s,t\]

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

例子：  
初始序列为：2、4、7、5、8、1、3、6为例子，归并排序算法过程如下  
![归并算法][SouthEast]

**算法分析**  
（1）时间复杂度  
归并排序的形式就是一颗二叉树，需要遍历的次数是其深度。时间复杂度为O(N\*log2N)。

（2）空间复杂度  
需要申请的空间大小最大为整个序列的长度。至少为N。所以空间复杂度为O(N)

（3）稳定性  
归并排序中，相等的元素的顺序不会改变，是稳定的算法。

## 实现 ##

1、使用golang实现

package main
    
    import (
        "fmt"
    )
    
    func mergeSort(values []int) []int {
        Len := len(values)
        if Len <= 1 {
            return values
        }
        mid := Len / 2
        left := mergeSort(values[:mid])
        right := mergeSort(values[mid:])
        return merge(left, right)
    }
    
    func merge(left, right []int) (ret []int) {
        //fmt.Println(left)
        //fmt.Println(right)
        lnum, rnum := 0, 0
        lLen, rLen := len(left), len(right)
        for lnum < lLen && rnum < rLen {
            if left[lnum] <= right[rnum] {
                ret = append(ret, left[lnum])
                lnum++
            } else {
                ret = append(ret, right[rnum])
                rnum++
            }
        }
        ret = append(ret, left[lnum:]...)
        ret = append(ret, right[rnum:]...)
        return
    }
    
    func main() {
        values := []int{
       2, 4, 7, 5, 8, 1, 3, 6}
        fmt.Println(values)
        ret := mergeSort(values)
        fmt.Println(ret)
        return
    }

结果

[2 4 7 5 8 1 3 6]
    [1 2 3 4 5 6 7 8]

打开注释可以得到的结果为：

[2]
    [4]
    [7]
    [5]
    [2 4]
    [5 7]
    [8]
    [1]
    [3]
    [6]
    [1 8]
    [3 6]
    [2 4 5 7]
    [1 3 6 8]

对应：  
![归并过程][SouthEast 1]

[SouthEast]: /images/20220605/e8d2e5415af1449b950c8c87ed098a2c.png
[SouthEast 1]: /images/20220605/0a35c2f9b4344ca19c870d910fea15e3.png