Skip to Main Content
计算机科学导论:跨学科方法
book

计算机科学导论:跨学科方法

by 罗伯特 塞奇威克, 凯文 韦恩
August 2021
Beginner to intermediate content levelBeginner to intermediate
450 pages
19h
Chinese
Pearson
Content preview from 计算机科学导论:跨学科方法

4.2 排序和搜索

排序问题旨在将数组中的元素重新排列成升序。在许多计算和应用中,这是一个常用且关键的任务:音乐库中的歌曲按字母顺序排列;电子邮件按接收时间的相反顺序显示等。把事物按某种顺序排列是一种很自然的需求。排序非常有用的一个理由是,在排序的列表中搜索某些内容,要比在未排序的列表中容易得多。这种需求在计算中尤为突出,因为计算中要搜索的数组可能十分巨大,而高效的搜索可能是一个问题解决方案中的关键因素。

排序和查找对于商业应用程序(企业按照顺序存储客户文件)和科学应用程序(组织数据和计算)非常重要,并且在其他可能看似与事物排序无关的领域中也有各种应用,包括数据压缩、计算机图形学、生物信息学、数值计算、组合优化、密码学等。

我们使用这些基本问题来阐述一个观念,那就是高效的算法是计算问题的有效解决方案的关键之一。事实上,科学家已经提出了许多不同的排序和查找方法。解决一个具体任务时,我们应该选择哪种算法呢?这是一个非常重要的问题,因为不同的算法在性能上有显著的差异,从而导致成功解决实际问题还是根本无法解决实际问题的差别(即使使用最快的计算机)。

在本节中,我们将详细讨论用于查找和排序的两个经典算法——二分查找和归并排序,以及若干侧重效率的应用程序。通过这些例子,你会意识到,在解决需要大量计算的问题时,不仅仅需要注重方法的有效性,还需要注意运行成本。

二分查找法 “20个问题”的游戏(见程序1.5.2)为计算问题设计高效算法提供了一个重要并且有用的思路。规则十分很简单:你的任务是猜测一个神秘整数的值,它在0到n-1这n个整数之中。每次你做出一个猜测时,程序会告知猜测的值等于、大于或者小于那个神秘数字。为了阐述得更加清楚,我们首先稍微修改一下游戏的提问形式:“请问该数大于或等于x吗?”,其答案仅为true或false,假设n是2的整数次幂。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

数据科学之编程技术:使用R进行数据清理、分析与可视化

数据科学之编程技术:使用R进行数据清理、分析与可视化

迈克尔 弗里曼, 乔尔 罗斯
C语言核心技术(原书第2版)

C语言核心技术(原书第2版)

Peter Prinz, Tony Crawford

Publisher Resources

ISBN: 9787111641414