出自上帝之手的精妙算法 - Algorithm from THE BOOK (1)

本文主要是介绍出自上帝之手的精妙算法 - Algorithm from THE BOOK (1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

《Proofs from THE BOOK》是一本非常出名的书籍，收录了不少精妙的证明。

类似地，在cstheory.stackexchange.com上有人召集大家讨论假如上帝有一本书收集精妙的算法，那么，那本书应该包含一些什么算法呢？ "Proof from THE BOOK" 中译本翻译为“来自圣经的证明” 或者 “数学天书中的证明”。天书，听上去似乎是比较难于看明白的艰难的证明。然而，恰恰相反，收录的证明都是非常巧妙，优美，容易理解的。因此，我更倾向于翻译为“出自上帝之手的”。

Algorithm from THE BOOK 讨论中包含的算法，普遍也属于优美有效的，让人称绝的。花了一些时间整理了下，顺序按照大家的投票。上面包含很多已经耳熟能详的大名鼎鼎的算法，也包含一些我还不了解的。稍后，可以学习下其中尚未熟悉的算法，体会其中的巧妙思想和优美设计。

原讨论帖链接：http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book?page=1&tab=votes#tab-top

Algorithm from THE BOOK 候选：

1. 并查集. 维护等价关系的更新和查询的数据结构

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

2. KMP字符串匹配算法

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

3. BFPRT算法. 寻找第k大元素的线性算法

名字来源于发明算法的五位大牛: Blum,Floyd,Pratt,Rivest,Tarjan

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

http://en.wikipedia.org/wiki/Median_of_medians

4. 二分查找算法