图解排序算法及实现——归并排序（Merge Sort）

约定不等于承诺〃 2022-05-14 05:29 240阅读 0赞

# 思路 #

归并排序（MergeSort），是创建在归并操作上的一种有效的排序算法，效率为***O(nlogn)*** 。1945年由约翰·冯·诺伊曼首次提出。该算法是采用**分治法（Divide and Conquer）**的一个非常典型的应用，且各层分治递归可以同时进行。

# 实现 #

### 递归法: 自顶向下（Top-Down） ###

直接在原序列上直接归并排序，每次归并排序分别对左右两边进行归并排序，直至细分到**两两分组**。

### 迭代法：自底向上（Bottom-Up） ###

假设序列共有 ***n*** 个元素：  
1. 先相邻**两两分组**进行归并排序  
2. 再相邻**四四分组**进行归并排序  
3. 再相邻**八八分组**进行归并排序  
4. 重复扩大分组规模，直到所有元素排序完毕  
5. …

# 复杂度 #

平均时间复杂度：***O(nlogn)***  
最坏时间复杂度：***O(nlogn)***  
最优时间复杂度：***O(nlogn)***

最坏空间复杂度：***O(n)***

# 图解 #

![这里写图片描述][SouthEast]  
来源：  
![这里写图片描述][Merge-sort-example-300px.gif]  
来源：维基百科  
![这里写图片描述][Merge_sort_animation2.gif]  
来源：维基百科

# python实现 #

### 递归法: 自顶向下（Top-Down） ###

def MergeSort(arr):
        '''1.自顶向下递归实现'''
    
        n = len(arr)
        _mergeSort(arr, 0, n-1)  # 顶部开始： 先对[0,n-1]范围内进行递归排序
    
    
    def _mergeSort(arr,l,r):
    
        # 终止迭代的条件
        if l>=r:
            return
    
        mid = l+(r-l)//2  # (l+r)//2 的改进算法，防止l+r太大溢出
        _mergeSort(arr,l,mid)   # 对左半边arr[l...mid]归并排序
        _mergeSort(arr,mid+1,r) # 对右半边arr[mid+1...r]归并排序
        _merge(arr,l,mid,r)     # 合并之
    
    
    def _merge(arr,l,mid,r):
        '''将arr[l...mid]和arr[mid+1...r]两部分进行归并'''
    
        # 额外开辟空间，拷贝arr[l,..,r]到aux数组，然后在原arr上赋值操作
        aux = arr[l:r+1]
    
        i ,j = l, mid+1 # 从各自左边开始扫描
        # k 指向当前为arr赋值的位置
        for k in range(l,r+1):
    
            # 边界判断
            if i > mid:
                arr[k] = aux[j-l]
                j +=1
            elif j > r:
                arr[k] = aux[i-l]
                i += 1
            elif aux[i-l] < aux[j-l]:
                arr[k] = aux[i-l]
                i += 1
            else:
                arr[k] = aux[j-l]
                j += 1

### 递归法: 自顶向下（改进版） ###

改进1：归并到小规模数据时，直接调用插入排序。（因为对小规模数组,使用插入排序更高效）  
改进2：对于arr\[mid\] <= arr\[mid+1\]的情况,无需merge

def MergeSort(arr):
        '''2.自顶向下递归实现（改进）'''
    
        n = len(arr)
        _mergeSort(arr, 0, n-1)  # 顶部开始： 先对[0,n-1]范围内进行递归排序
    
    
    def _mergeSort(arr,l,r):
    
        if l>=r:
            return
        # 改进1：对于小规模数组,使用插入排序更高效
    #    from SortFunctions import InsertionSort
    #    if r-l <= 15:
    #        insertionSort(arr, l, r)
    #        return
    
        mid = (r+l)//2  # (l+r)/2 的改进算法，防止l+r太大溢出
        _mergeSort2(arr,l,mid)   # 对左半边arr[l...mid]归并排序
        _mergeSort2(arr,mid+1,r) # 对右半边arr[mid+1...r]归并排序
    
        # 改进2：对于arr[mid] <= arr[mid+1]的情况,无需merge
        # 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
        if arr[mid] > arr[mid+1]:
            _merge(arr,l,mid,r)

`_merge()`函数上面已定义，直接上面的就好，这里为了节省篇幅，不再定义  
对于**改进1**，经本人实测，在python3的环境下，并没有提升速度，所以我还是注释掉了。

### 迭代法：自底向上（Bottom-Up） ###

def MergeSort(arr):
        '''3.自底向上迭代实现'''
    
        # 逐层迭代，从最底层开始，sz = 1 → n 为待合并数组的长度
        sz = 1
        while sz <= n:
            # 每层，从左往右两两归并，i = 0 → n-1
            i = 0
            while i<n:
                # 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
                _merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1))
                i += sz+sz # 跳到下一对
            sz += sz

`_merge()`函数上面已定义，直接上面的就好，这里为了节省篇幅，不再定义

# 与其他排序算法性能比较 #

[SouthEast]: /images/20220514/b7a9ea3445a84d73ba7e91386d077020.png
[Merge-sort-example-300px.gif]: https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif
[Merge_sort_animation2.gif]: https://upload.wikimedia.org/wikipedia/commons/c/c5/Merge_sort_animation2.gif