算法第一步（Python版）

《算法第一步（Python版）》针对零基础的初学者，以算法为核心，以编程为手段，最终的目的是培养读者的计算思维。

本书涉及大学计算机课程中程序设计、数据结构和计算机原理等多个领域的知识，从程序、编程和算法是什么入手；然后重点介绍了控制流程和数据结构，并针对数据结构的限制和实现剖析了现代电子计算机的基础：二进制和冯·诺依曼结构；最后重点介绍了6大经典算法的原理、过程和编程实现，以及其背后的算法策略。

为了使零基础的读者能够上手编程，本书从操作角度阐述了编程工具的使用和程序编写、运行、调试的过程。

叶蒙蒙，微软资深算法工程师，科普写手。近二十年间积累了大量用C/C++, Java, C# 和 Python开发各类软件的经验，深刻体会到编程的核心在于算法。本着帮助更多朋友了解、学习计算机算法，掌握计算思维的初心，写作此书。

笔者第一次接触编程是20 世纪80 年代，当时参加了宋庆龄儿童活动中心举办的一项编程体验活动，就是照着前面黑板上写的代码在现场的机器上敲一遍，然后运行。当时到底用的是什么语言已经记不清了，但是还记得花费了好大力气，摸索着敲了一遍完全不清楚其含义的字符串，然后按照说明运行，最终毫无动静。虽然请教了巡场的工作人员，但他们也不知道是什么问题，到离场时都没能让程序“跑”起来——难道，编程就是要用计算机“写”一堆“ 密码”吗？如果这堆密码“跑”起来了，又会是怎样的效果呢？
　　初次不成功的体验后，直到20 世纪90 年代中期，因为学校开设了计算机课，笔者才再度接触编程。老师在课堂上讲了一点Basic 语言知识，编写的是a+b=c 之类的程序，然后运行得出结果。笔者由此知道了编程语言，期末考试成绩也不错，但对于编程是什么，计算机能干什么，还是不明所以。国外的影视剧中用计算机能做生意，能管理企业，但我们编写的程序只能做算术题，这是为什么呢？
　　上大学后，除了编程语言，笔者还学习了“数据结构”、“计算机原理”、“计算机体系结构”、“编译原理”、“操作系统”和“软件工程”等专业课程，这才逐渐明白了“编程”这一表面现象背后的体质：算法是怎么回事，计算机是如何运行的，为什么我们输入的静态字符能够变成动态的程序，通过其“跑动”来满足人们的需求……并由此了解到编程其实就是实现算法的过程。
　　算法，才是编程的核心。
　　后来进入职场，成了程序员，十几年一路走来，始终在一线研发岗位，开发过不同类型的实践项目，在开发过程中不断学习、揣摩，才逐渐领悟到抽象算法和现实问题之间的关系：软件开发就是通过各种算法实现具体的业务逻辑，把繁杂的过程抽象化、可计算化的过程。
　　而软件开发工作背后的思维逻辑（将一个个具体的问题及其解决方案表达成计算机可以处理的形式，并设计计算的方式，将客观世界解释为一个复杂的信息处理过程）则被称为计算思维，其具体表现如下：
　　把一个大问题分解为一个个子问题，然后进一步分解为一个个子子问题……直到无须分解。
　　分别执行一个个最小规模的问题。
　　按照问题划分的结构将各个小问题的结果组成整个问题的结果。
　　也就是自上而下进行结构化的设计，遇到问题“分而治之，各个击破”。这种解决问题
　　的方法并不是计算机专业独有的，完全可以脱离编程而存在，并且是各行各业都需要的：
　　准备一桌宴席应该怎么做？先确定总共有几道菜；然后购买原料，逐一烹调，装盘上桌——这是分而治之的过程。
　　创作一幅漫画应该怎么做？先确定故事背景、人物设置；然后构思主题、情节，绘制分镜头脚本；最后将每个分镜头的草图通过精描、上色等步骤绘制成成品图——这也是分而治之的过程。
　　举办一场学术会议应该怎么做？先确定主题、主讲人、参会群体、场地；然后分头准备（如邀请主讲人、确定演讲题目、制定日程）、租用/ 借用场地、协调交通、布置会场；最后招募参会者，注册、缴费，安排各项活动——这也是分而治之的过程。
　　开办一家餐馆应该怎么做？
　　拍摄一部电影应该怎么做？
　　研发一款电动汽车应该怎么做？
　　建设一个高新科技开发区应该怎么做？
　　……
　　计算思维不仅提出了一套解决问题的方法论，而且非常强调实践性——解决方案不是理论正确就可以，而是要在实际中可行才可以。
　　这个特点是由计算思维的诞生背景所决定的——当计算机科学家处理问题时，除了需要知道如何将一个问题抽象为计算机能够理解的可计算模型，还要能够将计算收敛到有限空间中得到结果。如果算法的时空复杂度过大，以当前的算力在有效求解的时间内无法得出结果，那么再完美的理论算法也无法在现实中奏效。
　　世界上的问题有大有小，所需要的资源有多有少，但抽象到最高层面的方法论可以是一致的。计算思维是各行各业都需要的。
　　掌握计算思维单靠理论学习是远远不够的，必须经由大量的实践。编程实践就是习得计算思维的最佳方式。
　　既然要进行编程实践，学习编程语言和工具的使用方法当然是必不可少的。但语言、工具都只是皮毛，随着计算机技术的发展，编程语言日益增加，各种工具日新月异，“保质期”越来越短。而经由现实问题提炼出来的经典算法却经得起时间的考验。
　　从计算机被发明出来到现在，一些逻辑层面的基础问题在大多数应用领域都会用到。
　　许多应用层繁多的花样，最终对应的都是共同的基础问题。计算机领域的科研人员、开发者，在几十年的工作中，针对一些历史悠久、应用广泛、高频出现的问题，研发出了对应的精致、高效的算法，我们将这些算法称为经典算法。
　　计算机的经典算法也有多种，但其中重要且常用的相对有限，主要有：
　　针对序列数据的查找算法和排序算法是基础。
　　针对树和图数据结构的各种算法：首先是遍历算法（深度优先和广度优先）；然后是各种类型的树结构，以及以计算图中不同顶点间最短路径为目的的各种算法。
　　若干用于解决数学问题（求最大公约数等）的计算机算法。
　　通过对经典算法的研习和实践，掌握“用数值表达现实事物，用运算描述任务目标，
　　再通过算法处理数据找到到达目标的最优路径”的方法论。如此，既是一种有效的思考力训练，又是形成计算思维的过程。由此形成的思维能力是内力，而同步掌握的编程技能则属外功。
　　从长远来看，学习编程可以提升人们的计算思维水平；就近期来看，掌握一门正在日益变得通用的技能非常重要。
　　本书针对没有任何程序设计基础的读者，同步讲解两方面内容：使用Python 语言编写程序；基础经典算法。由编程学算法，以算法促编程。同时，为了帮助读者理解算法，本书还介绍了计算机的基础运行原理。
　　在大学计算机专业课程中，本书所介绍的内容往往被拆分在如下几门课程中：
　　程序设计语言（如Python）
　　数据结构
　　计算机组成原理和体系结构
　　本书将几个领域的知识融合在一起，从日常事物开始，介绍软件、程序、算法和编程分别是什么；然后重点介绍编程的两大要素，即控制流程和数据结构，并详细介绍了几种常见的数据结构（如数组、链表、树和图），在此过程中，由数据结构的限制和实现引出现代电子计算机的基础——二进制和冯·诺依曼结构；最后进入算法阶段，从最简单的顺序查找开始，一边介绍算法，一边介绍它们的编程实现，详细介绍的经典算法包括顺序查找、二分查找、简单排序（包括选择排序、起泡排序、插入排序）和快速排序。
　　介绍具体算法无法脱离背后的原则，所以本书还介绍了作为快速排序思维基础的分治策略和引自数学的递归等算法策略。为了使零基础的读者能够上手编程，本书从操作角度阐述了编程工具的使用和程序编写、运行、调试的过程。
　　如此安排本书的内容主要源于以下两点：
　　使读者在接触编程的最初阶段就能够明确编程的核心是算法，从而将掌握算法策略、原理和过程作为学习重点，而不必将过多精力投入编程语言的语法或工具的操作等 “易过期”的细节上。
　　在学习理论算法的同时能够时刻联系实际，使读者不仅可以理解算法本身在不同应用场景中的优点和缺点，还可以运用算法解决现实中的问题，并培养读者的计算思维。
　　为了写作本书，笔者专门邀请了两位零基础的同学作为学生，按照上述思路，为她们上了为期一年的“算法编程同步学”课程。本书就是根据这门课程的教案整理而成的。在此特别感谢康牧心和任臻同学

