Some Information in Study

Books recommended by programmer
1、《Code Complete(2nd Ed) by Steve McConnell》
2、《The Pragmatic Programmer》
3、《Structure and Interpretation of Computer Programs》
4、《The C Programming Language》
5、《Refactoring: Improving the Design of Existing Code》
6、《Introduction to algorithms》
7、《The Mythical Man-Month》
8、《Design Patterns》
9、《The Art of Computer Programming(First Volume Hardcover)》
10、《Compilers: Principles, Techniques, and Tools 》
11、《Head-First Design Patterns》
12、

How to Learn Machine Learning and Data Mining
1、《机器学习实战》
2、《数据挖掘——实用机器学习学习技术》
3、《数据挖掘：概念和技术》
4、《统计学习基础 数据挖掘、推理和预测》
5、《机器学习》 （Mitchell）
6、《统计学习方法》
7、《机器学习导论》
8、《机器学习及其应用》
9、《模式分类》
10、《推荐系统实践》
11、《深入搜索引擎：海量信息的压缩、索引和查询》
12、《概率论和数理统计》
13、《大数据：互联网大规模数据挖掘与分布式处理》
14、《Web数据开发》
15、《数据之巅》
16、《深入浅出统计学》
17、《矩阵分析》
18、台大林轩田的《机器学习基石》和《机器学习技法》公开课
https://class.coursera.org/ntumlone-001

How to Learn Algorithm
1、《Algorithm》， Robert Sedgewick（in Coursera has lesson）
2、《算法导论》
3、《数据结构与算法分析》
4、《数据结构》，邓俊辉的MOOC
5、《Book of Elementary Algorithm and Data Structure》
6、《编程珠玑》
7、《Purely functional data structure》，Chris Okasaki
8、《啊哈，算法》
9、《算法的乐趣》
10、《算法问题实战策略》
11、《挑战程序设计竞赛》
12、《算法帝国》
13、Visual Data Structure：
http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

How to Learn Digital Circuit Design
1、《微处理器设计——从设计规划到工艺制造》， Grant McFarland
2、《CPU自制入门》
3、《Testing of digital systems》
4、《IC Compiler student guide》
5、Rabaey and Weste & Harris’s Book
6、CMOS Digital Integrated Circuits, S. –M. Kang and Y. Leblebici, Mc Graw Hill, 3 rd edition, 2003
7、CMOS数字集成电路：分析与设计（第3版）
8、CMOS VLSI Design A Circuits and Systems Perspective 4th Edition

How To Do Research
1. 确定你感兴趣要研究的领域（大方向）
2. 搜集该领域的所有顶级期刊和顶级会议（影响因子至少在2.0以上）
3. 确定更具体的研究方向（小方向，某一类还未有成熟解法的开放问题）
4. 搜集对这一类问题求解的所有经典论文，2000年以前的成果可以直接找书看，2000年以后的建议看论文，毕竟书本至少滞后学术5年以上。
5. 搜集出现在顶级期刊和顶级会议上关于这一问题的最新论文成果，通常是近3年内。
然后就是真正的苦力活了。
1. 看懂你搜集的经典论文，这里会要求一定的数学基础，所以你至少要先达到做你感兴趣的研究需要的数学基础。
2. 对这些经典论文逐一用代码实现，你如果有大公司的编程经验，你将在这里甩开没有编程经验的没去公司工作过的科班学生几条街，这是作为有工程经验回头搞研究最大的优势。虽然通常经典论文都会有现成的代码，但自己动手实现一遍对于深刻理解是必不可少的。
3. 阅读关于这一类问题的最新论文成果，看看其他人关于这个问题还在哪个方面努力，然后根据你对这一问题的理解并参考最新论文，思考出一个新的角度，并从这一角度出发尝试解决这一大类问题。
http://www.zhihu.com/question/31093017/answer/54234678

