查找，排序，麻利儿搞定啥叫堆：选择题白话串讲（5）

公共基础

二级Office必考的考点

专业性很强

如果没有好的复习资料

是相当枯燥、晦涩、难懂的

你还为公共基础难懂

苦大愁深吗？

你还为不知如何拿下选择题

焦头烂额吗？

今天开始，小编带着大家

远离枯燥、远离专业术语

白话学懂公共基础！

程林高手武功秘籍--公共基础知识

1.8 这个经常有--查找技术

计算机是人类的伙伴，它凭借强大的存储能力可以帮助我们保存很多信息。保存信息不是目的，我们希望的是能随时方便、快捷地从海量信息中获取所需要的信息，这就是查找。查找操作在计算机中非常常见，比如你今天百度了一个什么，或者在网上商城查询一个商品的价格，就连登录一次QQ都需要查找，服务器首先需要找到你的账号，确认你的身份是否合法。

计算机是怎样实现查找的呢？最简单的查找方法是顺序查找。

1.8.1 顺序查找

顾名思义，顺序查找就是按顺序一个一个地翻，直到找到为止，这是最原始的方法。若扫描完整个线性表后仍未找到，表示没有找到。

显然这种查找方式的工作量与数据的多少有关，还与要找的元素所在的位置有关。如果要找的数据恰好位于0号元素，则只需比较1次就可以了；如果要找的数据在a[1]，则需比较2次……，最"倒霉"的情况是要找的数据在最后一个位置a[n-1]，所有的元素都要比较过来，需比较n次。这是找到元素的情况。如没有找到元素，都要比较n次。因此，顺序查找最好情况需要比较1次，最坏情况需要比较n次，平均需要比较(1+2+…+n)/n=(n+1)/2次。

如果n是一个很大的值，那么需要比较的次数就太多了！即使计算机有极快的速度，还需要一些时间查找。全世界网页的数字是个天文数字。如果度娘用这种方法查找，每个人的每次搜索都要比较这么大的一个天文数字的次数，全世界又有很多人在同时用度娘，那度娘要比较多少次呢？我们单击搜索之后恐怕要等到明年才能看到结果了……然而事实不是这样的，我们可以立即得到结果，其查找速度是非常之快的。因为度娘绝不是用"顺序查找"的方法，而是采用了更快、效率更高的查找方法。

查找方法可以很复杂，查找技术是一门学问，也有人在不断研究和发明更多更好的查找方法。我们只介绍其中之一——二分查找。

1.8.2 二分查找

二分查找又称对分查找、折半查找，这是一种效率很高的查找方法。然而要使用二分查找必须有两个前提：一是数据必须以数组的方式存储（也称顺序存储），以链表存储的数据是不能进行二分查找的；二是数据在数组中必须按由小到大或由大到小的有序顺序排列。

例如要在下面数组中查找25是不能用二分查找的：

因为数据大小顺序是乱序的。必须把数据按大小顺序重新组织，如由小到大排序：

这样才能进行二分查找。

二分查找时，第一次并不是比较a[0]是否为25，而是首先检查整个数组中间的一个元素。中间元素的下标用首尾下标相加除以2求得：(0+8)/2=4。因此第一次比较a[4]是否为25：发现a[4]为20不是25而小于25，虽然还未找到但可得出结论，要找的25必在a[4]之后，因为数据是由小到大排序的。这样a[4]之前的a[0]~a[3]这"一半"的数据以后就都不用看了，而只需再检查a[5]~a[8]，工作量减少一半。第二次比较的仍是a[5]~a[8]中间的一个元素：(5+8)/2=6（整数除法直接舍小数），a[6]为28大于25，再砍掉a[7]~a[8]这一半。第三次比较a[5]就找到了25。总共比较了3次。实际上，我们在查英文词典时，也是按照一种类似二分查找的方式。如图，例如要在词典中找tea这个单词，我们不会从第一个单词a开始查找，而是大概翻到词典的一半。如果发现是m开头的单词，则不会再查词典的前一半。下次翻到词典后一半中的大概一半的位置，例如翻到了x开头的单词，此处之后的部分也不会再查了，因为t在x之前。所剩部分再翻到大概一半的位置……如此逐步缩小查找范围，最终找到tea。然而这种查找有一个前提是词典中的单词是按字母表顺序a～z排列的。

