算法基础：排序（二）——归并排序——Python实现

1. 归并排序与分治策略

归并排序的核心思想就是 分而治之。

先介绍下分治法，设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略：对于一个规模为N（N较大）的问题，将其划分为K个规模较小的子问题，若子问题相互独立且与原问题形式相同，我们则可以使用递归不断地将子问题进行划分，将一个大问题自顶向下一层层划分为容易解得小问题，得到小问题的解后再自底向上逐层合并得到原问题的解。

归并排序就是采用了这样的分治策略来设计算法。对于一个长度为N的数组，通过逐层二分将大数组分解成容易排序的小数组，然后对排好序的两个子数组进行归并，最终得到归并后的有序数组。

使用增量策略的排序（如插入排序）的算法复杂度为O(n^2)，而使用分治策略的归并排序则将算法复杂度降到了O(nlogn)。经过测试，这种排序算法的优化效果是很显著的，大家可以在最后看到测试时各种方法所用时间的对比。

---

2. 自顶向下、自底向上、使用插入排序的归并算法实现

（1）归并算法

有了分治的策略，那么我们如何将排好序的子数组合并成一个有序的数组呢？这就是归并排序的核心算法merge(a,lo,mid,hi)。

对于上图看了代码应该很容易理解：
需要一个辅助数组aux，现将a的元素拷贝给aux，再将aux元素归并到a中。

    def __merge(self,a,lo,mid,hi):
        i=lo
        j=mid+1
        self.__aux[lo:hi+1]=a[lo:hi+1] #将a[lo..hi] 复制给aux[lo..hi]
        for k in range(lo,hi+1):
            if i > mid:#左侧元素归并完毕，将右侧剩余元素依次拷贝到a
                a[k] = self.__aux[j]
                j+=1
            elif j > hi:#右侧，同上
                a[k] = self.__aux[i]
                i+=1
            elif self.less(self.__aux[j],self.__aux[i]):#谁小将谁归并入a
                a[k] = self.__aux[j]
                j+=1
            else:
                a[k] = self.__aux[i]
                i+=1

（2）自顶向下的归并排序

有了以上的归并操作后，我们如何递归地划分数组并将两个子数组排序呢？通过递归直到将子数组划分为长度为1的数组，此时hi <= lo开始return，归并后的数组即是长度为2，4，8，…，n的有序数组。

   def __sort_by_recurse(self,a,lo,hi): # 使用递归进行自顶向下归并
        if hi <= lo:
            return
        mid=int((hi+lo)/2)
        self.__sort_by_recurse(a,lo,mid)
        self.__sort_by_recurse(a,mid+1,hi)
        self.__merge(a,lo,mid,hi)

（3）自底向上的归并排序

我们同样可以使用循环，从长度为1的数组开始归并，层层向上，这样每次都是两个有序的子数组（长度n/2）归并成一个有序的数组（长度n）。

    def __sort_by_loop(self,a): # 使用循环，自底向上归并
        sz=1
        while sz<len(a):
            for lo in range(0,len(a)-sz,sz+sz):
                self.__merge(a,lo,lo+sz-1,min(lo+sz+sz-1,len(a)-1))
            sz += sz

（4）对小规模子数组使用插入排序

递归会使小规模问题中的函数调用过于频繁，而插入排序（或者选择排序）即简单，而且在小数组上可能比归并排序更快。经测试，插入排序子数组的大小在10左右比较合适。

    def __merge_with_insertion(self,a): # 对较小的子数组使用插入排序，从而减少归并次数，优化排序算法
        sz=min_merge_sz=10 # 归并子数组的最小长度
        for i in range(0,len(a),min_merge_sz):
            a[i:min(i + min_merge_sz, len(a))] = self.__insertion_sort(a[i:min(i+min_merge_sz, len(a))]) # 对长度小于min_merge_sz的子数组使用插入排序
        while sz < len(a):
            for lo in range(0, len(a) - sz, sz + sz):
                self.__merge(a, lo, lo + sz - 1, min(lo + sz + sz - 1, len(a) - 1))
            sz += sz

3.测试与对比

数组长度为1000

数组长度为10000

数组长度为100000（已无法使用O(n^2)的初级排序）

数组长度为1000000（百万级数组归并排序已经很慢了，需要十几秒）

