这个lec主要讲排序算法，首先从list的实现开始。Python中的list显然是可变的，可以自由地向其中添加、删除各种类型的元素，然后有可以使用下标来查找，有些类似于Java中的list。Python中的List显然不能用连续的内存空间来实现，因为存储在list中的元素可以类型不同，使用链表的方式可以解决这个问题，但存在效率问题，例如查找list aList中的第199个元素aList[198]，则需要链接198次才能得到。如果纯数组和纯链表不能解决这个问题，那么将二者结合起来，则可以形成一个比较好的解决方案。Python中List的实现如下图所示：

此lec的其他部分主要集中在常用排序算法的讲解上，贴代码看看就好了：

def bSearch(L, e, low, high):    if high - low < 2:        return L[low] == e or L[high] == e    mid = low + int((high - low)/2)    if L[mid] == e:        return True    if L[mid] > e:        return bSearch(L, e, low, mid - 1)    else:        return bSearch(L, e, mid + 1, high)def selSort(L):    """Assumes that L is a list of elements that can be compared       using >.  Sorts L in ascending order"""    for i in range(len(L) - 1):        #Invariant: the list L[:i] is sorted        minIndx = i        minVal= L[i]        j = i + 1        while j < len(L):            if minVal > L[j]:                minIndx = j                minVal= L[j]            j += 1        temp = L[i]        L[i] = L[minIndx]        L[minIndx] = temp        print 'Partially sorted list =', L##L = [35, 4, 5, 29, 17, 58, 0]##selSort(L)##print 'Sorted list =', Ldef merge(left, right, lt):    """Assumes left and right are sorted lists.     lt defines an ordering on the elements of the lists.     Returns a new sorted(by lt) list containing the same elements     as (left + right) would contain."""    result = []    i,j = 0, 0    while i < len(left) and j < len(right):        if lt(left[i], right[j]):            result.append(left[i])            i += 1        else:            result.append(right[j])            j += 1    while (i < len(left)):        result.append(left[i])        i += 1    while (j < len(right)):        result.append(right[j])        j += 1    return result            def sort(L, lt = lambda x,y: x < y):    """Returns a new sorted list containing the same elements as L"""    if len(L) < 2:        return L[:]    else:        middle = int(len(L)/2)        left = sort(L[:middle], lt)        right = sort(L[middle:], lt)        print 'About to merge', left, 'and', right        return merge(left, right, lt)##L = [35, 4, 5, 29, 17, 58, 0]##newL = sort(L)##print 'Sorted list =', newL##L = [1.0, 2.25, 24.5, 12.0, 2.0, 23.0, 19.125, 1.0]##newL = sort(L, float.__lt__)##print 'Sorted list =', newLdef lastNameFirstName(name1, name2):    import string    name1 = string.split(name1, ' ')    name2 = string.split(name2, ' ')    if name1[1] != name2[1]:        return name1[1] < name2[1]    else:        return name1[0] < name2[0]def firstNameLastName(name1, name2):    import string    name1 = string.split(name1, ' ')    name2 = string.split(name2, ' ')    if name1[0] != name2[0]:        return name1[0] < name2[0]    else:        return name1[1] < name2[1]##L = ['John Guttag', 'Tom Brady', 'Chancellor Grimson', 'Gisele Brady',##     'Big Julie']##newL = sort(L, lastNameFirstName)##print 'Sorted list =', newL##newL = sort(L, firstNameLastName)##print 'Sorted list =', newL

在上面的代码中，有一个很有趣的代码段：

def sort(L, lt = lambda x,y: x < y):

其中，lt = xxxx的意思是lt参数的默认值为lambda x, y: x < y。这里的lambda是Python函数式编程风格的一个体现，下面这段关于lambda的介绍是从这里节选过来的：

Python 支持一种有趣的语法，它允许你快速定义单行的最小函数。这些叫做 lambda 的函数，是从 Lisp 借用来的，可以用在任何需要函数的地方。

例 4.20. lambda 函数介绍

>>> def f(x):...     return x*2...     >>> f(3)6>>> g = lambda x: x*2  >>> g(3)6>>> (lambda x: x*2)(3) 6

	这是一个 lambda 函数，完成同上面普通函数相同的事情。注意这里的简短的语法：在参数列表周围没有括号，而且忽略了 return 关键字 (隐含存在，因为整个函数只有一行)。而且，该函数没有函数名称，但是可以将它赋值给一个变量进行调用。
	使用 lambda 函数时甚至不需要将它赋值给一个变量。这可能不是世上最有用的东西，它只是展示了 lambda 函数只是一个内联函数。

总的来说，lambda 函数可以接收任意多个参数 (包括) 并且返回单个表达式的值。lambda 函数不能包含命令，包含的表达式不能超过一个。不要试图向 lambda 函数中塞入太多的东西；如果你需要更复杂的东西，应该定义一个普通函数，然后想让它多长就多长。