【随讲随练16-25】为了对有序表进行对分查找，则要求有序表（ ）。

A.只能顺序存储

B.只能链式存储

C.可以顺序存储也可以链式存储

D.任何存储方式

【答案】A

二分查找每次比较都能"砍掉"一半的工作量，下次再"砍掉"一半中的一半……在最坏情况下它需要的比较次数是log2n，这比顺序查找的效率大大提高！

【随讲随练16-26】在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。

A.O(n)

B.O(n2)

C.O(log2n)

D.O(nlog2n)

【答案】C

1.9 混乱之治--排序技术

排序，就是按照各数据的大小，重新安排它们在数组或链表中的位置，使它们由小到大或由大到小排列。一副新买的扑克牌就是排好序的；将牌洗乱后，再重新按照花色和1~13的顺序整理，使顺序恢复如初，这就是排序。我们是怎样整理好洗乱的扑克牌的顺序的呢？

排序方法之一的冒泡排序法的基本思想是：总是相邻的两个数比较，前者大则交换位置，最终让最大的数沉底；下次不考虑上次沉底的数，让剩余的数中的最大数沉底……，直到最后剩余1个数排序完成，如图16-18。

排序方法有很多，现将各种常用的排序方法及它们的效率总结于表16-2。

表16-2 常用排序法效率总结

选择排序法的基本思想是每次从未排序元素中选择一个最大（或最小）元素，未排序元素个数逐渐减少，最后剩一个元素为止。插入排序法的基本思想是一个个地将元素插入到已排好序的序列中。快速排序法的基本思想是任取序列中某个元素为基准，将序列划分为左右两个子序列，左侧子序列都小于或等于基准元素，右侧子序列都大于基准元素，接下来分别对两个子序列重复上述过程。希尔排序法的基本思想是将原序列中相隔某个增量的那些元素构成一个子序列，在排序过程中，增量逐渐减小，当增量减小到1时，进行一次简单插入排序即可。

（累）堆排序法是借助"堆"的一种排序方法。什么是"堆"呢？具有n个元素的序列（h1,h2,...,hn），当且仅当满足hi≥h2i且hi≥h2i+1（或者两个条件都是≤）时称为"堆"。堆实际是一棵完全二叉树，其中根结点的值总要≥它的左右分支结点（或≤）。

【随讲随练16-27】下列各序列中不是堆的是（ ）。

A. (91,85,53,36,47,30,24,12)

B. (91,85,53,47,36,30,24,12)

C. (47,91,53,85,30,12,24,36)

D. (91,85,53,47,30,12,24,36)

【答案】C

【解析】

A) 每个情况，子节点都≤父节点

B) 每个情况，子节点都≤父节点

C) 蓝色节点:子节点都≤父节点；但却有红色节点:子节点都≥父节点；≤、≥情况不统一，故C不是堆

D) 每个情况，子节点都≤父节点

【随讲随练16-28】下列排序方法中，最坏情况下比较次数最少的是（ ）。

A.冒泡排序

B.简单选择排序

C.直接插入排序

D.堆排序

【答案】D

【随讲随练16-29】冒泡排序在最坏情况下的比较次数是（ ）。

A.n(n+1)/2

B.nlog2n

C.n(n-1)/2

D.n/2

【答案】C

【随讲随练16-30】在最坏情况下，堆排序的时间复杂度是（ ）。

A.O(nlog2n)

B.O(log2n)

C.O(n2)

D.O(n1.5)

【答案】A

——以上内容选自《玩转Office轻松过二级》(第2版)，部分内容取自《C语言其实很简单》（第11-12章）

想不怎么费力就学懂公共基础的童靴，推荐赶快去看一看这2本书吧，这目前应是唯一白话串讲公共基础的二级教材，也真的是最好的教材哦。

要看一本浅显易懂、适合快速学习的书。同意吗？

注意注意注意

千万不要用那种只有文字、没有图的复习材料或速背手册之类复习哦（除非你早有基础），那是很不负责的材料。公共基础必须要有图讲解，考试的考题里也有图。用只有文字的材料复习，考试必傻眼，别害了自己！