Python-排序-归并排序中如何用哨兵来追求极致的性能？

以下是本人学习极客时间的专栏《数据结构与算法之美》后，自己动手敲代码实现，并写下当时的思考，希望对你也有帮助。
系列文章：
工作后，为什么还要学习数据结构与算法
Python-排序-冒泡排序-优化
Python-排序-选择排序-优化
Python-排序-插入排序-优化

每当我在编写递归程序的时候，我都能感受到分治算法的强大威力。分治思想，也就是分而治之，将一个复杂的大问题可以分解成若干个子问题，子问题解决后，经过合并，最终得到大问题的解。想想生活中不也到处充满着分治思想吗？

一个大公司会分成若干部门，部分有若干负责人，负责人下面有若干员工。公司运转的好不好，要看部门运转的情况及部门之间的协调效果（归并），一个部门的运转情况要看负责人的规划和实施（对任务的更细分解），负责人的规则和实施又源自于每一个员工的工作绩效。每一个员工都优秀，再加上一级一级的归并，最终会体现在公司的经营业绩上面。

计算机领域中的分治思想的应用更是非常广泛，比如近些年非常火爆的分布式系统架构 Hadoop 中的 MapReduce。无论今后的技术更新迭代速度有多快，但其用到的算法思想，数学原理都是近百年前的东西，因此只要学好基础的算法、计算机相关的一些数学知识，就可以以不变应万变，无论何种新技术，都可以很快掌握。

今天我试着写了分治思想的排序算法--归并排序，它的思路也比较简单，以数组为例，要对一个数组进行排序，可以将数组从中间分成左右两部分，如果左部分有序，右部分也有序，那么就可以按照一定的顺序从左部分和右部分抽取数据组成一个有序的数组，接下来的问题就是如何让左部分和右部分有序，同样的道理，再次进行分解，直到最后的部分只有一个元素为止，再对分解后的部分进行归并，最终完成排序任务。

归并排序的代码比较容易写出来，但如何使用哨兵来优化性能，却需要动一动大脑，我也是考虑了好一会再想出来，今天特意写出来分享一下。

归并排序的思路

1. 给定待排序的数组 data_list，长度为 n ，设置首尾两个游标 p,q，初始状态，p = 0,q = n，先不纠结是 n 还是 n-1 。

2. 分解: 取中间值 r = (p + q)/2 ，将数组分成左部分 data_list[p,r],右部分 data_list[r+1,q] 。

3. 对上述左右部分递归调用分解。

4. 归并左部分和右部分的结果。

5. 退出条件是 p>=q。

下面直接给出归并排序的 Python 代码，你也可以改写成自己熟悉的编程语言。

归并排序代码（python)

def merge_sort(data_list):
    '''
    归并排序程序入口
    '''
    length = len(data_list)
    merge_sort_c(data_list,0,length)

def merge_sort_c(data_list,p,q):
    '''
    递归调用
    '''
    #退出条件
    if p+1>=q:
        return 
    else:
        r = (p+q)//2 
        merge_sort_c(data_list,p,r)
        merge_sort_c(data_list,r,q)
        merge(data_list,p,r,q)  #将data_list[p:r] 与 data_list[r:q] 按顺序归并到 data_list 相应位置

def merge(data_list,p,r,q):
    '''
    归并函数
    例如 data_list[p:q] = [...,1,4,2,3,...]
    data_list[p:r] = [1,4]
    data_list[r:q] = [2,3]
    tmp = [1,2,3,4]
    归并后 data_list[p:q] = [...,1,2,3,4,...]     
    '''
    tmp = []    
    i = p
    j = r 
    while i < r and j < q:
        if data_list[i] <= data_list[j]:
            tmp.append(data_list[i])
            i+=1
        else:
            tmp.append(data_list[j])
            j+=1

    while i < r :
        tmp.append(data_list[i])
        i+=1

    while j < q:
        tmp.append(data_list[j])
        j+=1
    
    #将 tmp 数据复制到 data_list
    for tmp_index,index in enumerate(range(p,q)):
        data_list[index] = tmp[tmp_index]

