9.3查找算法 查找算法与我们的生活息息相关。比如从书架上找一本书，从字典中找某一个单词，甚至在使用计算机登录你 的社交账号时，都用到了查找算法。 9.3.1顺序查找 查找算法中最简单的方法是顺序查找。也就是从第一个开始，逐个查找，比对，直到找到所需数据为止。比如 从书架上找一本书这个例子，如果所有的书都是随机放置在书架上的怎么会这样？)，那么就没有好办法了，只能 使用顺序查找的方式，一本一本的翻阅。很显然，这是效率非常低的一种查找方式。但是它胜在简单直观，对于规 模不大的数据的查找，这也是最容易实现的方法。 下面我们来做 个游戏。 我随便想一个介于1到100之间的数字，请你猜出我想到的这个数字。现在使用顺序查找法，那么你需要从1 开始往后猜。 你：1我：小了 你：2 我：小了 你：3 我：小了 你：4 我：小了 如果我想的数字是99，那么你需要猜99次才能猜到！下面是一种更好的猜数方法。 9.3.2二分查找 你：50 我：小了 /这时可以排除掉一半的数字，只需猜大于50的数字 你：75 我.大了 这时又排除掉一半的数字，只需在50到75之间选择 你：63 我：大了 /这时又排除掉一半的数字，只需在50到63之间选择 你：57 我：对门了！ 这就是二分查找法。不管我心里想的是什么数字，你都可以在7次以内猜到。 如果要从一本字典中查找单词，该字典包含240000个单词，而要找的单词恰好在字典的末尾。那么，如果使 用顺序查找，则需要240000步操作，使用二分查找，每次都排除一半单词，直到最后只剩下一个，只需18步操作。 这两种算法的效率高低一目了然。 般而言，对于包含n个元素的列表，用顺序查找最多需要n步，用二分查找最 多周要logzn步 当然，只有当列表中的数据有序时，二分查找才管用。因此，排序是查找的前提，有关排序的内容我们将在9.4 节中详细介绍。 下面通过一个实倒来给出二分查找的算法描述 -19 2732 4467081 92 这组数据已按从小到大的顺序排列好，我们要查找81这个数字，如果存在，给出它的位置，如果不存在，给 出相应的提示信总。 算法分析： 第1次比较的数字范围是整个数字序列，如图94中第一行数字下的框线所示。首先找到全部数字的中间位置， 也就是34，它将数字序列一分为二 要找的数字81>34，因此，继续在后半部分查找。此时要查找的数字范围是 34后面一个数字开始的，如图9.4中第二行数字下的框线所示，问题规模减小了一半。第2次比较的中间位置是数 字70，要找的数字81>70，则在后半部分继续查找。第3次比较的中间位置是数字81，至此查找成功
9.3 查找算法 查找算法与我们的生活息息相关。比如从书架上找一本书，从字典中找某一个单词，甚至在使用计算机登录你 的社交账号时，都用到了查找算法。 9.3.1 顺序查找 查找算法中最简单的方法是顺序查找。也就是从第一个开始，逐个查找，比对，直到找到所需数据为止。比如 从书架上找一本书这个例子，如果所有的书都是随机放置在书架上的(怎么会这样？)，那么就没有好办法了，只能 使用顺序查找的方式，一本一本的翻阅。很显然，这是效率非常低的一种查找方式。但是它胜在简单直观，对于规 模不大的数据的查找，这也是最容易实现的方法。 下面我们来做一个游戏。 我随便想一个介于 1 到 100 之间的数字，请你猜出我想到的这个数字。现在使用顺序查找法，那么你需要从 1 开始往后猜。 你：1 我：小了 你：2 我：小了 你：3 我：小了 你：4 我：小了 . . 如果我想的数字是 99，那么你需要猜 99 次才能猜到！下面是一种更好的猜数方法。 9.3.2 二分查找 你：50 我：小了 //这时可以排除掉一半的数字，只需猜大于 50 的数字 你：75 我：大了 //这时又排除掉一半的数字，只需在 50 到 75 之间选择 你：63 我：大了 //这时又排除掉一半的数字，只需在 50 到 63 之间选择 你：57 我：对了！ 这就是二分查找法。不管我心里想的是什么数字，你都可以在 7 次以内猜到。 如果要从一本字典中查找单词，该字典包含 240000 个单词，而要找的单词恰好在字典的末尾。那么，如果使 用顺序查找，则需要 240000 步操作，使用二分查找，每次都排除一半单词，直到最后只剩下一个，只需 18 步操作。 这两种算法的效率高低一目了然。一般而言，对于包含 n 个元素的列表，用顺序查找最多需要 n 步，用二分查找最 多需要 log2n 步。 当然，只有当列表中的数据有序时，二分查找才管用。因此，排序是查找的前提，有关排序的内容我们将在 9.4 节中详细介绍。 下面通过一个实例来给出二分查找的算法描述。 假定有一组数据如下： -19 6 27 32 34 46 70 81 92 这组数据已按从小到大的顺序排列好，我们要查找 81 这个数字，如果存在，给出它的位置，如果不存在，给 出相应的提示信息。 算法分析： 第 1 次比较的数字范围是整个数字序列，如图 9.4 中第一行数字下的框线所示。首先找到全部数字的中间位置， 也就是 34，它将数字序列一分为二。要找的数字 81>34，因此，继续在后半部分查找。此时要查找的数字范围是从 34 后面一个数字开始的，如图 9.4 中第二行数字下的框线所示，问题规模减小了一半。第 2 次比较的中间位置是数 字 70，要找的数字 81>70，则在后半部分继续查找。第 3 次比较的中间位置是数字 81，至此查找成功
第1次比较：-19627323446708192 第2次比：1962”324601明 第3次比较：196273234467092 图9.4二分查找过程 算法9.5 (1)将n个有序数字保存在变量a)中，i1n 要查找的关键字保存在变量key中 (2使用两个变量low和high分别代表要查找范围的下限和上限。显然它们的初值分别是：Iow=1,high=n(n 为全部数字的个数) 3如果 w<high,计算中间位置用变量mid保存：mid=(ow+high/2(如果无法整除，则取小于它的最大整数) 然后给变量y赋值：ya(mid,转向4 如果low≥high,转向7)。 (4如果ykey,则转向(6)。否则，转向5)。 6)输出k (7)榆出提示信息：没有要查找的数字。 9.4排序算法 9.4.1直接插入排序 直接插入排序是一种最为简单的排序方法。它的基本思想是将一条数据插入到已排好的有序表中合适的位置 使得插入后的序列仍然有序。下面通过 个例子来介绍直接插入排序的执行过程。 有这样一个数据元素序列 {13,6,7.2.11.9,28,4} 该序列的第一个元素13是初始子序列，下面要将元素6插入到这个子序列中，得到一个包含两个元素的有序 子序列。怎么操作呢？首先确定6要插入的位置。具体方法是，从13开始向左查找，由于6小于13，因此要将13 向后移动，将6插入到13的前面。这个过程被称为一直接插入排序。 这时数据序列变为了 {(6,13),7,2.11,9,28,4} 下面我们继续将元素7插入到有序子序列中。具体方法是，从13开始向左查找，由于7小于13，因此13要继 续向后移动：又因为7大于6，因此7要插入到6和13之间。这样就在原序列中得到一个新的包含3个元素的有序 子序列。 {6,7,13,2,11,9,28,4 按照这种插入的方法，可将后面的5个元素逐一插入到前面的子序列中，当子序列与原序列长度一样时，插入 排序结束。下面是元素序列13,6,7,2,11,9,28,4的直接插入排序全过程。 初始状态： {13,5,7,2,11,9,28,4 第1趟直接插入排序：(6,13，2,11,9,28,4 第2趙直接插入排序：(6,7,13一2,11,9,28,4
图 9.4 二分查找过程 算法 9.5： (1)将 n 个有序数字保存在变量 a(i)中，i=1.n 要查找的关键字保存在变量 key 中 (2)使用两个变量 low 和 high 分别代表要查找范围的下限和上限。显然它们的初值分别是：low=1，high=n（n 为全部数字的个数） (3)如果 low<high，计算中间位置用变量 mid 保存：mid=(low+high)/2（如果无法整除，则取小于它的最大整数）。 然后给变量 y 赋值：y=a(mid)，转向(4)。 如果 low≥high，转向(7)。 (4)如果 y=key，则转向(6)。否则，转向(5)。 (5)如果 y<key，则修改 low 的值：low=mid+1，转向(3)。 如果 y>key，则修改 high 的值：high=mid-1，转向(3)。 (6)输出 k。 (7)输出提示信息：没有要查找的数字。 9.4 排序算法 9.4.1 直接插入排序 直接插入排序是一种最为简单的排序方法。它的基本思想是将一条数据插入到已排好的有序表中合适的位置， 使得插入后的序列仍然有序。下面通过一个例子来介绍直接插入排序的执行过程。 有这样一个数据元素序列 {13, 6, 7, 2, 11, 9, 28, 4} 该序列的第一个元素 13 是初始子序列，下面要将元素 6 插入到这个子序列中，得到一个包含两个元素的有序 子序列。怎么操作呢？首先确定 6 要插入的位置。具体方法是，从 13 开始向左查找，由于 6 小于 13，因此要将 13 向后移动，将 6 插入到 13 的前面。这个过程被称为一趟直接插入排序。 这时数据序列变为了 { (6, 13), 7, 2, 11, 9, 28, 4} 下面我们继续将元素 7 插入到有序子序列中。具体方法是，从 13 开始向左查找，由于 7 小于 13，因此 13 要继 续向后移动；又因为 7 大于 6，因此 7 要插入到 6 和 13 之间。这样就在原序列中得到一个新的包含 3 个元素的有序 子序列。 { (6, 7, 13), 2, 11, 9, 28, 4} 按照这种插入的方法，可将后面的 5 个元素逐一插入到前面的子序列中，当子序列与原序列长度一样时，插入 排序结束。下面是元素序列{13, 6, 7, 2, 11, 9, 28, 4}的直接插入排序全过程。 初始状态： { (13), 6, 7, 2, 11, 9, 28, 4} 第 1 趟直接插入排序：{ (6, 13), 7, 2, 11, 9, 28, 4} 第 2 趟直接插入排序：{ (6, 7, 13), 2, 11, 9, 28, 4}
第3趙直接插入排序：(2,67,13)1,9,28,4 第4植直接插入排序：（亿，6,7，止13助9,28,4 第5趟直接插入排序：{2,6,7,911,13引，28,4 第6趟直接插入排序：(2,6,7,9,11,13,28,4 第7趟直接插入排序：(2,46,7,9.11,13,28} 从这个插入排序的过程中可以看出：一个包含有n个元素的序列，需要1趟排序就可以将原序列排列有序。 显然这个算法的效率是偏低的。 9.4.2选择排序 选择排序是一种常见的排序方法，下面通过一个实例来了解它的排序原理。有这样一组数据元素(13,6 2,11,9,28,4,第一趟排序时，要从这8个元素中找出最小的那个，也就是序列中的元素2，将它与第一个 元素13交换位置。得到序列： 【(2).6.7,13.11.9.28.4} 第二趟排序时，从后面的7个元素中找到最小的元素4，将它与第二个元素交换位置，得到序列： {2,47, 13,11,9,28,6 第三趟排序时，从后面的6个元素中找到最小的元素6，将它与第三个元素交换位置，得到序列： {2,4h,613,11,9,28,71 接下来的每一趟排序操作都是按照这样的“找最小值再交换位置”的方法进行。上述元素序列的选择排序过程 如下 初始状态： {136,7,2.11,9,28,4 第1趟选择排序：{26,7,13,11,9,28，_4 第2趙选择排序：{亿，4,7,13,11,9,286} 第3趟选择排序：{2,4,61,13,11,9,28,7 第4描选择排序：{(2,46,7八，11,9,28,13引 第5脑选择排序：，46,79立28,13 第6趟选择排序：{2,4,6,7,9,11.2迟13引 第7趟选择排序：{2,4,6,7,911,1328 从这个选择排序的过程中可以看出：一个包含有n个元素的序列，需要1趟排序就可以将原序列排列有序 最后第n个元素不需要再选择，它一定是最大的 与插入排序相比较，选择排序的优点是移动数据的次数已知(1次)，缺点是比较次数较多。而插入排序的 缺点是比较次数不一定，插入点后的数据移动较多，当数据总量庞大的时候，这个操作还是比较费时的
第 3 趟直接插入排序：{ (2, 6, 7, 13), 11, 9, 28, 4} 第 4 趟直接插入排序：{ (2, 6, 7, 11, 13), 9, 28, 4} 第 5 趟直接插入排序：{ (2, 6, 7, 9, 11, 13), 28, 4} 第 6 趟直接插入排序：{ (2, 6, 7, 9, 11, 13, 28), 4} 第 7 趟直接插入排序：{ (2, 4, 6, 7, 9, 11, 13, 28) } 从这个插入排序的过程中可以看出：一个包含有 n 个元素的序列，需要 n-1 趟排序就可以将原序列排列有序。 显然这个算法的效率是偏低的。 9.4.2 选择排序 选择排序是一种常见的排序方法，下面通过一个实例来了解它的排序原理。有这样一组数据元素 { 13, 6, 7, 2, 11, 9, 28, 4}，第一趟排序时，要从这 8 个元素中找出最小的那个，也就是序列中的元素 2，将它与第一个 元素 13 交换位置。得到序列： { (2), 6, 7, 13, 11, 9, 28, 4} 第二趟排序时，从后面的 7 个元素中找到最小的元素 4，将它与第二个元素交换位置，得到序列： { (2, 4), 7, 13, 11, 9, 28, 6} 第三趟排序时，从后面的 6 个元素中找到最小的元素 6，将它与第三个元素交换位置，得到序列： { (2, 4), 6, 13, 11, 9, 28, 7} 接下来的每一趟排序操作都是按照这样的“找最小值再交换位置”的方法进行。上述元素序列的选择排序过程 如下： 初始状态： { 13, 6, 7, 2, 11, 9, 28, 4} 第 1 趟选择排序：{ (2), 6, 7, 13, 11, 9, 28, 4} 第 2 趟选择排序：{ (2, 4), 7, 13, 11, 9, 28, 6} 第 3 趟选择排序：{ (2, 4, 6), 13, 11, 9, 28, 7} 第 4 趟选择排序：{ (2, 4, 6, 7), 11, 9, 28, 13} 第 5 趟选择排序：{ (2, 4, 6, 7, 9), 11, 28, 13} 第 6 趟选择排序：{ (2, 4, 6, 7, 9, 11), 28, 13} 第 7 趟选择排序：{ (2, 4, 6, 7, 9, 11, 13), 28} 从这个选择排序的过程中可以看出：一个包含有 n 个元素的序列，需要 n-1 趟排序就可以将原序列排列有序。 最后第 n 个元素不需要再选择，它一定是最大的。 与插入排序相比较，选择排序的优点是移动数据的次数已知（n-1 次），缺点是比较次数较多。而插入排序的 缺点是比较次数不一定，插入点后的数据移动较多，当数据总量庞大的时候，这个操作还是比较费时的