首页 > C/C++语言, Java语言, Python, 技术读物, 杂项资源, 编程语言 > 一些有意思的算法代码

一些有意思的算法代码

2011年11月29日 发表评论 阅读评论 41,029 人阅读    

Keith Schwarz是一个斯坦福大学计算机科学系的讲师。他对编程充满了热情。他的主页上他自己正在实现各种各样的有意思的算法和数据结构,http://www.keithschwarz.com/interesting/, 目前这个网页上有88个(见下面的列表),但这位大哥要干135个,你可以看看他的To-Do List

从这个列表上,我们可以看到,他从去年7月份就在自己实现这些东西了,我把他实现的这些算法转过来,

  • 另一方面我希望这个事可以影响到一些正在学习编程的人。看看别人是怎么学习编程的,希望对你有借鉴作用。
Name Link Date Added Language Description
Binomial Heap (link) 7‑24‑2010 C++ An implementation of a binomial heap data structure for use as a priority queue.
Bounded Priority Queue (link) 7‑24‑2010 C++ An implementation of a priority queue with a fixed upper limit to its size..
Matrix (link) 7‑24‑2010 C++ A collection of classes for manipulating matrices.
VList (link) 8‑16‑2010 Java An implementation of the List abstraction backed by a VList.
Function Wrapper (link) 8‑16‑2010 C++ A C++ wrapper class around unary functions.
String (link) 8‑17‑2010 C++ An implementation of a string abstraction that uses the small string optimization.

