算法导论笔记 第一章 And 第二章

插入排序和抓牌的过程是一样的, 右手抓牌向左手放, 每次抓到新牌都与左手中的牌从右至左比较一番,找到合适的位置放置.循环直到抓完所有牌.
python源码如下: (之后都用python来翻译书中的伪码)

    def isort(a):
        for j in xrange(1, len(a)):
            key = a[j]
            i = j - 1
            while i >= 0 and a[i] > key:
                a[i + 1] = a[i]
                i = i - 1
            a[i + 1] = key
    a = [2,4,6,1,3,7,9,8]
    isort(a)
    print a  

在证明插入排序的时候, 书中提到了 循环不变式(loop invariant), 网上有人说这里应该翻译成循环不变性,是一种属性.”要寻找循环不变的特性,一般都是循环结束时数据具有的特性.” 注:简单说下算法导论中的伪代码, 和python一样的缩进很喜欢, 但是数组下标从一开始有些不习惯, 另外, do关键字让我误以为是do…while循环, 实际上只是和循环语义搭配的关键字.


习题:选择排序(selection sort)

    def ssort(a):
        for i in xrange(0, len(a)):
            key = i
            for j in xrange(i + 1, len(a)):
                if a[key] > a[j]:
                    key = j
            a[key], a[i] = a[i], a[key]
    
    a = [2,6,9,11,3,8,1,12,11,102]
    ssort(a)
    print a 试着用循环不变性分析一下:   最终排序的结果是有序数组,故循环不变性即有序性.   初始化:只有一个数的情况, 符合有序性.   保持:每个循环都找出当前最小数,也就是上一个循环的次小数,放进数组,故每次循环都保证了有序性.   终止:当i == n-1时, 所有数都重新放进数组,且符合有序性.   (感觉都是废话...  

分治法:将原问题划分成n个规模较小而结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果.合并排序(归并排序)完全依照分治法的模式进行.
分解(Divide)->解决(Conquer)->合并(Combine)
最关键也是相对比较困难的步骤是合并的这个过程.
首先将数组a划分为两个部分a[p…q]和a[q+1…r],分别排序后,合并到一起, 实际上就是合并两个有序数组, 每次从两个数组中最小的一端开始取出相对较小的元素push到新数组中,最后得到有序数组, 书中具体的做法是分别从a[p…q]和a[q+1…r]复制到两个新数组La和Lb, 然后以如上策略从La和Lb中取元素依次放至原数组,从而完成合并,这里似乎较难找到不创建新数组原地合并的方法.代码如下:

    from copy import deepcopy
    def merge(arr, p, q, r):
        n1 = q - p + 1
    	n2 = r - q
    	la = deepcopy(arr[p : q + 1])
    	lb = deepcopy(arr[q + 1 : r + 1])
    	la.append(9999999)
    	lb.append(9999999)
    	i = 0
    	j = 0
    	for k in xrange(p, r + 1):
    		if la[i] >= lb[j]:
    			arr[k] = lb[j]
    			j = j + 1
    		elif la[i] < lb[j]:
    			arr[k] = la[i]
    			i = i + 1

(学到了python中 deepcopy的使用= =
排序函数代码如下:

    def msort(arr, p, r):
        if p < r:
    		q = (p + r) / 2
    		msort(arr, p, q)
    		msort(arr, q + 1, r)
    		merge(arr, p, q, r)

a = [2,4,8,1,6,9,12,11,18,102,35,7,9,8]
msort(a, 0, len(a) - 1)
print a

习题中有个提到冒泡排序的,顺手给写了吧,其他习题暂时不做了. def psort(arr): for i in xrange(0, len(arr)): for j in xrange(len(arr) - 1, i, -1): if arr[j - 1] > arr[j]: arr[j - 1], arr[j] = arr[j], arr[j - 1] arr = [1,2,4,6,5,12,46,13,17,14,7] psort(arr) print arr

Published: August 07 2013