我们知道，计算机可以储存很多很多数据。不仅如此，一个强大的计算机还可以在很短的时间内迅速地找到用户希望提取的数据，比如当我们搜索某段微信聊天记录的时候。计算机这项强大的能力就叫做searching（检索）。 而在apcsa考试题型中，我们需要掌握两种searching algorithms（检索算法），分别是linear search（线性检索）和binary search（二分检索）。 其中，Binary search的效率通常会更高，但使用它的条件是：我们要检索的数据得提前被排序（无论是从小到大还是从大到小排列），而这个排序的过程又需要用到新的排序算法(sorting algorithms)。 

所以今天，我将带着同学们一起了解AP CSA考试所要求我们掌握的一些searching algorithms和sorting algorithms。

【考点提示】searching和sorting只会在选择题中出现噢~FRQ是不会考察的。所以不会写相关的代码也没关系，但一定要认真理解这些代码的逻辑，才不会在选择题里丢分噢~

01 Searching

1.1 Linear Search/ Sequential Search

Linear search（线性检索）也叫sequential search（顺序检索）。顾名思义，这种算法指的就是从前到后检索序列(sequence)中的一个个元素(element)，看序列中是否有元素与我们想找的目标元素一致。 如果程序在序列中找到了目标元素，就会返回这个元素在序列中的位置(index)，并停止检索；如果程序在检查完序列中的每一个元素后，都没有发现与目标元素一致的元素，就说明序列中根本没有我们想要查找的元素，就会返回-1。 这是linear search的具体代码： 

这段代码是干什么呢的？

下面这段代码同样运用了linear search的算法，和上面那段代码比较，大家发现了什么不同吗？
 

首先，在上一个method中，我们想要查找的序列是一个int array（整数型数组）；但在这个method中，我们要查找的序列变成了一个String array（字符串型数组），那么相应的，我们想查找的元素类型也就从int变成了String。 其次，上一个method比较a[i]和searchValue使用的是 “==”，但这个method使用的是方法“.equals()”。为什么呢？因为只有当被比较的两个references指向同一个object（对象）时，“==”才会返回true；而方法“.equals()”（在使用这个方法的class中被重新定义后）比较的才是两个references的内容的一致性。
 

找不同

因此，如果我们想要检索的元素类型是数值（int或者double），我们可以使用a[i] == searchValue；但如果我们想检索的元素类型是string或者某个object的内容，则应该使用a[i].equals(searchValue)。

1.2 Binary Search

如果我们想查找的序列含有的元素比较少，而且元素的排序没啥规律，使用linear search进行检索是没有太大问题的。但如果我们想要查找一个很大的序列，而且这个序列里的元素还已经从小到大/从大到小排列好了，使用linear search一个一个检索就会显得很慢而且非常低效。 想想看，如果你有一本英语词典，你想查找“search”这个单词是什么意思，你会从词典的第一页开始一页页地翻直到找到这个单词吗？肯定不会吧！大部分人应该会选择随机翻开词典中的某一页，然后将当前的字母和“search”的首字母“s”比照，按照26个字母的排列顺序选择往前翻页或是往后翻页，直到定位到“search”这个词为止。

Binary search（二分检索）的原理和查词典的过程非常相似：在进行binary search之前，我们要先确保这个序列里的元素已经按照顺序排列好了。 首先我们要找到一个序列中最中间的那个元素，将那个元素和我们想要检索的元素进行比较，如果它们恰好拥有一样的值，说明我们非常幸运，第一步就定位到了我们的目标元素，method会返回这个最中间的元素的位置。 但大部分情况下我们都没有那么幸运，如果这个最中间的元素比目标元素小，说明目标元素应该在最中间元素的右边，那我们就会在右边这一堆元素中继续检索； 如果这个最中间的元素比目标元素大，就说明目标元素应该在最中间元素的左边，那我们就应该在左边这一堆元素中继续检索。 只要我们还没找到目标元素，上述过程就会一直进行下去，直到我们找到目标元素并返回它的位置为止；如果直到最后都没有找到，就说明序列里不包含这个目标元素，就只好返回-1啦。
 

上面是binary search的代码，现在让我们来一步步拆分下：

02 Sorting

上文提到过，要使用binary search，前提是序列里的元素已经被排列得整整齐齐。那我们要通过什么方法按照一定顺序排列一个序列里的元素呢？

AP CSA要求我们掌握两种sorting algorithms，分别是selection sort（选择排序法）和insertion sort（插入排序法）。（其实还有merge sort，在recursion这一章节会学习。）它们有什么区别呢？Let’s dive in! 

2.1 Selection Sort

a.Introduction

Selection sort的基本逻辑是这样的：从index 0（序列的第一个位置）开始一一往后检索，找到序列中值最小的元素，然后将这个值最小的元素与处于index 0的元素交换，这时最小值就来到了序列的第一个位置。 然后程序重新从index 1（序列的第二个位置）往后检索，将找到的最小值和处于index 1的元素交换，这样全序列第二小的元素就来到了序列的第二个位置。然后程序会重新从index 2（序列的第三个位置）往后检索，做同样的事情，直到完成排序。最后，序列里的元素会按升序（从小到大）排序。 让我们来看看selection sort的具体代码：
 

b.Visualization

接下来我将用一个序列作为例子，用图画的方式展示selection sort是如何将元素进行排序的。长图预警！ 

2.2 Insertion Sort

仔细观察selection sort的代码，我们会发现无论序列里元素最开始是怎么排列的，程序该做的比较还是一步都少不了，序列里的元素得被反反复复检查好多回。但如果一个序列最开始就已经有被排列过的痕迹了，只是需要做一些微调，那insertion sort可能是一个更好的选择。  

a.Introduction

Insertion sort的基本逻辑可以这样理解：

桌子上有一些按顺序摆好的卡片，你手上有一张新卡片，你需要将它插入合适的位置以保持卡片的排列顺序。那么你会拿着这张卡片，从后往前一个个和桌上的卡片比对，直到找到合适的位置插入。你会一直重复，直到你把手上所有的卡片插入完成为止。

下面是insertion sort的具体代码：

b.Visualization

接下来我将用同一个序列作为例子，展示insertion sort是如何排序序列里的元素的，大家可以把长方形里的元素设想成摆放在桌子上的卡片，其他的元素是我们准备往桌子上放、决定插入哪个位置比较合适的卡片。 长图预警！

结 语

今天我们非常细致地了解了两种searching algorithms和两种sorting algorithms的基本逻辑和代码，希望能帮助你更好地理解它们~ 扫码咨询小助手，免费领相关资料！