nstream (link) 8‑31‑2010 C++ An stream class that sends and receives data over a network.
Snake (link) 8‑31‑2010 C++ An implementation of the game Snake with a rudimentary AI.
Mergesort (link) 9‑14‑2010 C++ An implementation of the mergesort algorithm.
Next Permutation (link) 10‑6‑2010 C++ An implementation of the next_permutation STL algorithm.
Interval Heap (link) 10‑17‑2010 Java An implementation of a double-ended priority queue using an interval heap.
Linear-Time Selection (link) 10‑18‑2010 C++ A deterministic, linear-time selection algorithm using the median-of-medians algorithm.
Heapsort (link) 10‑18‑2010 C++ An implementation of the heapsort algorithm.
Union-Find (link) 10‑19‑2010 Java An implementation of a disjoint-set data structure using a disjoint set forest.
Radix Sort (link) 10‑19‑2010 C++ An implementation of the radix sort algorithm.
Rational (link) 10‑23‑2010 C++ A data structure representing a rational number.
DPLL (link) 10‑23‑2010 Haskell An implementation of the DPLL algorithm for solving CNF-SAT.
Smoothsort (link) 10‑27‑2010 C++ An implementation of the smoothsort algorithm, an adaptive heapsort variant.
Extendible Array (link) 10‑28‑2010 Java dynamic array class with O(1) worst-case runtime lookup and append.
In-Place Merge (link) 10‑29‑2010 C++ An implementation of a merge algorithm that runs in-place.
Random Shuffle (link) 10‑29‑2010 C++ An algorithm for generating a random permutation of a set of elements.
Random Sample (link) 10‑29‑2010 C++ An O(n) time, O(1) space algorithm for randomly choosing k elements out of a stream with uniform probability.
Natural Mergesort (link) 10‑30‑2010 C++ An implementation of natural mergesort, an adaptive variant of mergesort.
Interpolation Search (link) 10‑31‑2010 C++ An implementation of the interpolation search algorithm.
Introsort (link) 10‑31‑2010 C++ An implementation of the introsort algorithm, a fast hybrid of quicksortheapsort, andinsertion sort.
Hashed Array Tree (link) 11‑3‑2010 Java An implementation of a dynamic array backed by a hashed array tree.
Recurrence Solver (link) 11‑13‑2010 C++ A fast algorithm for generating terms of a sequence defined by a linear recurrence relation.
Fibonacci Heap (link) 11‑15‑2010 Java An implementation of a priority queue backed by a Fibonacci heap.
Dijkstra’s Algorithm (link) 11‑16‑2010 Java An implementation of Dijkstra’s algorithm for single-source shortest paths.
Prim’s Algorithm (link) 11‑17‑2010 Java An implementation of Prim’s algorithm for computing minimum spanning trees.
Kruskal’s Algorithm (link) 11‑17‑2010 Java An implementation of Kruskal’s algorithm for computing minimum spanning trees.
Majority Element (link) 11‑17‑2010 C++ A fast, linear-time algorithm for finding the majority element of a data set.
Haar Transform (link) 11‑17‑2010 C++ A set of functions to decompose a sequence of values into a sum of Haar wavelets.
Argmax (link) 11‑19‑2010 C++ A pair of functions to compute the arg min or max of a function on some range.
Derivative (link) 11‑19‑2010 C++ function object that approximates the derivative of a function.
Levenshtein Distance (link) 11‑19‑2010 C++ An algorithm for computing the Levenshtein distance between two sequences.
Skiplist (link) 11‑20‑2010 C++ An implementation of a skip list, a randomized data structure for maintaining a sorted collection.
van Emde Boas Tree (link) 11‑26‑2010 C++ An implementation of a sorted associative array backed by a van Emde Boas tree.
Cuckoo HashMap (link) 11‑27‑2010 Java An implementation of a hash table using cuckoo hashing.
Needleman-Wunsch Algorithm (link) 11‑28‑2010 C++ An implementation of the Needleman-Wunsch algorithm for optimal string alignment.
Treap (link) 11‑28‑2010 C++ An implementation of a sorted associative array backed by a treap.
Floyd-Warshall Algorithm (link) 12‑10‑2010 Java An implementation of the Floyd-Warshall algorithm for all-pairs shortest paths in a graph.
Power Iteration (link) 12‑10‑2010 C++ An implementation of the power iteration algorithm for finding dominant eigenvectors.
Edmonds’s Matching Algorithm (link) 12‑15‑2010 Java An implementation of Edmonds’s matching algorithm for finding maximum matchings in undirected graphs.
Kosaraju’s Algorithm (link) 12‑15‑2010 Java An implementation of Kosaraju’s algorithm algorithm for finding strongly connected components of a directed graph.
2-SAT (link) 12‑15‑2010 Java A linear-time algorithm for solving 2-SAT.
Bellman-Ford Algorithm (link) 12‑17‑2010 Java An implementation of the Bellman-Ford algorithm for single-source shortest paths.
Topological Sort (link) 12‑17‑2010 Java An algorithm for computing a topological sort of a directed acyclic graph.
Graham Scan (link) 12‑19‑2010 C++ An implementation of the Graham scan for finding convex hulls in 2D space.
Bipartite Testing (link) 12‑19‑2010 Java A linear-time algorithm for checking whether a directed graph is bipartite.
Johnson’s Algorithm (link) 12‑19‑2010 Java An implementation of Johnson’s algorithm for all-pairs shortest paths.
Strassen Algorithm (link) 12‑20‑2010 C++ An implementation of the Strassen algorithm for fast matrix multiplication.
Cartesian Tree Sort (link) 12‑21‑2010 C++ An implementation of Cartesian tree sort, an adaptive, out-of-place heapsort variant.
Ford-Fulkerson Algorithm (link) 12‑21‑2010 Java An implementation of the Ford-Fulkerson maximum-flow algorithm.
Scaling Ford-Fulkerson (link) 12‑22‑2010 Java An modification of the Ford-Fulkerson maximum-flow algorithm that uses scaling to achieve polynomial time..
Splay Tree (link) 12‑27‑2010 C++ An implementation of a sorted associative array backed by a splay tree.
Ternary Search Tree (link) 12‑28‑2010 C++ An implementation of a sorted set of strings backed by a ternary search tree.
Ring Buffer (link) 12‑30‑2010 Java An implementation of a FIFO queue using a ring buffer.
AVL Tree (link) 12‑30‑2010 C++ A sorted associative container backed by an AVL tree.
Rabin-Karp Algorithm (link) 1‑1‑2011 C++ An implementation of the Rabin-Karp algorithm for string matching.
RPN Evaluator (link) 1‑18‑2011 C++ / strain A library to tokenize and evaluate simple arithmetic expressions in reverse Polish notation.
Shunting-Yard Algorithm (link) 1‑18‑2011 C++ / strain An implementation of Dijkstra’s shunting-yard algorithm for converting infix expressions to reverse-Polish notation.
Skew Binomial Heap (link) 1‑20‑2011 C++ An implementation of a priority queue backed by a skew binomial heap.
2/3 Heap (link) 3‑1‑2011 C++ An implementation of a priority queue whose branching factor alternates at different levels to maximize performance.
Zeckendorf Logarithm (link) 3‑10‑2011 C++ An algorithm based on Zeckendorf representations that efficiently computes logarithms.
Factoradic Permutations (link) 3‑17‑2011 C++ A set of algorithms for generating permutations using the factoradic number system.
Binary Cyclic Subsets (link) 3‑20‑2011 C++ A set of algorithms for generating subsets in lexicographical order using binary numbers and cyclic shifts.
Fibonacci Iterator (link) 3‑22‑2011 C++ An STL-style iterator for iterating over the Fibonacci numbers.
Fibonacci Search (link) 3‑22‑2011 C++ An implementation of the Fibonacci search algorithm.
Euclid’s Algorithm (link) 4‑18‑2011 Haskell An implementation of Euclid’s algorithm and applications to continued fractions and the extended Euclidean algorithm.
Find Duplicate (link) 4‑18‑2011 Python An algorithm to find a repeated element in an array using Floyd’s cycle-finding algorithm.
Permutation Generator (link) 4‑19‑2011 Python generator for producing all permutations of a list of elements.
Matrix Find (link) 4‑19‑2011 Python A solution to the classic interview question of searching a sorted matrix for a particular value.
Binary GCD (link) 4‑23‑2011 Scheme An implementation of the binary GCD algorithm for computing greatest common divisors of nonnegative integers.
Knuth-Morris-Pratt Algorithm (link) 5‑3‑2011 Python An implementation of the Knuth-Morris-Pratt algorithm for fast string matching.
Kadane’s Algorithm (link) 5‑7‑2011 C++ An implementation of Kadane’s algorithm for solving the maximum-weight subarray problem.
Karatsuba’s Algorithm (link) 8‑15‑2011 Python An implementation of Karatsuba’s algorithm for fast integer multiplication.
Min-Stack (link) 8‑15‑2011 C++ An implementation of a LIFO stack that supports O(1) push, pop, and find-minimum.
Random Bag (link) 8‑15‑2011 Python A data structure that supports insertion and removal of a uniformly-random element.
Min-Queue (link) 8‑15‑2011 C++ An implementation of a FIFO queue that supports O(1) push, pop, and find-minimum.
Lights-Out Solver (link) 8‑29‑2011 C++ A solver for the game Lights Out using Gaussian elimination over GF(2).
Maximum Single-Sell Profit (link) 11‑9‑2011 Python Four algorithms for the maximum single-sell profit problem, each showing off a different algorithmic technique.
Generalized Kadane’s Algorithm (link) 11‑10‑2011 C++ A generalization of Kadane’s algorithm for solving the maximum subarray problem subject to a length restriction.
Longest Range (link) 11‑19‑2011 Java An algorithm for solving the longest contiguous range problem.
Egyptian Fractions (link) 11‑20‑2011 Python An implementation of the greedy algorithm for finding Egyptian fractions.
LL(1) Parser Generator (link) 11‑21‑2011 Java An LL(1) parser generator.
LR(0) Parser Generator (link) 11‑23‑2011 Java An LR(0) parser generator.
Word Ladders (link) 11‑27‑2011 JavaScript A program for finding word ladders between two words.

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell.cn ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
好烂啊有点差凑合看看还不错很精彩 (22 人打了分,平均分: 4.86 )
Loading ... Loading ...
  1. 2011年11月29日11:40 | #1

    “充满了热情” 真让人嫉妒。

  2. Ciel
    2011年11月29日11:46 | #2

    曾经也充满热情, 现在却为面包在打拼

  3. 小北在发飙
    2011年11月29日12:19 | #3

    他的介绍里好像说他是一个Lecturer:“Hello internet! My name is Keith Schwarz, and I’m a lecturer in Stanford’s CS department teaching CS103.”见http://www.keithschwarz.com/me/

  4. millis
    2011年11月29日12:49 | #5

    cool!这是何等的激情!学习算法不难,难的是长期坚持学习算法并practice

  5. kalekale
    2011年11月29日12:49 | #6

    正在念书的童鞋应该好好看看啊!正在工作的同志赶快干活去!

  6. 卢达
    2011年11月29日13:00 | #7

    kalekale :
    正在念书的童鞋应该好好看看啊!正在工作的同志赶快干活去!

    +1

  7. Hedgehog
    2011年11月29日14:12 | #8

    牛!坚持就是胜利,要反思自己的学习之路啊,Practice makes perfect!

  8. 深夜两点
    2011年11月29日16:04 | #9

    数据结构还是c和c夹夹的天下啊。

  9. 2011年11月29日16:30 | #10

    看来对语言的研究也很多,对什么样的应用什么语言更加适合应该有所思考

  10. Softwaring
    2011年11月29日16:44 | #11

    注释好多噢。。。

  11. 2011年11月29日16:47 | #12

    不断的学习算法并且不断的实践,这就是ACM带给我的。。。一个习惯

  12. brilliant
    2011年11月29日19:42 | #13

    @kaitian
    学习acm好榜样

  13. 2011年11月29日21:56 | #14

    真正的大牛啊

  14. fei
    2011年11月29日22:50 | #15

    @卢达
    +1 again

  15. fei
    2011年11月29日22:51 | #16

    卢达 :

    kalekale :
    正在念书的童鞋应该好好看看啊!正在工作的同志赶快干活去!

    +1

    +1 again

  16. Chenyu
    2011年11月30日01:32 | #17

    如果把学编程当一件苦逼事来对待的话不太可能到这个境界的吧,我在美国遇到的geek大部分都是发自心底的觉得编程和算法都很好玩。虽然说自我push是做好一件事情也是产生兴趣的一个好方法,不过我也见过很多国内的童鞋迫于生计做了coder,不论是push他们还是激励他们自我提高,都可以感受到他们的痛苦。

  17. avc
    2011年11月30日08:22 | #18

    这个人好厉害……态度决定一切啊,用这种态度不管做什么事情都能成功,都能变成大牛的。

  18. 无毁湖光
    2011年11月30日09:40 | #19

    好东西,收藏回去正好复习学习下过去学过的和没学过的 :-)

  19. sarstime
    2011年11月30日10:19 | #20

    非常好,是该回炉重新看看这些东西了,不然真的全部忘光了。。。

  20. reneliu
    2011年11月30日14:39 | #21

    http://www.jjj.de/fxt/ 也有很多算法代码,已经结集出书了

  21. 雨过天晴
    2011年11月30日17:35 | #22

    谢谢楼主了,我正想好好补补算法呢,呵呵,可惜我的数学基础实在是太差了

  22. 2011年11月30日22:24 | #23

    好东西,收藏了…

  23. fee
    2011年12月1日13:30 | #24

    Chenyu :
    如果把学编程当一件苦逼事来对待的话不太可能到这个境界的吧,我在美国遇到的geek大部分都是发自心底的觉得编程和算法都很好玩。虽然说自我push是做好一件事情也是产生兴趣的一个好方法,不过我也见过很多国内的童鞋迫于生计做了coder,不论是push他们还是激励他们自我提高,都可以感受到他们的痛苦。

    +1

  24. sarstime
    2011年12月2日09:20 | #25

    可惜我们日常工作中能应用这些算法的机会少之又少,不温故知新恐怕很快就忘记的一干二净了

  25. Logicalmars
    2011年12月3日19:42 | #26

    受你文章的启发,我也做一个类似的网页,欢迎参观,放在Google Site上需要翻墙

    https://sites.google.com/site/menglinhome/icpc-code-library

  26. Mic
    2011年12月3日21:04 | #27

    这种才是程序员

  27. walkerinwind
    2011年12月4日09:23 | #28

    Chenyu :
    如果把学编程当一件苦逼事来对待的话不太可能到这个境界的吧,我在美国遇到的geek大部分都是发自心底的觉得编程和算法都很好玩。虽然说自我push是做好一件事情也是产生兴趣的一个好方法,不过我也见过很多国内的童鞋迫于生计做了coder,不论是push他们还是激励他们自我提高,都可以感受到他们的痛苦。

    ++

    代码如此美妙,为什么一定要将其作为一个苦难的事情呢?

  28. j
    2011年12月5日16:46 | #29

    @walkerinwind

    偶干编程十几年了。也曾充满热情~ 甚至还维持了很多年~不过,这份热情逐渐被无休止的赶工、客户修改要求、又赶工、客户又修改给磨光了。。。

    不过,看到优秀的代码,还是会为之眼前一亮~~ 能尚存一丝梦,就不错了。

  29. 2011年12月6日11:28 | #30

    C++最近学得头都大了。坚持就是胜利啊

  30. liuxiaori
    2011年12月6日13:03 | #31

    Chenyu :
    如果把学编程当一件苦逼事来对待的话不太可能到这个境界的吧,我在美国遇到的geek大部分都是发自心底的觉得编程和算法都很好玩。虽然说自我push是做好一件事情也是产生兴趣的一个好方法,不过我也见过很多国内的童鞋迫于生计做了coder,不论是push他们还是激励他们自我提高,都可以感受到他们的痛苦。

    对对,好多都是听说coder工资高才混进来的。他们根本就不爱程序。

  31. 大头鬼
    2011年12月8日16:44 | #32

    goog links

  32. 2011年12月9日15:24 | #33

    我想当一名程序员!!!!

  33. shuson
    2011年12月29日17:45 | #34

    TO-DO List links to an incorrect URl

  34. 2012年3月16日16:02 | #35

    可惜英文不好啊!

  35. 2012年5月8日13:13 | #36

    好东西,留下坐标。学好了英语再来

  36. 2014年4月20日11:40 | #37

    Thanks for finally talking about >一些有意思的算法代码 酷壳 – CoolShell.cn | 酷 壳 – CoolShell.cn <Loved it!

  37. simple
    2014年7月22日17:52 | #38

    要是这些算法都能通过python实现,哪就更牛了!

  1. 2011年11月29日22:33 | #1
  2. 2011年11月30日23:00 | #2
  3. 2012年5月23日14:39 | #3
  4. 2012年8月20日19:22 | #4
  5. 2012年8月30日09:04 | #5
  6. 2013年10月27日15:25 | #6
  7. 2013年11月22日17:30 | #7