NLP Library in Python
1.NLTK
NLTK 在使用 Python 处理自然语言的工具中处于领先的地位。它提供了 WordNet 这种方便处理词汇资源的接口，以及分类、分词、词干提取、标注、语法分析、语义推理等类库。
网站：
http://www.nltk.org/
安装：
安装 NLTK: sudo pip install -U nltk
安装 Numpy (可选): sudo pip install -U numpy
安装测试: python then type import nltk
2.Pattern
Pattern 拥有一系列的自然语言处理工具，比如说词性标注工具(Part-Of-Speech Tagger)，N元搜索(n-gram search)，情感分析(sentiment analysis)，WordNet。它也支持机器学习的向量空间模型，聚类，向量机。
网站:
https://github.com/clips/pattern
安装:
pip install pattern
3.TextBlob
TextBlob 是一个处理文本数据的 Python 库。它提供了一个简单的 api 来解决一些常见的自然语言处理任务，例如词性标注、名词短语抽取、情感分析、分类、翻译等等。
网站：
http://textblob.readthedocs.org/en/dev/
安装：
pip install -U textblob
4.Gensim
Gensim 是一个 Python 库，用于对大型语料库进行主题建模、文件索引、相似度检索等。它可以处理大于内存的输入数据。作者说它是“纯文本上无监督的语义建模最健壮、高效、易用的软件。”
网站：
https://github.com/piskvorky/gensim
安装：
pip install -U gensim
5.PyNLPI
它的全称是：Python 自然语言处理库（Python Natural Language Processing Library，音发作: pineapple） 是一个用于自然语言处理任务库。它集合了各种独立或松散互相关的，那些常见的、不常见的、对NLP 任务有用的模块。PyNLPI 可以用来处理 N 元搜索，计算频率表和分布，建立语言模型。它还可以处理向优先队列这种更加复杂的数据结构，或者像 Beam 搜索这种更加复杂的算法。
安装：
LInux:sudo apt-get install pymol
Fedora:yum install pymol
6.spaCy
这是一个商业的开源软件。结合了Python 和Cython 优异的 NLP 工具。是快速的，最先进的自然语言处理工具。
网站：
https://github.com/proycon/pynlpl
安装：
pip install spacy
7.Polyglot
Polyglot 支持大规模多语言应用程序的处理。它支持165种语言的分词，196中语言的辨识，40种语言的专有名词识别，16种语言的词性标注，136种语言的情感分析，137种语言的嵌入，135种语言的形态分析，以及69种语言的翻译。
网站：
https://pypi.python.org/pypi/polyglot
安装：
pip install polyglot
8.MontyLingua
MontyLingua 是一个免费的、功能强大的、端到端的英文处理工具。在 MontyLingua 输入原始英文文本 ，输出就会得到这段文本的语义解释。它适用于信息检索和提取，请求处理，问答系统。从英文文本中，它能提取出主动宾元组，形容词、名词和动词短语，人名、地名、事件，日期和时间等语义信息。
网站：
http://web.media.mit.edu/~hugo/montylingua/
9.BLLIP Parser
BLLIP Parser（也叫做 Charniak-Johnson parser）是一个集成了生成成分分析器和最大熵排序的统计自然语言分析器。它包括命令行和python接口。
10.Quepy
Quepy 是一个 Python 框架，提供了将自然语言问题转换成为数据库查询语言中的查询。它可以方便地自定义自然语言中不同类型的问题和数据库查询。所以，通过 Quepy，仅仅修改几行代码，就可以构建你自己的自然语言查询数据库系统。
网站：
https://github.com/machinalis/quepy
http://quepy.machinalis.com/

Using HMM to Produce Article
马尔可夫模型有个很酷的应用是一种语言模型，在这个模型中，我们根据当前的一个或几个词预测下一个词是什么。如果我们只是根据上一个词预测，则它是一个一阶马尔可夫模型。如果我们用上两个词预测，则它是一个二阶马尔可夫模型。
在我的实例中，我使用Henry Thoreau的小说Walden做训练。为了好做实验，我也加入了Nietszche的Thus Spoke Zarathustra，以及一些Obama的演讲。无论你训练什么样的文本，模型都会生成相似的结果，是不是很酷？
首先我们引入NLTK，它是Python中最好的NLP库。我想说，虽然我们这里做的自然语言处理很简单，但NLTK的内置函数还是帮我节省了很多代码。然后我们利用split()函数将字符串（从文本文件中获得的）转换成一个数组。

import nltk
import random
file = open('Text/Walden.txt', 'r')
walden = file.read()
walden = walden.split()

上边两个函数是代码的基本函数。我们最终要使用的NLTK中的“条件频率字典”必须以成对数组作为输入，所以短语“Hi my name is Alex”需要变为[(“Hi”, “my”), (“my, “name”), (“name”, “is”), (“is”, “Alex”)]。函数makePairs以一个数组（以词分割字符串得到）作为输入，输出符合上边格式的数组。
生成文章的方法，需要一个条件频率分布作为输入。想想看，“农场”的后边每一个词出现的次数是多少？这是一个“条件频率分布”的输出（对于所有的词，而不只是“农场”）。生成函数的其余部分是根据训练数据中观察到的分布输出文本。我通过创建一个出现在当前词后边的每一个词组成的数组实现这一点。数组中也有正确的计数，因此，接下来我只需要随机选择数组中的一个词即可，而这个过程也是服从分布的。

