Lecture 10: Divide and conquer methods, merge sort, exceptions
本课前半部分由二分法引申到分治法，再应用分治法到排序之中并以归并排序为例。课程后半部分提出了哈希算法，一种以空间换速度的经典算法。最后简要介绍了异常处理的except语法。
根据《算法导论》第2章算法入门所述，有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题。这些算法通常采用分治策略(Divide and conquer method)：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治模式在每一层递归上都有三个步骤：
- 分解(Divide)：将原问题分解成一系列子问题；
- 解决(Conquer)：递归地解各子问题。若子问题足够小，则直接求解；
- 合并(Combine)：将子问题的结果合并成原问题的解。
（注意：以上对于分治法的解释和定义均来源于《算法导论》）
在本课程中，对于分治法的定义和解释基本与算法导论中的说法相同，因此便不再累述。
对于归并排序(Merge sort)，则完全依照了分治模式，即上述模式，直观地进行如下操作：
- 分解：将n个元素分成各含n/2个元素的子序列；
- 解决：用归并排序法对两个子序列递归地排序；
- 合并：合并两个已排序的子序列已得到排序结果。
归并排序的思路非常简单，试想我们有两叠已经排好的扑克牌，假设每叠有4张。
第一叠：[1, 2, 4, 8]
第二叠：[3, 5, 6, 7]
那么我们是怎么理牌的呢？假设两叠拍都是最小的牌朝上，那么第一张牌是1，因为1<3，第二张牌是2，因为2<3，第三张牌是3，因为3<4，依次类推。
根据这样的思路，我们可以有如下归并排序的Python标程：
import sys
def Merge(nums, first, middle, last):
""" This function is used to merge two ordered lists """
n1 = middle - first + 1
n2 = last - middle
lnums = nums[first:middle+1]
rnums = nums[middle+1:last+1]
lnums.append(sys.maxint)
rnums.append(sys.maxint)
p = 0
q = 0
for i in range(first, last+1):
if lnums[p] < rnums[q]:
nums[i] = lnums[p]
p += 1
else:
nums[i] = rnums[q]
q += 1
（注意：其中lnums.append(sys.maxint)和rnums.append(sys.maxint)的思想在于：有可能两叠牌的数量是不一样的，一叠有3张，一叠有4张，那3张的排完了，4张的怎么办？这时候，4张的那叠剩下的牌就和3张的那叠最后一张哨兵牌相比。哨兵牌是在每叠牌最后放上的一个足够大的数，例如无限。这样就可以确保所有牌都有效归序）
然而，Merge这个函数只解决了一个子问题，即合并两个以排好的序列，那么还有前两步，即分解和解决。因此，我们可以写出一个递归函数，Python标程如下：
def MergeSort(nums, first, last):
""" This function is used to sort unordered lists by merge sorting """
middle = 0
if first < last:
middle = (first + last) / 2
MergeSort(nums, first, middle)
MergeSort(nums, middle + 1, last)
Merge(nums, first, middle, last)
return nums
那么将两个函数放到一起，我们就可以用归并排序的方法去排列一个无序数组了。归并排序的算法复杂度要比上节课所提到的冒泡排序和选择排序低得多，即O(n logn)。可以说，归并排序的效率大大提高了。
本课后半部分提到了哈希算法(Hashing Algorithm)，这是一个用空间（即计算机内存）换时间（即计算速度）的算法。下面有两个例子：
例1：储存一组正整数，搜索某一数是否存在，存在为真(True)，不存在为假(False)
def create(smallest, largest):
intSet = [None] * (largest + 1)
return intSet
def insert(intSet, e):
intSet[e] = 1
def search(intSet, e):
return intSet[e] == 1
例2：储存字符，并搜索。
def hashChar(c):
# c is a character
# function returns a different integer in the range 0 - 255 for each possible value of c
return ord(c)
def cSetCreate():
cSet = []
for i in range(256):
cSet.append(None)
return cSet
def cSetInsert(cSet, e):
cSet[hashChar(e)] = 1
def cSetSearch(cSet, e):
return cSet[hashChar(e)] == 1
根据上面的两个例子，不难看出，哈希算法的思路在于：
- 创键一个很长的序列，每一个位置代表一个数，比如数列的第一个数代表0，第二个数代表1，以此类推。
- 如果数0储存进数列的话，则在数0，即数列第一个的位置做上记号（这里是赋值为1，当然也可以赋值为真）
- 搜索时只需要查看在所对应位置上的值是否被标注过记号，即是否为1，那么就可以知道是否存在这个数了
不难想到，这个算法的复杂度为常数，即O(c)，c为常数。那么这个算法的速度是非常快的，而且无论输入值的大小如何，运算速度都是一样的。
但是这时，也不难看出这种算法有一个致命的缺陷：如果输入值非常大，此算法会占据大量的存储空间。因此，空间与时间，这种权衡就由程序设计者考虑了。
最后一个话题为异常处理，即except的用法。这里最主要的是try-except的格式，如下：
try:
block of code
except:
block of code
具体关于异常处理的系列会在下节课中详细说明，也可以参考Python学习笔记，或者Python基础教程（第二版），都非常有用。
总结：本课主讲分治法和哈希法，都很经典有效，建议听讲。
学员评论