第1章 认识算法
1.1 算法究竟是什么
1.1.1 广义的算法
1.1.2 计算机领域的算法
1.2 程序、编程和算法之间的关系
1.2.1 算法与程序
1.2.2 算法与编程
1.2.3 学习算法和编程的用处
1.3 学习算法的深度
1.3.1 掌握算法的5个层次
1.3.2 对应不同层次的讲解方法
1.3.3 算法驱动编程
1.3.4 算法的难点：从原理到实现

第2章 万事的抽象：控制流程
2.1 认识流程
2.1.1 顺序
2.1.2 顺序结构
2.1.3 条件（分支）
2.1.4 条件（分支）结构
2.1.5 循环（迭代）
2.1.6 循环（迭代）结构
2.2 用简单的结构表达复杂的过程：控制结构的排列和嵌套
2.2.1 什么是流程图
2.2.2 极简版流程图符号表
2.2.3 最简单的流程图
2.3 流程图的粒度与嵌套
2.3.1 粒度
2.3.2 嵌套
2.3.3 条件结构和循环结构的嵌套
2.3.4 粒度均衡的流程图

第3章 计算机是如何运行的
3.1 数据
3.1.1 信息数字化
3.1.2 数据化与数据
3.1.3 数据的组织
3.1.4 数据结构
3.2 计算机原理浅释
3.2.1 电子计算机的前世今生
3.2.2 冯·诺依曼结构
3.2.3 存储空间的地址和内容
3.2.4 一条指令是如何被执行的
3.2.5 冯·诺依曼结构的直观解释
3.2.6 冯·诺依曼结构的应用
3.2.7 冯·诺依曼结构的瓶颈
3.2.8 哈佛结构