通过前两个可以验证插入排序O(n^2)的时间复杂度，n没增大10倍，耗时增加100倍。
洗牌算法时间复杂度为O(n)，归并排序时间复杂度O(nlogn)。

为了测试方便，将测试代码的一部分写入了sort方法里，完整的程序如下：

import random
import time


# random、numpy.random模块都有shuffle方法，这里顺便自己实现一下
class Shuffle:

    @staticmethod
    def knuthShuffle(a):
        for i in range(0, len(a)): # 从左到右遍历数组
            r=random.randint(0,i) # 生成一个0-i之间的随机数
            a[i], a[r] = a[r], a[i] # 交换


class Sort:

    def sort(self, a):
        pass

    @staticmethod
    def less(small, big):
        return small < big

    @staticmethod
    def exch(a, i, j):
        a[i], a[j] = a[j], a[i]

    def isSorted(self, a):
        for i in range(1,len(a)):
            if self.less(a[i], a[i-1]):
                return False
        return True


class Insertion(Sort):

    def sort(self, a):
        for i in range(1,len(a)):
            for j in range(i,0,-1):
                if self.less(a[j],a[j-1]):
                    self.exch(a,j,j-1)
                else:
                    break


class Merge(Sort):

    __aux = None

    def sort(self, a):
        self.__aux = list(a) # 创建辅助数组
        l1, l2, l3, l4 = list(a), list(a), list(a), list(a)

        start = time.time()
        self.__sort_by_recurse(l1, 0, len(l1) - 1)
        end = time.time()
        print("Merge sort by recurse:",end - start,l1)

        start = time.time()
        self.__sort_by_loop(l2)
        end = time.time()
        print("Merge sort by loop:",end - start,l2)

        start = time.time()
        self.__merge_with_insertion(l3)
        end = time.time()
        print("Merge sort with insertion:",end - start,l3)

        start = time.time()
        self.__insertion_sort(l4)
        end = time.time()
        print("Insertion sort by recurse:",end - start,l4)

    def __sort_by_recurse(self,a,lo,hi): # 使用递归进行自顶向下归并
        if hi <= lo:
            return
        mid=int((hi+lo)/2)
        self.__sort_by_recurse(a,lo,mid)
        self.__sort_by_recurse(a,mid+1,hi)
        self.__merge(a,lo,mid,hi)

    def __sort_by_loop(self,a): # 使用循环，自底向上归并
        sz=1
        while sz<len(a):
            for lo in range(0,len(a)-sz,sz+sz):
                self.__merge(a,lo,lo+sz-1,min(lo+sz+sz-1,len(a)-1))
            sz += sz

    def __merge_with_insertion(self,a): # 对较小的子数组使用插入排序，从而减少归并次数，优化排序算法
        sz=min_merge_sz=10 # 归并子数组的最小长度
        for i in range(0,len(a),min_merge_sz):
            a[i:min(i + min_merge_sz, len(a))] = self.__insertion_sort(a[i:min(i+min_merge_sz, len(a))]) # 对长度小于min_merge_sz的子数组使用插入排序
        while sz < len(a):
            for lo in range(0, len(a) - sz, sz + sz):
                self.__merge(a, lo, lo + sz - 1, min(lo + sz + sz - 1, len(a) - 1))
            sz += sz

    def __merge(self,a,lo,mid,hi):
        i=lo
        j=mid+1
        self.__aux[lo:hi+1]=a[lo:hi+1] #将a[lo..hi] 复制给aux[lo..hi]
        for k in range(lo,hi+1):
            if i > mid:
                a[k] = self.__aux[j]
                j+=1
            elif j > hi:
                a[k] = self.__aux[i]
                i+=1
            elif self.less(self.__aux[j],self.__aux[i]):
                a[k] = self.__aux[j]
                j+=1
            else:
                a[k] = self.__aux[i]
                i+=1

    def __insertion_sort(self, a):
        for i in range(1, len(a)):
            for j in range(i, 0, -1):
                if self.less(a[j], a[j - 1]):
                    self.exch(a, j, j - 1)
                else:
                    break
        return a


l = [i for i in range(10000)] # 生成一个0-9999的列表
start = time.time()
Shuffle.knuthShuffle(l) # 洗牌,类内定义了static方法，不用实例化也可以调用
end = time.time()
print("Shuffling time:",end - start,l)
mergesort=Merge()
mergesort.sort(l)