下面运行下

if __name__ == "__main__":
    data_list = [38, 50, 63, 27, 89, 94, 11, 82, 9, 13]
    print(data_list)
    merge_sort(data_list)
    print(data_list)

得到如下结果

[38, 50, 63, 27, 89, 94, 11, 82, 9, 13]
[9, 11, 13, 27, 38, 50, 63, 82, 89, 94]

性能分析

1、时间复杂度：归并排序不关心数组的初始状态，因此最好、最坏、平时时间复杂度都是一样的，为O(nlogn)，关于专栏中是这样求解时间复杂度的，非常有学习的价值。

不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。

我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：

T(1) = C；   n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1

通过这个公式，如何来求解 T(n) 呢？还不够直观？那我们再进一步分解一下计算过程。

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步分解推导，我们可以得到 T(n) = 2^k T(n/2^k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log₂n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog₂n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

2、空间复杂度：O(n)，因此它不是一个原地排序算法。递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

3、稳定性：稳定。我们对数组分成左右两部分，对于两边相同的值，我们可以选择将右部分的值归并后放在左边相同值的后面，因此它是稳定的排序算法。

使用哨兵优化性能

在上述 merge 函数中有三处使用了 while 循环，第一个 while 循环条件中还有两个范围判断语句，当数据量非常大时，这些过多的判断势必会影响算法的性能。

我们知道，在编程中可以借助哨兵来简单条件判断，从而可以写出 bug 更少的代码，进而优化性能。

上述中的 merge 函数主要目的主是合并两个有序数组，但是为了在比较的过程中防止越界，加入了 i < r 和 j < q 来防止左右部分越界，最后防止某部分有剩余元素从而多写了两个 while 循环。

其实在大多数情况下，越界的情况是非常少的，那么每一次循环对越界的检查也会浪费 CPU 资源，而哨兵就是优化条件判断的。

思考：
1、如果左右部分的最后一个元素都是最大且相等，那么当左边的元素循环结束时，右边也必定结束，这样只用一个 while 就可以搞定，而且只需要一个 i < r 就够了，节省一个条件判断。

2、范围比较 i < r 需要 cpu 对每个二进制位进行比较，如果换成不等于判断，只要一个二进制位不同，就可以得出结果，理论上也可以更快些。

使用哨兵的 merge 函数如下所示：

def merge2(data_list,p,r,q):
    '''
    利用哨兵的归并函数
    例如 data_list[p:q] = [...,1,4,2,3,...]
    part_left = [1,4]
    part_right = [2,3]
    归并后 data_list[p:q] = [...,1,2,3,4,...] 
    '''
    part_left = [data_list[index] for index in range(p,r)]  #临时数组保存左部分
    part_right = [data_list[index] for index in range(r,q)] #临时数组保存右部分

    #对左边部分或右边部分增加哨兵，哨兵为待排序数据的最大值如99999
    max_value = 99999
    part_left.append(max_value)
    part_right.append(max_value)
    i = 0
    j = 0
    k = p
    # while i != r-p: # 也可以这样写，看自己喜好
    while part_left[i] != max_value:
        if part_left[i] <= part_right[j]:
            data_list[k] = part_left[i]
            i += 1
        else:
            data_list[k] = part_right[j]
            j += 1
        k +=1 #依次从左边部分和右边部分按顺序抽取数据  

分别在左部分和右部分的最后加入最大值的哨兵，可以减化 merge 函数的编码，使用哨兵有以下三点优化：

1、减少了 while 的个数，简化了编码过程
2、减少了 while 循环的条件判断
3、将范围判断改为不等于判断

小结：分治是一种解决问题的处理思想，递归是一种编程技巧。哨兵是一种不错的编程技巧，使用它也可减少 bug，某种程度上，也提高了代码的性能。

（完）

加个人微信公众号 somenzz，获得原创技术干货，和你一起学习。

个人微信公众号.jpg