编程珠玑：优雅Quicksort算法与编程艺术

4星 · 超过85%的资源需积分: 10 114 浏览量更新于2024-07-26 1 收藏 1.23MB PDF 举报

《Programming Pearls, Second Edition》是由Jon Bentley撰写的一本经典IT书籍，它被誉为编程艺术的瑰宝，强调了编程中的洞察力和创新思维。这本书的独特之处在于作者分享了一种优雅的代码划分模式，通过Nico Lomuto的教学，Bentley开发并完善了快速排序算法（Quicksort），这是他自认为最漂亮的代码之一。快速排序是一种高效的排序算法，基于分治策略，其核心思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序。 Bentley在书中提倡简洁编程的原则，类似于William Strunk Jr.在《The Elements of Style》中的写作理念，他认为代码应当避免冗余，保持精炼。这体现在他将原本约40行的Quicksort实现优化到了十几行，展示了编程之美在于逻辑清晰、效率高的同时，还能保持代码的优雅性。《Programming Pearls》不仅包含了深入浅出的小案例和实际例子，还提供了丰富的学习材料，适合学生和经验丰富的程序员阅读，通过这些实例学习如何设计和创造程序，以及如何思考编程问题。书中每章都包含几个栏目，如"Cracking the Oyster"启发读者解决问题的新视角，"Aha! Algorithms"提供算法设计的思考路径，"Writing Correct Programs"关注程序正确性的保证，而"ASmall Matter of Programming"则探讨编程细节的艺术。此外，网站上提供了书中部分内容的样本供读者探索，教师可以利用书中的链接找到适合课堂使用的材料。Steve McConnell赞誉这本书为"设计小型作品的庆典"，鼓励读者通过浏览网站进一步感受设计之美。新网站上不断更新的内容，包括从书中摘录的部分，如目录、前言以及关于性能、算法背后原理、正确编写程序技巧等主题的深入讨论。这本书不仅仅是一本技术手册，更是一部启发思考、提升编程技艺的宝典，对于任何追求编程艺术的人来说，都是一份宝贵的资源。

Word Frequencies

(Illustrating Section 15.1 of

Programming Pearls)

Section 15.1 describes word frequencies and gives an example. Here are

some more examples, generated

by this program from the King James

Bible (789,616 words), the Iliad (153,210 words), and Programming Pearls

(79,525 words). This table shows the 40 most common words, and their

percentage in the document.

BIBLE % ILIAD % PEARLS %

the 7.86 the 6.25 the 5.64

and 4.88 and 4.23 of 2.76

of 4.35 of 3.64 a 2.43

to 1.69 to 2.15 to 2.18

And 1.61 his 1.62 and 2.01

that 1.57 he 1.60 in 1.96

in 1.54 in 1.42 is 1.36

shall 1.24 a 1.17 that 1.20

he 1.20 with 1.04 The 0.91

unto 1.13 that 0.94 for 0.83

I 1.10 you 0.91 by 0.67

his 1.06 for 0.89 it 0.57

a 1.01 him 0.84 this 0.56

for 0.90 I 0.83 with 0.51

they 0.87 as 0.79 an 0.50

be 0.84 was 0.77 program 0.48

is 0.84 they 0.66 on 0.48

with 0.75 on 0.64 be 0.47

not 0.74 from 0.64 are 0.47

all 0.66 but 0.58 as 0.45

thou 0.59 son 0.58 we 0.43

thy 0.56 had 0.58 at 0.39

was 0.56 not 0.56 can 0.39

it 0.56 their 0.56 time 0.38

which 0.54 it 0.56 I 0.36

my 0.52 is 0.50 was 0.35

LORD 0.50 will 0.49 you 0.33

their 0.49 have 0.48 code 0.33

have 0.48 all 0.47 from 0.28

will 0.47 by 0.47 or 0.26

from 0.45 them 0.46 its 0.26

ye 0.45 were 0.43 one 0.25

them 0.44 at 0.43 This 0.25

as 0.41 who 0.42 array 0.25

him 0.40 my 0.40 have 0.25

are 0.36 so 0.40 two 0.25

upon 0.34 your 0.38 each 0.25

were 0.34 when 0.37 first 0.24

by 0.32 be 0.36 search 0.24

when 0.31 upon 0.35 function 0.23

Phrases

(Section 15.2 of

Programming Pearls)

Words are the basic component of documents, and many

important problems can be solved by searching for words.

Sometimes, however, I search long strings (my documents, or

help files, or web pages, or even the entire web) for phrases,

such as ``substring searching'' or ``implicit data structures''.

How would you search through a large body of text to find ``a

phrase of several words''? If you had never seen the body of text

before, you would have no choice but to start at the beginning

and scan through the whole input; most algorithms texts

describe many approaches to this ``substring searching problem''.

Suppose, though, that you had a chance to preprocess the body of text before performing searches. You could make

a hash table (or search tree) to index every distinct word of the document, and store a list of every occurrence of

each word. Such an ``inverted index'' allows a program to look up a given word quickly. One can look up phrases

by intersecting the lists of the words they contain, but this is subtle to implement and potentially slow. (Some web

search engines do, however, take exactly this approach.)

We'll turn now to a powerful data structure and apply it to a small problem: given an input file of text, find the

longest duplicated substring of characters in it. For instance, the longest repeated string in ``Ask not what your

country can do for you, but what you can do for your country'' is `` can do for you'', with `` your country'' a close

second place. How would you write a program to solve this problem?

[Click for more examples of long repeated strings]

This problem is reminiscent of the anagram problem that we saw in Section 2.4. If the input string is stored in

c[0..n-1], then we could start by comparing every pair of substrings using pseudocode like this

maxlen = -1

for i = [0, n)

for j = (i, n)

if (thislen = comlen(&c[i], &c[j])) > maxlen

maxlen = thislen

maxi = i

maxj = j

The comlen function returns the length that its two parameter strings have in common, starting with their first

characters:

int comlen(char *p, char *q)

剩余282页未读，继续阅读

飞翔的马桶

粉丝: 8
资源: 7

编程珠玑：优雅Quicksort算法与编程艺术

编程珠玑+第二版(Programming+Pearls,2nd+Edition)(英文版+中文版+源码打包)PDF高清.rar

Programming Pearls

编程珠玑II(More programming Pearls) pdf

c++ gems: programming pearls

Paint Pearls c++怎么做

推荐程序员必读的10本书

数据结构书籍和网课推荐

想要学习算法有什么书可以推荐一下

数据结构与算法设计相关学习书籍

算法类的经典书籍有那些

最新资源