计算机科学及编程导论(麻省理工)

Lecture 9: Binary search, bubble and selection sorts

本课前半部分重温了上节课略过的二分法搜索，后半部分开始讲排序问题，并举了两个最经典但是最没有效率的两种排序，冒泡排序和选择排序。

鉴于上节课最后已经提到过了二分法搜索，那么这里就不再累述具体细节，标程也可以从上节课的笔记中找到。

但是这里必须要提到的，是二分法的通用模板(Template/generalizing binary search)，这个模板是一个简单的分治法(Divide and conquer method)，在下节课会讲到。那么，二分法的模板如下：

• 找到数据的中点
• 检查是否是符合要求的答案
• 如果不是，那么就将问题规模缩小，重复相同的操作

（注意：运用此模板可以讲问题规模以常数倍逐次缩小，从而大大提高运算效率）

本课后半节讲到了排序，并举了排序中最经典，最简单，但也是效率最低的两种排序——选择排序和冒泡排序。可以说，这两种排序的思路有类似之处，复杂度都为二次方级，即O(n^2)。那么下面我就会给出这两种排序的标程，当然初学者也可以自己尝试：

例1：选择排序

def selectSort(L):

    for i in range(len(L)-1):

         minIndex = i

         minVal = L[i]

         j = i + 1

         while j < len(L):

              if minVal > L[j]:

              minIndex = j

              minVal = L[j]

              j = j + 1

         temp = L[i]

         L[i] = L[minIndex]

         L[minIndex] = temp

    return L

选择排序的算法思想是这样的：取minIndex表示最小值的元素号码，取minVal表示最小值的值。每次循环中找出最小值存入minVal，其元素号码存入minIndex，然后交换数据。第一次循环找出最小的数，第二次找出第二小的数，依此类推。

例2.1：冒泡排序

def bubbleSort1(L):

     l = len(L) - 2

     i = 0

     while i < l:

           j = l

           while j >= i:

                  if L[j + 1] < L[j]:

                  L[j], L[j + 1] = L[j + 1], L[j]

                  j -= 1

           i += 1

     return L

冒泡排序的算法思想是这样的：每次从最后开始往前滚，邻接元素两两相比，小元素交换到前面。第一轮循环把最小的元素上浮至第一位置，第二小的元素上浮至第二位置，依此类推。

例2.2：冒泡排序（优化）

def bubbleSort2(L):

     sort = True

     while sort:

            sort = False

            for i in range(len(L) - 1):

                    if L[i] > L[i + 1]:

                            L[i + 1], L[i] = L[i], L[i + 1]

                            sort = True

     return L

这里优化之处在于：当for循环中没有交换时，列表则被视为已经排好，则不再进行多余的操作。

在本课中还需要提到的一个知识点是循环不变量(Loop Invariant)，这表示在循环结构中每次循环都为真的属性。在这些排序中，循环不变量是这样的：

• 列表被分为两部分：前半部分已经被排好，后半部分则是未排好的
• 每次循环被排好的部分不变，但是规模+1，直到后半部分什么都不存在，而整个列表都被排好

（注意：对于循环不变量的具体证明，各位可以参考《算法导论》第二章算法入门，有详细解释）

总结：这里介绍的两种排序都不常用，因为效率太低，但是对于初学者来说，这是排序入门的两个例子。