第4章 万物的抽象：数据结构
4.1 认识数据结构
4.1.1 数组
4.1.2 链表
4.2 直观理解数据结构
4.2.1 数组与链表
4.2.2 数组与链表之同
4.2.3 数组与链表之异
4.3 预留给货物的固定货架：内存中的数组
4.3.1 存储空间
4.3.2 数组：一块连续的存储空间
4.3.3 数组的下标
4.3.4 数组中的元素
4.3.5 数组的元素值
4.3.6 数组的特性
4.3.7 连续存储惹的祸
4.4 见缝插针地摆放货物：内存中的链表
4.4.1 链表
4.4.2 链表的编辑
4.5 数据结构的特性和发展
4.5.1 特性各异的链表与数组
4.5.2 数据结构的发展

第5章 复杂一些的数据结构：图和树
5.1 图
5.1.1 图的定义和分类
5.1.2 相关概念和算法
5.2 树
5.2.1 树的定义
5.2.2 二叉树
5.3 遍历算法
5.3.1 树的遍历和图的遍历
5.3.2 二叉树的深度优先遍历算法
5.3.3 二叉树的广度优先遍历算法
5.4 图和树的现实意义
5.4.1 图的抽象
5.4.2 树的抽象
5.5 图和树
5.5.1 树是图的真子集
5.5.2 树比图更加严谨