def makePairs(arr):
  pairs = []
  for i in range(len(arr)):
      if i < len(arr)-1:
          temp = (arr[i], arr[i+1])
          pairs.append(temp)
  return pairs

def generate(cfd, word = 'the', num = 50):
  for i in range(num):
      arr = []                 
      # make an array with the words shown by proper count
      for j in cfd[word]:
          for k in range(cfd[word][j]):
              arr.append(j)

      print(word, end=' ')
      word = arr[int((len(arr))*random.random())]

最后三行代码，我们输出了一些很像Walden风格的文本。

pairs = makePairs(walden)
cfd = nltk.ConditionalFreqDist(pairs)
generate(cfd)

输出结果：
我建议你看一下我Github上的iPython笔记，因为我继续完成了一个方法。利用这个方法，你只需要输入一个文件名，它就能输出生成的文本。Obama的例子也非常的酷。
如果你想自己尝试一下，只需要创建一个文本文件，然后把它放在合适的目录即可。
http://python.jobbole.com/81966/

Page Rank and Map Reduce
一、什么是pagerank
PageRank的Page可是认为是网页，表示网页排名，也可以认为是Larry Page(google 产品经理)，因为他是这个算法的发明者之一，还是google CEO（^_^）。PageRank算法计算每一个网页的PageRank值，然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。
二、最简单pagerank模型
互联网中的网页可以看出是一个有向图，其中网页是结点，如果网页A有链接到网页B，则存在一条有向边A->B。
这个例子中只有四个网页，如果当前在A网页，那么悠闲的上网者将会各以1/3的概率跳转到B、C、D，这里的3表示A有3条出链，如果一个网页有k条出链，那么跳转任意一个出链上的概率是1/k，同理D到B、C的概率各为1/2，而B到C的概率为0。一般用转移矩阵表示上网者的跳转概率，如果用n表示网页的数目，则转移矩阵M是一个n*n的方阵；如果网页j有k个出链，那么对每一个出链指向的网页i，有M[i][j]=1/k，而其他网页的M[i][j]=0。
初试时，假设上网者在每一个网页的概率都是相等的，即1/n，于是初试的概率分布就是一个所有值都为1/n的n维列向量V0，用V0去右乘转移矩阵M，就得到了第一步之后上网者的概率分布向量MV0,（nXn）*(nX1)依然得到一个nX1的矩阵。
注意矩阵M中M[i][j]不为0表示用一个链接从j指向i，M的第一行乘以V0，表示累加所有网页到网页A的概率即得到9/24。得到了V1后，再用V1去右乘M得到V2，一直下去，最终V会收敛，即Vn=MV(n-1)，上面的图示例，不断的迭代，最终V=[3/9,2/9,2/9,2/9]‘：
三、终止点问题
互联网上的网页不满足强连通的特性，因为有一些网页不指向任何网页，如果按照上面的计算，上网者到达这样的网页后便走投无路、四顾茫然，导致前面累计得到的转移概率被清零，这样下去，最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉，C变成了一个终止点。
四、陷阱问题
另外一个问题就是陷阱问题，即有些网页不存在指向其他网页的链接，但存在指向自己的链接。
上网者跑到C网页后，就像跳进了陷阱，陷入了漩涡，再也不能从C中出来，将最终导致概率分布值全部转移到C上来，这使得其他网页的概率分布值为0，从而整个网页排名就失去了意义。如果按照上面图对应的转移矩阵。
五、解决终止点问题和陷阱问题
上面过程，我们忽略了一个问题，那就是上网者是一个悠闲的上网者，而不是一个愚蠢的上网者，我们的上网者是聪明而悠闲，他悠闲，漫无目的，总是随机的选择网页，他聪明，在走到一个终结网页或者一个陷阱网页（比如两个示例中的C），不会傻傻的干着急，他会在浏览器的地址随机输入一个地址，当然这个地址可能又是原来的网页，但这里给了他一个逃离的机会，让他离开这万丈深渊。模拟聪明而又悠闲的上网者，对算法进行改进，每一步，上网者可能都不想看当前网页了，不看当前网页也就不会点击上面的连接，而上悄悄地在地址栏输入另外一个地址，而在地址栏输入而跳转到各个网页的概率是1/n。假设上网者每一步查看当前网页的概率为a，那么他从浏览器地址栏跳转的概率为(1-a)，于是原来的迭代公式。
六、用Map-reduce计算Page Rank
上面的演算过程，采用矩阵相乘，不断迭代，直到迭代前后概率分布向量的值变化不大，一般迭代到30次以上就收敛了。真的的web结构的转移矩阵非常大，目前的网页数量已经超过100亿，转移矩阵是100亿*100亿的矩阵，直接按矩阵乘法的计算方法不可行，需要借助Map-Reduce的计算方式来解决。实际上，google发明Map-Reduce最初就是为了分布式计算大规模网页的pagerank，Map-Reduce的pagerank有很多实现方式，我这里计算一种简单的。
考虑转移矩阵是一个很多的稀疏矩阵，我们可以用稀疏矩阵的形式表示，我们把web图中的每一个网页及其链出的网页作为一行，这样第四节中的web图结构用如下方式表示：
1 A B C D
2 B A D
3 C C
4 D B C
A有三条出链，分布指向A、B、C，实际上，我们爬取的网页结构数据就是这样的。
1、Map阶段
Map操作的每一行，对所有出链发射当前网页概率值的1/k，k是当前网页的出链数，比如对第一行输出

