上一节课我们已经讲了算法的基础知识，这节课我们讲一下算法中两个最为经典的类型：排序算法和查找算法。排序和查找我们之前直接使用列表的内置方法，那实现排序和查找最底层的原理是什么呢？我们正式开始这节课的内容吧。

一、排序算法

1.1 冒泡排序

冒泡排序是最简单的一种排序方法，它的原理是将一列数据中较大（或较小）的数据逐次向右推移的一种排序方法。冒泡排序分为内外两层循环。外层是总共要跑的遍数，2个数据比较一遍，3个数据比较一遍，以此类推，n个数据就跑了n-1遍。内层循环真正比较数据。以升序为例，每次比较把较大的放到后面。由于每一遍都是将本遍最大的数据移动到最右边。就像是水中的气泡一样，小的气泡上升，就排到最上面，就像是“冒泡”一样，所以我们称它为冒泡排序。

下面我们以升序为例，讲一下冒泡排序的基本思想：

第一遍从第1个元素开始，让它和第2个元素进行比较，如果大数在前就交换；然后让2个元素和第3个元素比较，大数在前就交换；依次类推，直到比较完最后一个元素为止。第一遍排序结束时，最后一个元素是所有元素中的最大值。

第二遍从第一个元素开始，让它和第2个元素进行比较，如果大数在前就交换；然后让2个元素和第3个元素比较，大数在前就交换；依次类推，直到比较到倒数第二个元素为止。第二遍排序结束时，倒数第二个数为第二大的数。

……

n个数排序共需要n-1遍。

我们看一下模拟的实例：

3 9 2 1 6 原始数据
3 9 2 1 6 将3和9比较，不交换位置
3 2 9 1 6 将9和2比较，交换位置
3 2 1 9 6 将1和9比较，交换位置
3 2 1 6 9 将9和6比较，交换位置。第一轮结束
2 3 1 4 9 将3和2比较，交换位置
2 1 3 4 9 将3和1比较，交换位置
2 1 3 4 9 将3和4比较，不交换位置。第二轮结束
……

下面我们看一下冒泡排序的Python代码实现：

a = [3, 9, 2, 1, 6]
count = len(a)
for i in range(0, count - 1): # 外层循环
    for j in range(0, count -1 - i): # 内层循环
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j] # 两个数交换
print(a) 

1.2 选择排序

选择排序对冒泡排序的改进。选择排序是在参加排序的所有元素中找出数值最小或最大的元素，如果它不是左侧第一个元素，就让它和左侧第一个元素交换位置；然后在余下的元素中找出数值最小或最大的元素，如果它不是左侧第二个元素，就与左侧第二个元素交换位置；……依次类推，直到所有元素构成有序的序列。

比起冒泡排序，选择排序更符合人们日常的排序习惯。它的比较次数与冒泡排序相通，但是交换的次数比冒泡排序要少，因此具有更高的效率。

下面我们以升序为例，讲一下选择排序的基本思想：

第一遍从第1个元素到第n个元素中找出一个最小的元素，如果它不是第1个元素，就让它和第1个元素交换位置。第一遍排序结束时，第1个元素为所有元素中的最小值。

第二遍从第2个元素到第n个元素中找出一个最小的元素，如果它不是第2个元素，就让它和第2个元素交换位置。第二遍排序结束时，第2个元素为所有元素中第二小的值。

……

下面我们看看如何实现最小元素的交换位置：

第i遍排序开始时，先假设第i个位置上的数是最小的数，用k标记。让k位置上的数(a[k])与i后面的数(a[j])逐个比较，当找到一个比k位置上小的数，用k记录j的值。当j到达最后一个数时，一遍比较结束，k指向最小的数，即k记录最小的数的位置。当i≠k时，交换a[i]与a[k]的值。

我们看一下选择排序的Python代码实现：

a = [3, 9, 2, 1, 6]
count = len(a)
for i in range(0, count - 1):
    k = i
    for j in range(i + 1, count):
        if a[k] > a[j]:
            k = j
    if k != i:
        a[k], a[i] = a[i], a[k] 
print(a)

1.3 插入排序

插入排序是先将待排序的数列中的第1个元素看成一个有序的子数列，然后从第2个元素开始，将数据逐个插入这个有序的子数列中，以此类推到最后一个数据。整个排序的过程类似于玩扑克牌时一边抓牌一遍理牌的过程，每抓一张牌就把它插入到应有的位置上。

插入排序的整个过程如下图所示：