第6章 第一行Python代码
6.1 跟你的计算机聊天：编程语言
6.1.1 什么是编程语言
6.1.2 从低级语言到高级语言
6.1.3 编译和解释
6.2 直观感受不同的编程语言
6.3 一条可爱的小蟒蛇：Python语言
6.3.1 主流编程语言
6.3.2 为什么选择Python
6.3.3 Python的特性
6.3.4 结合数组与链表的优点的列表
6.4 Python的编辑、运行环境
6.4.1 顺序安装
6.4.2 创建项目
6.4.3 开始编写第一个程序
6.5 第一个Python程序：让Python小蟒蛇动起来
6.5.1 你好世界
6.5.2 运行Python程序的几种方式
6.5.3 编程语言的基本概念
6.5.4 Python中的print()函数

第7章 开始用Python语言编写程序
7.1 数据值和数据类型
7.1.1 数据的抽象和具象含义
7.1.2 数据类型
7.2 标识符
7.3 字面量、变量和常量
7.4 变量赋值
7.4.1 赋值的方式
7.4.2 赋值前无须声明类型
7.4.3 赋值后不能隐性转换类型
7.5 Python中的数组
7.5.1 逻辑上的数组
7.5.2 列表和元素
7.5.3 列表的赋值和复制
7.6 Python中的流程控制
7.6.1 用缩进划分代码块
7.6.2 关键字
7.6.3 Python中的3种控制结构
7.6.4 不同类型结构的嵌套

第8章 实现第一个算法并衡量其优劣
8.1 从最简单的算法开始学：顺序查找
8.1.1 什么是查找算法
8.1.2 查找算法的要素
8.1.3 顺序查找
8.2 顺序查找的数据结构和控制流程
8.2.1 数据结构
8.2.2 控制流程
8.3 用Python实现顺序查找算法
8.3.1 用变量和赋值重绘流程图
8.3.2 代码实现
8.4 用for语句实现顺序查找算法
8.4.1 Python循环关键字：for和while
8.4.2 用for循环实现顺序查找算法
8.5 如何衡量算法的性能
8.5.1 时间复杂度
8.5.2 常见算法的时间复杂度
8.5.3 空间复杂度

第9章 简单但有用的经典查找算法
9.1 猜数游戏
9.1.1 游戏规则
9.1.2 不限制猜测次数的游戏的必胜攻略
9.1.3 限制猜测次数的猜数游戏
9.2 从“挨着找”到“跳着找”
9.3 二分查找：从原理到形式化描述
9.3.1 二分查找的原理
9.3.2 结构化的自然语言描述——流程图
9.3.3 形式化描述第一步——变量和赋值
9.4 二分查找的编程实现
9.4.1 形式化流程控制
9.4.2 从流程图到代码
9.5 二分查找的性能
9.5.1 二分查找的时间复杂度
9.5.2 二分查找的空间复杂度

第10章 程序中的函数
10.1 计算机领域的函数
10.1.1 编程中的函数
10.1.2 函数的定义
10.1.3 函数的调用
10.1.4 二分查找函数
10.2 函数的作用
10.2.1 重用
10.2.2 抽象和封装
10.2.3 从程序之外获得数据
10.3 函数的参数
10.3.1 函数的参数及其值的变化
10.3.2 Python的函数参数传递
10.3.3 函数参数问题的简化理解

第11章 编程实现猜数游戏
11.1 用Python实现猜数游戏
11.1.1 猜数游戏与二分查找
11.1.2 编写猜数游戏攻击者辅助程序
11.2 修改后的猜数小助手为什么输了
11.3 Bug
11.4 Bug的天敌——Debug
11.4.1 什么是Debug
11.4.2 常用Debug方法：打印变量中间值
11.5 和Bug斗智斗勇
11.5.1 Bug的严重性
11.5.2 产生Bug的原因
11.5.3 防止Bug产生危害的方法

