分治思想下的高效排序算法

cover

什么是分治？这是一种解决问题的方法。别看它名字高大上，其实我们在日常生活学习中经常用到它。我相信，你看完下面的例子后就可以明白分治的内涵了。

还记得你小学是如何计算多个数连续相加吗？我想，一般的解决办法应该是这样的：

从左到右，让第一个数和第二个数相加，所得的结果和后续的式子相加构成新的式子。此时，新得到的式子比原式更简单，更容易解决（因为要相加的数的个数变少了）。接着，让新的式子中的第一个数和第二个数相加，所得结果和后续剩下的式子构成另一个新的式子···如此进行下去，原式会不断的被化简，最终只剩下一个数，而这个数，正是原式的结果。

这里用来化简多个数相加的方法其实就是“分治”的实际应用。仔细观察上述过程，我们可以总结概括利用分治解决问题的两大步骤：

第一， 化简原问题。我们要找到能够将原问题化简为相似的、更小的、更易解决的子问题的方法。在上述连续的加法计算中，不断地将式子中第一个数字和第二个数字相加，所得结果和剩下的式子构成新式子，供下一步化简使用。这个过程便是不断化简问题的过程。

第二， 找到答案显而易见的基础案例。我们要找到一个非常简单的一个案例和该案例发生时的条件（这个案例要尽可能地简单，从而通过常识即可给出案例对应的答案）。这也指明了化简的终点。对应上面加法的例子，它的基础案例便是当化简到一个数时，化简终止。

上述对于分治方法的描述是不是有些熟悉？对了！它解决问题的过程和递归十分相似。基于这一点特质，我们可以利用递归程序来实现分治。

分治思想在算法中有很多应用，要说其中最基础的、最实用的，我想应该是以下要介绍的两种高效排序算法：一是归并排序，二是快速排序。

下面，我们来看一看这两个高效的排序算法是如何工作的。

首先是归并排序。它的算法流程描述如下：

假设待排序的数据序列中有n个数据， 可以先将序列看成是由n个长度为1 的有序子序列组成

n 然后再两两子序列合并， 得到一个n/2个长度为2或1 （当序列中数据为奇数时会有一个子序列长度为1 ） 的有序子序列，

n 再两两子序列合并， 如此重复， 直到得到一个长度为n的有序序列为止

为了更清晰地理解归并排序的流程，我们来看一个例子。

我们来看看利用归并排序算法排序83，84，87，88，61，50，70，60，80，99这10个数的流程：（注：以下分号分割每一组数据，逗号分割组内数据）

首先，进行2个数合并排序，得到：83，84 ；87，88；50，61；60，70；80，99；

其次，进行4个数合并排序，得到：83，84，87，88；50，60，61，70；80，99；

接着，进行8个数合并排序，得到：50，60，61，70，83，84，87，88；80，99；

最后，将剩下的2个子序列合并排序，得到：50, 60, 61, 70, 80, 83, 84, 87, 88, 99。

那么，这样的排序流程如何用代码来实现呢？

这个过程与递归相似，但不完全一致，所以需要通过一定的转化，才能利用递归实现归并排序算法。

递归程序，无非要找两个东西。一是初始条件，二是能够将原问题化为更小子问题的递推公式。在归并排序中，这两个东西对应着什么呢？

仔细观察上述归并排序的过程，我们发现这个过程是一个不断合并的过程，所以我们可以先写一个函数，来实现合并两个内部已经有序的数据序列。有了这个函数的支持，我们下一步就需要将原问题化为更小的子问题。这里，一种解决方案是将原数据序列不断划分为左一半和右一半，然后再利用合并函数将它们合并即可。那么什么时候到达划分的终点呢？根据排序这个问题，我们很容易发现，当数据序列中的元素只有一个时，便达到划分的终点。

根据上述讨论，简单总结一下便是：对原序列划分成左半部和右半部后再合并，是归并排序的原问题化简的方法；数据序列中只剩下一个元素时，划分到达终点，这也是该递归程序的初始条件。

