线性查找法（線形探索法）是从数据开头起依次 逐个 与目标值比较，一旦相同就结束的查找方法。
第 3 次比较时相同，剩下的 2 不再检查，直接结束。
数据即使没有排序，也可以直接使用。比较次数取决于目标值所在的位置，若它在末尾或根本不存在，就要与全部数据逐一比较。平均下来，大约需要比较数据个数一半的次数。
类比就像在书脊排列杂乱的书架上找一本书，只能从最左边开始一本一本地看。
记法“线性”就是一条线：像沿着线描一样，从一端朝一个方向推进。
考点
二分查找法（2分探索法）用于按从小到大（升序）或从大到小（降序）排好序的数据，每次与查找范围 中间 的值比较，把范围缩小为目标值所在的那一半。
新范围中间的第 6 个正是 21，比较 2 次就找到了。
以升序为例，目标值比中间值小就只保留前半部分，比中间值大就只保留后半部分，如此反复，直到找到或范围为空。每比较一次，候选就减少约一半，所以数据个数翻倍，比较次数也只增加 1 次左右。不过比较次数也会随目标值的位置而变，若目标值靠近开头，线性查找法有时反而用更少的次数就能找到。
类比就像在一沓按号码顺序叠好的挂号单里抽出中间那张，判断要找的号码在前还是在后，再到剩下的一半里看中间那张。
记法“二分”就是一分为二。英文 binary search 中的 binary 也是“二”的意思。
考点
| 比较点 | 线性查找法 | 二分查找法 |
|---|---|---|
| 关键数据的排列 | 不限排列顺序 | 须已按升序或降序排好 |
| 开始比较的位置 | 开头 | 查找范围的中间 |
| 数据个数翻倍时 | 最坏比较次数也翻倍 | 比较次数增加 1 次左右 |
选择排序（選択ソート）是反复从尚未排好的范围中选出 最小值（或最大值），并与该范围一端的值交换的排序方法。
第 3 次把剩余 9 6 中较小的 6 与第 3 个的 9 交换，第 3 个确定；最后剩下的 9 不用比较，就落在第 4 个。
排序是把数据按值的大小顺序重新排列的处理。把未排序范围检查一遍、确定一端 1 个位置的值，这一轮称为 1 趟，每过 1 趟范围就缩小 1 个。比较次数大约与数据个数的平方成正比，因此数据多时很费时间。
类比就像整理手里的扑克牌：从还没理好的牌里找出最小的一张，放到已理好那几张的右边，如此反复。
记法英文 selection 意为“挑选”：就像选拔代表，先把所有人比一遍，再选出 1 个。
考点
冒泡排序（バブルソート）是比较 相邻的两个 值、顺序相反就交换，并从一端到另一端反复进行的排序方法。
交换第 3 个和第 4 个后，最大的 9 被送到末尾，第 4 个确定。
按升序排列时，每走完 1 趟，最大的值就被送到末尾并确定下来。下一趟在除去已确定末尾的范围内做同样的操作，如果某 1 趟中一次交换也没发生，排序就已完成。比较次数与选择排序相同，大约与数据个数的平方成正比。
类比就像排成一列的人只和身旁的人比身高，个子高的往右挪一位，一直比到队尾。
记法bubble 是“气泡”：大的值像气泡一样，一个个浮到末端。
考点
| 比较点 | 选择排序 | 冒泡排序 |
|---|---|---|
| 关键每比较一次之后 | 若值更小，就把它记为新的最小值候选（不交换） | 顺序相反就当场交换相邻两值 |
| 每趟的交换次数 | 最多 1 次 | 与比较时顺序相反的相邻对数相同 |
| 升序基本形式下每趟确定的值 | 选出的最小值（开头一侧） | 最大值（末尾一侧） |
快速排序（クイックソート）是先选定 1 个 基准值（pivot），把数据分成比它小的组和比它大的组，再对各组重复同样步骤的排序方法。
各组也按基准值再分，只剩 1 个的值位置随即确定。从左往右读就是 1 2 4 5 7 8。
组内元素只剩 1 个或没有时就不必再分，把各组按顺序排起来，整体就排好了。像这样把同一步骤套用到更小部分上的做法称为递归。平均比较次数比“平方型”方法少，但基准值选得不好时，会接近数据个数的平方。
类比就像把一堆文件按某个基准日期分成之前和之后两堆，再把每一堆照同样方法继续分下去。
记法quick 在英文中是“快”的意思。
从本单元的过去问中选 4 题
开始做确认题