第12章 二分查找的变形
12.1 二分查找变形记：重复数列二分查找
12.1.1 包含重复元素数列的二分查找
12.1.2 包含重复元素数列的二分查找的变形
12.2 让变形更高效：与经典二分查找相同的时间复杂度
12.2.1 包含重复元素数列的二分查找的时间复杂度
12.2.2 时间复杂度的计算
12.2.3 包含重复元素数列的二分查找的O(log(n))算法
12.3 二分查找再变形：旋转数列二分查找
12.3.1 有序数列的旋转
12.3.2 不包含重复元素旋转数列的二分查找
12.3.3 算法实现
12.3.4 代码优化
12.4 包含重复元素旋转数列的二分查找

第13章 认识排序算法
13.1 处处可见的排行榜
13.1.1 什么是排序
13.1.2 排序算法的江湖地位
13.1.3 无处不在的排行榜
13.2 排序算法的分类
13.2.1 排序算法的分类方式
13.2.2 比较排序
13.2.3 比较排序的局限和优势
13.3 排序算法的基本操作：两两交换数组中的元素
13.3.1 查找算法和排序算法
13.3.2 两两交换数组中的元素
13.3.3 swap()函数
13.3.4 没有返回值的swap()函数

第14章 几种简单排序算法
14.1 扑克牌游戏
14.1.1 用扑克牌做一个小游戏
14.1.2 排序要解决的问题
14.1.3 基于直觉的排序算法
14.2 选择排序
14.2.1 算法原理
14.2.2 数据结构
14.2.3 算法步骤
14.2.4 编程实现
14.3 起泡排序
14.3.1 历史
14.3.2 算法原理
14.3.3 算法步骤
14.3.4 编程实现
14.3.5 算法优化
14.4 插入排序
14.4.1 算法原理：又见扑克牌
14.4.2 在数组中插入元素
14.4.3 算法步骤
14.4.4 编程实现
14.5 简单排序概述
14.5.1 排序的时间复杂度
14.5.2 排序的空间复杂度
14.5.3 简单排序算法性能总结

第15章 必须掌握的排序算法
15.1 快速排序
15.1.1 一个“笑话”
15.1.2 算法原理
15.1.3 算法的江湖地位
15.1.4 算法步骤
15.2 快速排序的时间复杂度
15.2.1 时间复杂度的计算
15.2.2 最佳时间复杂度
15.2.3 最差时间复杂度
15.2.4 平均时间复杂度
15.2.5 理解快速排序的平均时间复杂度
15.3 快速排序的空间复杂度
15.3.1 简单的分区函数
15.3.2 优化分区函数
15.4 解读分区算法源代码
15.4.1 “人肉计算机”法
15.4.2 打印解读法
15.5 编程实现快速排序算法
15.5.1 分治策略
15.5.2 快速排序的分与治
15.5.3 编程实现快速排序算法

第16章 递归实现快速排序
16.1 递归：像“贪吃蛇”一样“吃掉”自己
16.1.1 历史悠久的概念
16.1.2 无效递归
16.1.3 有效递归
16.1.4 分形
16.1.5 斐波那契数列
16.2 递归函数
16.2.1 递归和分治
16.2.2 递归函数
16.2.3 最简单的递归函数
16.2.4 Python 限制递归深度
16.2.5 限制运行次数的递归函数
16.2.6 递归实现斐波那契数的计算
16.3 实现递归式快速排序
16.3.1 递归式快速排序的原理
16.3.2 递归式快速排序的编程实现
16.3.3 算法性能
16.4 测试算法程序
16.4.1 构造测试数据集
16.4.2 安装 pip 和用 pip 安装模块
16.4.3 用生成数据测试快速排序
16.4.4 分区函数带来的差异

第17章 算法精进
17.1 如何算学会了一个算法
17.1.1 以二分查找为例了解“掌握算法的几个层次”
17.1.2 依据掌握的知识解决问题
17.1.3 学习算法的误区
17.2 学会之后——创新
17.3 如何自学算法
17.3.1 自学三要素
17.3.2 学习材料和内容
17.3.3 学习目的和深度
17.3.4 学习方法
17.3.5 如何阅读代码
17.3.6 练习与实践
17.4 说说刷题