了解了这些，代码也就很容易写了。

它的代码实现如下：

def merge(lst1,lst2):
    """
    merge:
     对于内部已经从小到大排序的两个列表，把它们合并成一个从小到大排序的列表
    参数：
     lst1：内部已经从小到大排序的数据列表1
     lst2：内部已经从小到大排序的数据列表2
    返回：
     两个列表的合并结果（结果从小到大排序）
    """
    lst = lst1#合并后的lst
    while len(lst2) != 0:
        a = lst2.pop(0)#取出lst2中第一个元素，并且将它从lst2中删除
        place = len(lst)#记录元素a插入结果lst的位置
        lst.append(a)#将a插入到lst末尾
        for i in range(len(lst1)-1,-1,-1):#寻找大小顺序合适的位置插入元素a，保证lst从小到大排列
            if a < lst[i]:
                lst[i+1] = lst[i]
                place = i
        lst[place] = a
    return lst

def merge_sort(lst):
    """
    merge_sort:
     利用归并排序使得列表中的数据从小到大排列
    参数：
     lst：待排序的数据列表
    返回：
     从小到大排序的数据列表
    """
    if len(lst) == 1:#当数据列表中只有一个元素时，这个列表已经有序，直接返回该列表
        return lst
    else:
        #分解子问题，对原lst排序，相当于对当前lst的左一半和右一半做排序
        lst1 = merge_sort(lst[:len(lst)//2])#左一半的有序数据列表
        lst2 = merge_sort(lst[len(lst)//2:])#右一半的有序数据列表
        return merge(lst1,lst2)#将两个有序列表合并

# 测试用例
print(merge_sort([83,84,87,88,61,50,70,60,80,99]))

"""
输出结果:
[50, 60, 61, 70, 80, 83, 84, 87, 88, 99]
"""

接着，我们来看一看快速排序。

快速排序的中的分治思想也是将原数据序列做划分，但是它在排序过程中又与归并排序有些不同。归并排序首先让每一个子序列内部有序，但外部整体无序；然后再通过合并子序列，使得整体有序。快速排序则是首先让数据外部整体有序，但内部无序；之后利用同样的方法使得子序列内部有序，再将它们按照外部整体有序时的顺序合并即可。

那么快速排序算法是怎样实现外部整体有序的呢？快速排序每次选择一个枢轴（ \(pivot\) ）元素，将当前数据序列中剩下的所有比枢轴元素小的组成一个新的数据序列（假设名字为 \(l\) ）、所有比枢轴元素大的组成一个新的数据序列（假设名字为 \(g\) ），那么 \(l\) ， \(pivot\) ， \(g\) 三个子序列在外部便已经有序。如何解决 \(l\) 、 \(g\) 两个子序列内部无序的的问题呢？对子序列利用快速排序的思想即可。比如在 \(l\) 中选择枢轴元素，将 \(l\) 划分成 \(ll\) （比 \(ppivot\) 小的）、 \(ppivot\) （枢轴元素）、 \(gg\) （比 \(ppivot\) 大的）三部分···经过不断的划分，最终我们会使得序列中的元素个数小于2个，这也就是我们划分的终点。

有了上述的讨论，我想下面的代码也会很容易理解吧。

def quick_sort(lst):
    """
    quick_sort:
     利用快速排序使得列表中的数据从小到大排列
    参数：
     lst：待排序的数据列表
    返回：
     从小到大排序的数据列表
    """
    #如果列表元素只有1个或者没有，
    #那么其本身已经有序，不需要任何额外操作，
    #直接返回即可
    if len(lst) == 1 or len(lst) == 0:
        return lst
    else:
        pivot = lst[0]#选定当前lst的第一个元素为枢轴元素（基准）
        lst_l = [i for i in lst[1:] if i < pivot]#在lst中抽取所有比枢轴元素小的元素构成列表lst_l
        lst_g = [i for i in lst[1:] if i > pivot]#在lst中抽取所有比枢轴元素大的元素构成列表lst_g

        #lst_l、pivot、lst_g已经相对有序，但是lst_l、lst_g内部无序，
        #所以需要分别对lst_l、lst_g执行快速排序，使其有序
        #最后将结果合并即可
        return quick_sort(lst_l) + [pivot] + quick_sort(lst_g)

# 测试用例
print(quick_sort([83,84,87,88,61,50,70,60,80,99]))
"""
输出结果:
[50, 60, 61, 70, 80, 83, 84, 87, 88, 99]
"""

归并排序和快速排序在排序算法中是比较高效的算法。它们究竟有多快呢？我们来一起分析一下他们呢的时间复杂度。

首先假设问题规模为 \(N\) ，所需要的执行步骤为 \(T ( N )\) 。在归并排序中，程序第36行和37行将问题分解为左右一半，第38行的合并相当于将两个子序列都遍历了一遍（每个子列的规模为 \(\frac{N}{2}\) ），所以有如下递推公式：

\[ \begin{aligned} T(N) &= 2T(N/2) + N / 2 + N / 2\\ &=2T(N/2) + N \end{aligned} \]

进一步递推可得， \(T(N) = N\cdot T(1) + k\cdot N\) ，其中 \(k = log_{2}(N)\) 。当数据规模为1时，解决问题的步骤显然只需一步，所以 \(T(N) = N + N\cdot log_{2}(N)\)，所以归并排序的时间复杂度为 \(O( N\cdot log( N ) )\) 。

快速排序中，子序列的划分并不像归并排序那么确定（因为枢轴元素的选取会影响快速排序中子列的划分），同时快速排序的时间复杂度也有多种情况。最好的情况，枢轴元素恰巧是该序列的中数（也就是排序后，该数的位置在序列的中间），第一层快速排序会使得枢轴元素两端的子序列的个数相差不大。这种情况就相当于把原序列对半划分，和归并排序十分类似。分析一下，这种情况下快速排序的时间复杂度和归并排序一样，为 \(O( N\cdot log( N ) )\) ；最坏的情况，枢轴元素是原序列中最小的元素或者是最大的元素，他将原序列划分为两个十分不平衡的子序列，一边没有元素，而另一边含有所有剩下的元素。对于这种情况，我们有如下递推公式：

\[ T(N) = T(N-1) + N\\ 其中,T(N-1)为解决子问题的时间，N为合并时间 \]

递推下去，可得 \(T(N) = T(1) + N\times N = N^{2} + 1\) ，所以时间复杂度为 \(O( N^{2} )\) 。平均情况下，枢轴元素的选取不会总是最坏情况，大多数情况下都是 \(O( N\cdot log( N ) )\) 。

文章的最后，我们简单总结一下本文的内容：

1. 分治是一种解决问题的方法，他通过不断将原问题分解成相似的、更小的、更以解决的子问题，并通过可以直接看出结果的子问题的答案，逐层回代解决原问题。
2. 分治解决问题的一般步骤：找到显而易见的子问题的解；分解原问题到子问题，通过子问题的解解决原问题。
3. 分治的方法可以利用递归程序实现。
4. 分治思想下有两种十分高效的排序算法：一是归并排序，二是快速排序。
5. 归并排序的流程：将原序列不断对半划分，直至其中元素只剩1个返回，然后逐层将左右子序列合并即可。
6. 快速排序的流程：将原序列利用枢轴元素划分，比枢轴元素小的为一个子序列，比枢轴元素大的为另一个子序列，直至其中元素只剩1个返回，然后将这些子序列逐层合并即可。
7. 归并排序的时间复杂度为 \(O( N\cdot log( N ) )\) 。
8. 快速排序的最好时间复杂度为 \(O( N\cdot log( N ) )\) ，最坏时间复杂度为 \(O( N^{2} )\) ，平均时间复杂度为 \(O( N\cdot log( N ) )\) 。