1 #!/bin/python
2 '''Mapper for sort'''
3 import sys
4 for line in sys.stdin:
5      print line.strip()

SortReducer.py也是一样

1 #!/bin/python
2 '''Reducer for sort'''
3 import sys
4 for line in sys.stdin:
5       print line.strip()

PageRankMapper.py代码:

1 ''' mapper of pangerank algorithm'''
2 import sys
3 id1 = id2 = None
4 heros = value = None
5 count1 = count2 = 0
6
7 for line in sys.stdin:
8     data = line.strip().split('\t')
9     if len(data) == 3 and data[1] == 'a':# This is the pangerank value
10         count1 += 1
11         if count1 >= 2:
12             print '%s\t%s' % (id1,0.0)
13            
14         id1 = data[0]
15         value = float(data[2])
16     else:#This the link relation
17         id2 = data[0]
18         heros = data[1:]
19     if id1 == id2 and id1:
20         v = value / len(heros)
21         for hero in heros:
22             print '%s\t%s' % (hero,v)
23         print '%s\t%s' % (id1,0.0)
24         id1 = id2 = None
25         count1 = 0

PageRankReducer.py代码:

1 ''' reducer of pagerank algorithm'''
2 import sys
3 last = None
4 values = 0.0
5 alpha = 0.8
6 N = 4# Size of the web pages
7 for line in sys.stdin:
8     data = line.strip().split('\t')
9     hero,value = data[0],float(data[1])
10     if data[0] != last:
11         if last:
12             values = alpha * values + (1 - alpha) / N
13             print '%s\ta\t%s' % (last,values)
14         last = data[0]
15         values = value
16     else:
17         values += value #accumulate the page rank value
18 if last:
19     values = alpha * values + (1 - alpha) / N
20     print '%s\ta\t%s' % (last,values)

在linux下模仿Map-Reduce的过程：

1 #!/bin/bash
2 PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games
3 export PATH
4 max=10
5 for i in seq 1 $max
6 do
7 echo “$i”
8 cat links.txt pangerank.value > tmp.txt
9 cat tmp.txt |sort|python PageRankMapper.py |sort|python PageRankReducer.py >pangerank.value
10 done

这个代码不用改动就可以直接在hadoop上跑起来。调用hadoop命令：

1 #!/bin/bash
2
3 #sort
4 mapper=SortMapper.py
5 reducer=SortReducer.py
6 input="yours HDFS dir"/links.txt
7 input="yours HDFS dir"/pagerank.value
8 output="yours HDFS dir"/tmp.txt
9
10 hadoop jar contrib/streaming/hadoop-*streaming*.jar
11     -mapper /home/hduser/mapper.py
12     -reducer /home/hduser/reducer.py
13     -input $input
14     -output $output
15    
16    
17 #Caculator PageRank
18 mapper=PageRankMapper.py
19 reducer=PageRankReducer.py
20 input="yours HDFS dir"/tmp.txt
21 output="yours HDFS dir"/pagerank.value
22
23 hadoop jar contrib/streaming/hadoop-*streaming*.jar
24     -mapper /home/hduser/mapper.py
25     -reducer /home/hduser/reducer.py
26     -input $input
27     -output $output

第四步中带环的陷阱图，迭代40次，权值a取0.8，计算结果如下：

