分而治之算法是递归的。使用分而治之解决问题的过程包括两个步骤。
(1) 找出基线条件,这种条件必须尽可能简单。
(2) 不断将问题分解(或者说缩小规模),直到符合基线条件。
能够不断缩小问题的规模,并且有终止的条件是分而治之的核心。在这样的方案构建过程中,归纳证明非常重要。

练习1、使用递归分而治之的方法计算2,4,6的和。



本图来自《算法图解》

def Sum( array ):
    if( 0 == len(array) ):
        return 0
    if( 1 == len(array) ):
        return array[0]
    firstOne = array.pop( 0 )
    return firstOne + Sum( array )

print( Sum([ 2, 4, 6 ]) )

练习2、找出列表中最大的数字。
注意python中的三元运算符,这和C++有所不同。

def Max( array ):
    if( 1 == len(array) ):
        return array[0]
    if( 2 == len(array) ):
        return (( array[1], array[0] )[array[0] > array[1]])
    A = array.pop(0)
    result = Max( array )
    return (result, A)[A > result]

print( Max([ 2, 4, 6 ]) )

练习3、实现快速排序

def quickSort( arr ):
    if( len(arr) < 2 ):
        return arr
    else:
        smaller = [ i for i in arr[1:] if i <= arr[0] ]
        greater = [ i for i in arr[1:] if i > arr[0] ]
        return quickSort( smaller )+[ arr[0] ] + quickSort( greater )

print( quickSort([ 10005, 30007, 40008, 20001 ]) )

练习4、实现归并排序(merge sort)

def mergeSort( arr ):
    if len( arr ) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        mergeSort( L )
        mergeSort( R )

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i = i + 1
            else:
                arr[k] = R[j]
                j = j + 1
            k = k + 1

        while i < len(L):
            arr[k] = L[i]
            i = i + 1
            k = k + 1
        while j < len(R):
            arr[k] = R[j]
            j = j + 1
            k = k + 1

arrList = [ 10005, 30007, 40008, 20001 ]
mergeSort( arrList )
print( arrList )

分类: Algorithm

发表评论

电子邮件地址不会被公开。 必填项已用*标注