计算机基础课第 30 期分享

转载请联系授权（微信ID：qianpangzi0206）

前两周，我们"初尝"了高级编程语言（比如 Python 和 Java），我们讨论了几种语句 - 赋值语句，if 语句，循环语句，以及把代码打包成 "函数"，比如算指数。重要的是，之前写的指数函数只是无数解决方案的一种，还有其它方案。

01

算法的定义

即使结果一致，有些算***更好，一般来说，所需步骤越少越好。不过有时我们也会关心其他因素，比如占多少内存。

"算法" 一词来自 波斯博识者 阿尔·花拉子密（1000 多年前的代数之父之一）如何想出高效算法 - 是早在计算机出现前就有的问题，从而诞生了专门研究计算的领域，然后发展成一门现代学科—计算机科学！

02

排序算法

记载最多的算法之一是"排序"，排序到处都，比如给名字、数字排序，找最便宜的机票，按最新时间排邮件，按姓氏排联系人等这些都要排序。你可能想"排序看起来不怎么难… 能有几种算法呢?" ，答案是超多。计算机科学家花了数十年发明各种排序算法，还起了酷酷的名字，比如冒泡排序，快速排序，插入排序，归并排序等。

我们来试试排序！试想有一堆机票价格，都飞往  印第安纳波利斯 (美国地名)。

上图的这样一组数据  叫"数组"（Array），来看看怎么排序（建议拿出笔和纸跟着说明来排序），先从一种简单算法开始，先找到最小数，从最上面的 307 开始，因为现在只看了这一个，所以它是最小数，下一个是 239，比 307 小，所以新的最小数变成 239。下一个是 214 ，新的最小数，250 不是，384, 299, 223, 312 都不是，现在扫完了所有数字，214 是最小的。

为了升序排列（从小到大排序），把 214 和最上面的数字，交换位置，刚排序了一个数字。现在重复同样的过程，这次不从最上面开始，从第 2 个数开始，先看到 239，我们当作是 "最小数"，扫描剩下的部分，发现 223 最小，所以把它和第 2 位交换，重复这个过程，从第 3 位数字开始，让 239 和 307 互换位置，重复直到最后一个数字。

数字排好了，可以买机票了！

刚刚这种方法，或者说算法，叫 选择排序 - 非常基础的一种算法

以下是"伪代码"

03

算法复杂度

这个函数可以排序8个, 80个或8千万个数字，函数写好了就可以重复使用。这里用循环遍历数组，每个数组位置都跑一遍循环，找最小数然后互换位置，每个数组位置都跑一遍循环，找最小数然后互换位置，可以在代码中看到这一点（一个 for 循环套另一个 for 循环）。这意味着，大致来说，如果要排 N 个东西，要循环 N 次，每次循环中再循环 N 次，共 N*N,  或 N。算法的输入大小和运行步骤之间的关系叫算法的复杂度，表示运行速度的量级。

计算机科学家们把算法复杂度叫大 O 表示法，算法复杂度 O（N*N）效率不高

前面的例子有 8 个元素（n=8）, 8*8= 64，如果 8 个变 80 个，运行时间变成 80*80 = 6400。虽然大小只增长了 10 倍（8 到 80），但运行时间增加了 100 倍！（64 到 6400 ）。随着数组增大，对效率的影响会越来越大。这对大公司来说是个问题，比如谷歌要对几十亿条信息排序。

作为未来的计算机科学家你可能会问：有没有更高效的排序算法？我们下节继续

相关阅读：

1. 从汇编语言到高级编程语言的演变

2. 编程语言的基本元素

3. 函数的强大之处