1 A B C D
2 0.15 0.216666666667 0.416666666667 0.216666666667
3 0.136666666666 0.176666666666 0.51 0.176666666666
4 0.120666666666 0.157111111111 0.565111111111 0.157111111111
5 0.112844444444 0.145022222222 0.597111111111 0.145022222222
6 0.108008888889 0.138100740741 0.615789629629 0.138100740741
7 0.105240296296 0.134042666667 0.62667437037 0.134042666667
8 0.103617066667 0.131681145679 0.633020641975 0.131681145679
9 0.102672458272 0.130303676049 0.636720189629 0.130303676049
10 0.10212147042 0.129500792625 0.638876944329 0.129500792625
11 0.10180031705 0.129032709162 0.640134264625 0.129032709162
12 0.101613083665 0.128759834878 0.640867246578 0.128759834878
13 0.101503933951 0.128600756262 0.641294553524 0.128600756262
14 0.101440302505 0.128508018225 0.641543661044 0.128508018225
15 0.10140320729 0.128453954625 0.64168888346 0.128453954625
16 0.10138158185 0.128422437127 0.641773543895 0.128422437127
17 0.101368974851 0.128404063344 0.64182289846 0.128404063344
18 0.101361625338 0.128393351965 0.641851670733 0.128393351965
19 0.101357340786 0.128387107543 0.641868444129 0.128387107543
20 0.101354843017 0.128383467227 0.64187822253 0.128383467227
21 0.101353386891 0.128381345029 0.641883923053 0.128381345029
22 0.101352538012 0.128380107849 0.641887246292 0.128380107849
23 0.10135204314 0.128379386609 0.641889183643 0.128379386609
24 0.101351754644 0.128378966148 0.641890313062 0.128378966148
25 0.101351586459 0.128378721031 0.641890971481 0.128378721031
26 0.101351488412 0.128378578135 0.64189135532 0.128378578135
27 0.101351431254 0.128378494831 0.641891579087 0.128378494831
28 0.101351397932 0.128378446267 0.641891709536 0.128378446267
29 0.101351378507 0.128378417955 0.641891785584 0.128378417955
30 0.101351367182 0.128378401451 0.641891829918 0.128378401451
31 0.10135136058 0.128378391829 0.641891855763 0.128378391829
32 0.101351356732 0.12837838622 0.64189187083 0.12837838622
33 0.101351354488 0.12837838295 0.641891879614 0.12837838295
34 0.10135135318 0.128378381043 0.641891884735 0.128378381043
35 0.101351352417 0.128378379932 0.64189188772 0.128378379932
36 0.101351351973 0.128378379284 0.64189188946 0.128378379284
37 0.101351351714 0.128378378906 0.641891890474 0.128378378906
38 0.101351351562 0.128378378686 0.641891891065 0.128378378686
39 0.101351351474 0.128378378558 0.64189189141 0.128378378558
40 0.101351351423 0.128378378483 0.641891891611 0.128378378483
41 0.101351351393 0.128378378439 0.641891891728 0.128378378439
可以看到pagerank值已经基本趋于稳定，并与第四步的分数表示一致。
PageRank的简介就介绍到这里了，如果想深入可以参考原论文或者下面的参考文献
参考文献:
1.《Mining of Massive Datasets》
2.《An introduction to information retrival》
3.使用python操作Hadoop
4.js可视化展示PageRank计算过程(可能需要梯子)，可访问作者博客.
http://www.cnblogs.com/fengfenggirl/p/pagerank-introduction.html

Eight Sorting Algorithm By Python
1、插入排序

描述

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

代码实现

def insert_sort(lists):
    # 插入排序
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

2、希尔排序

描述

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

代码实现

def shell_sort(lists):
    # 希尔排序
    count = len(lists)
    step = 2
    group = count / step
    while group > 0:
        for i in range(0, group):
            j = i + group
            while j < count:
                k = j - group
                key = lists[j]
                while k >= 0:
                    if lists[k] > key:
                        lists[k + group] = lists[k]
                        lists[k] = key
                    k -= group
                j += group
        group /= step
    return lists

3、冒泡排序

描述

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

代码实现

def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists

4、快速排序

描述

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码实现

def quick_sort(lists, left, right):
    # 快速排序
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

5、直接选择排序

描述

基本思想：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

代码实现

def select_sort(lists):
    # 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists

6、堆排序

描述

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

代码实现

def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if i < size / 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)

def build_heap(lists, size):
    for i in range(0, (size/2))[::-1]:
        adjust_heap(lists, i, size)

def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)

7、归并排序

描述

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

代码实现

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def merge_sort(lists):
    # 归并排序
    if len(lists) <= 1:
        return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

8、基数排序

描述

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

代码实现

import math
def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k+1):
        for j in lists:
            bucket[j/(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        for z in bucket:
            lists += z
            del z[:]
    return lists

Some Scientific Hot Except DP
1、distributed / stochastic optimization；
2、Human Computation；