算法导论--分治策略

概述

　　算法中有两个非常重要的思想分别是：分治策略和动态规划。它们通常可以将处理复杂的问题，转化为处理Ｎ个相关的子问题。通过这种方式，给予人们清晰的思路的同时，降低处理问题的难度。这一篇文章我们来介绍分治策略，并给出几个经典的算法来进行展示。

简介

　　分治策略中，往往是通过递归去求解问题，并在每层递归中应用如下三个步骤:

1. 分解:将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
2. 解决:递归的求解子问题，如果子问题的规模足够小，则停止递归，直接求解。
3. 合并:讲子问题的解组合成原问题的解。

算法举例

　　在上一篇文章里，我们看到的归并排序其实使用的就是分治思想。这里我们再列举两个常用的，并且使用分治思想的算法:堆排序和快速排序。

堆排序

　　堆排序的时间复杂度为O(nlogn)，并且所需的额外存储数量固定。堆通常使用数组进行存储，它可以被看成一个近似的完全二叉树，它的每一个节点对应着数组中的一个元素。接下来我们试着去实现堆排序。
　　首先我们来理解一下最大堆。如果按照刚才我们所提到的，将堆看做成二叉树。那么如果是最大堆，其特点是A[PARENT(i)]>=A[i]。这个公示代表着，任何一个节点不大于其父节点。这里我们用伪代码表示一下父节点和左右子节点的关系。

PARENT(i)
        return [i/2]
LEFT(i)
        return 2i
RIGHT(i)
        return 2i+1

　　接下来我们讨论一下堆排序算法。堆排序的一个重要环节是调节堆。详细的说，比如我们目标是构建最大堆，在Ｎ个节点的树中总会有不满足最大堆要求的父子节点关系，那么我们就要进行调整。
　　堆排序的第一个环节就是构建最大堆。这里我们假设某个节点的两个子节点都已经是最大树的根节点，在这种情况下，再对该节点进行调整是最容易的。所以我们构建最大堆的思路是先讲子树构建成最大堆，然后开始父节点构建。这样我们将会完成最大堆的构造。然而，这里大家一定要注意，最大堆构建完成并不代表着数组已经排序完成。比如(16,14,10,8,7,9,3)就是最大堆，但是并不是有序的。它只保证了其父节点不小于该节点。
　　最后我们来完成排序工作。具体的步骤就是，讲根节点与最后一个节点交换，并从树种去除，然后对树进行调整。不断的迭代这个过程，完成最终的排序工作。
　　这里开始为自己的表达能力感到捉急。我们还是来看伪代码吧。

//第一步，调整堆
MAX-HEAPIFY(A,i)
        l = LEFT(i)
        r = RIGHT(i)
        largest = i
        if l <= heapsize and A[l] > A[i]
                largest = l
        if r <= heapsize and A[r] > A[i]
                largest = r
        if largest != i
                exchange(A[i],a[largest])
                MAX-HEAPIFY(A,largest)

　　第一步，通过递归来调整以i为根节点的子树为最大堆。以此为基础，我们讲堆从子节点向上遍历，不断地调整子树为最大树来完成最大堆的构建。

//第二步，构建最大堆
BUILD-MAX-HEAP(A)
        A.heapsize = A.length
        for i = [A.length/2] downto 1
                MAX-HEAPIFY(A,i)

　　在完成最大堆的构建之后，我们已经完成了堆排序最核心的两个步骤，那么我们现在完成堆排序。

//堆排序
HEAP-SORT(A)
        BUILD-MAX-HEAP(A)
        for i = A.length downto 2
                exchange A[i] with a[i]
                A.heapsize = A.heapsize-1
                MAX-HEAPIFY(A,1)

　锵锵锵锵，堆排序完成。

快速排序

　　另一个使用分治思想的常用算法就是快速排序。快速排序的期望时间复杂度是O(nlogn)。但是最坏情况的时间复杂度又O(n*n)。虽然看起来最坏情况的时间复杂度很差，但是实际排序应用中它往往是最好的选择，因为它的平均性很好，而且O(nlogn)的常数因子非常小。
　　快速排序的三步分治过程:

1. 分解:　将数组A[p..r]，以A[q]为界换分为两个子数组，子数组可以为空,q可以自由选择。使得A[p..q-1]中的元素都小于A[q],A[q+1..r]中的元素都大于A[q]。
2. 解决:　通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序
3. 合并: 因为子数组都是原址排序，所以不需要合并操作:数组A[p..r]已经有序

　　来看具体的伪代码实现:

PARTITION(A,p,r)
        x = A[r]
        i = p - 1
        for j = p to r - 1
                if A[j] <= x
                        i = i + 1
                        exchange A[i] with A[j]
        exchage A[i+1] with A[r]
        return i + 1

　　在快速排序中，PARTITION是非常关键的部分，它的作用有两个，第一个是选定界限值q，第二个就是对输入数组进行原址重排。

QUICKSORT(A,p,r)
        if p < r
                q = PARTITION(A,p,r)
                QUICKSORT(A,p,q-1)
                QUICKSORT(A,q+1,r)

　　快速排序完成