第1次插入，将第2个元素与第1个元素比较。先将要插入到数a[1]放入一个空的变量key；将key与前面已经排好序的元素比较，如果key<a[0]成立，说明key要插入到a[0]前面，将a[0]向后移动一个位置，放到a[1]中，再将key放到a[0]中；如果key<a[0]不成立，说明key要插入到a[0]后面，放key放入到a[1]的位置中。

第2次插入，前面两个元素已经排好序，将第3个元素放入一个空的变量key，将key与前面排好序的元素比较，再将它插入对应的位置中。

……

依次类推。

我们看一下插入排序的Python代码实现：

a = [3, 9, 2, 1, 6]
count = len(a)
for i in range(1, count):
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j+1] = a[j]
        j -= 1
        a[j+1] = key
print(a)

1.4 其他排序算法

以上三种排序的算法外，还有归并排序、快速排序、堆排序、计数排序、桶排序、希尔排序等等，快速排序的思想下节课我们会讲解，归并排序这里就略去不讲了，大家可以自己研究。别的排序算法相对较为复杂，目前阶段不需要大家掌握。有兴趣的同学可查阅相关资料。

相对好理解一些的是归并排序（暂时不需要掌握代码），大家可以看动画的图片做相应的理解：

二、查找算法

2.1 顺序查找

顺序查找是一种最为常用的查找算法。我们生活中也经常会用到，比如我们要从一堆书里面找到我们想要的书，我们会从第一本开始一本一本地看，直到找到我们想要的那本书。

顺序查找的基本思想是从第一个元素开始，按顺序逐个将数据与给定的数据进行比较，如果某个数据与给定的数据相等，则查找成功，输出所查数据；反之则未找到。

顺序查找的代码使用Python实现也非常简单：

data = [12, 23, 1, 89, 34, 13, 78, 67, 54]
key = 34 # 要查找的元素
x = -1 # 要查找元素的索引
count = len(data)
for i in range(0, count):
    if data[i] == key:
        x = i
        break
if x == -1: # -1代表元素未找到
    print('元素不存在')
else:
    print(x)

2.2 对分查找

对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是被查找的序列是有序的。

我们思考一个问题，从1到100中随机一个数字，猜出这个数是多少。如果我们从1开始一个个往后猜，每次只能排除一个数字，最坏的情况我们可能要猜100次。但是如果第一次猜50，告诉你大了或者小了。下次再猜25，再下次猜12，以此类推，不管是哪个数字，最多7次之内就能猜出来了。这样比起顺序查找要省了很多的时间。这就是对分查找算法。

我们看看对分查找的思路：

如果key是我们需要查找的值，列表a中存放了n个已经升序排列的元素，m为查找范围[i, j]的中间位置。我们查找的过程中必然是以下三种情况之一：

1. 如果key < a[m]，key在前半部分，新的查找范围在[i, m-1]中
2. 如果key = a[m]，找到需要对数据
3. 如果key > a[m]，key在后半部分，新的查找范围在[m+1, j]中

我们看一下对分查找的Python代码实现：

data = [2, 34, 36, 47, 51, 53, 59, 62, 75, 79, 82]
key = 47  # 需要查找的元素
count = len(data)
i, j = 0, count - 1
x = -1
while i <= j:
    m = (i + j) // 2
    if key == data[m]:
        x = m
        break
    elif key > data[m]:
        i = m + 1
    else:
        j = m - 1
if x == -1:
    print('未找到元素')
else:
    print(x)

三、课后思考题

1、选择题

列表l = [9, 2, 8, 6, 3, 4]，采用选择排序进行升序排序，第二遍排序之后的结果是（）

A. [2, 3, 8, 6, 9, 4]

B. [2, 8, 6, 3, 4, 9]

C. [2, 6, 3, 4, 8, 9]

D. [2, 3, 4, 6, 8, 9]

2、选择题

列表l = [5, 2, 6, 3, 7]，利用插入排序进行升序排序，第二次插入排序的结果是（）

A. [5, 2, 3, 6, 7]

B. [2, 5, 3, 6, 7]

C. [2, 5, 6, 3, 7]

D. [2, 3, 5, 6, 7]

3、选择题

某个列表中有7个元素，依次为19、28、30、35、39、42、48。如果采用对分查找法在列表中查找元素48，需要查找的次数是（）

A. 1 B. 2 C. 3 D. 4

四、上节课思考题答案

1、C

2、C

3、参考代码

n = 0 # 统计个数
for i in range(100, 1000):
    a = i // 100 # 百位数
    b = i % 100 // 10 # 十位数
    c = i % 10 # 个位数
    if a ** 3 + b ** 3 + c ** 3 == i:
        n += 1
        print(i)
print("合计个数：", n)