Python实现的快速排序
今天看了下《算法新解》这本书，很薄的一本书，最开始吸引我的有两点，一个是里面的大量的图，内容相对来说比较清新，第二个是里面的代码是基于Python实现。尽管算法和语言的关联实现差别不是很大，重在思想，我是希望直接一些，能看到最直接的就懒得转换了。
看这本书的时候有几个瞬间突然有顿悟的感觉。
第一个是一般的翻译书的内容背景很难转换，老外举的例子我们很多时候没有代入感。在这里我找到了一些共同的语言，作者看起来是在硅谷工作，举的一个旅行家问题是以旧金山，帕罗奥图，伯克利来说明，一看到这个例子，我就能很快想起之前去那边的行程安排，地图我已经研究得很熟了，所以再看到这个例子完全不会陌生，还多了一些亲切感。这可能就是一些额外的知识补充给带给我的福利吧。
第二个是对于数据结构设计上和算法的密切相关，让我突然理解了数据库中的设计方式。如果说原来是明白了5分，现在是打通了原来的一道壁垒，我能够真正的接受那种设计方式。
第三个是对于算法的设计，排除了我原来的一些盲点。大学看的算法书都很严谨，严谨到很多时候看不懂，越是关键的算法，觉得自己花费的脑细胞越多，但是感觉还是不得要领，今天在这里找到了一些灵感，大概2个多小时的时间，竟然看完了1/3的内容。
算法是程序员的一大利器，做一件事情实现的方式有很多，但是如何平衡找到最合适的方法却很难。记得大学看一个算法，花了好几个小时，结果上课的时候，老师花了不到五分钟就讲完了，然后脑袋一片空白，记得当时学快速排序的时候，感觉这个算法应该是很复杂，感觉理解了，但是很快就忘记了。如果要落到纸面上完全不行。
第四个是对递归的理解。今天看了之后算是刷新自己的认知。里面有句话说的好：递归将人分为三个截然不同的阵营，恨它的，爱它的，和恨了几年又爱上它的。我确切的说也是属于第三种。
使用循环，程序的性能可能而更好，但是使用递归，程序更容易理解。
对于快速排序，算法的思考方式就是由简到难。
如果是一个数，则返回，如果是两个数，直接比较很快就能出结果，我们用雇一个通用思维来考虑，设定一个参考值，如果大于参考值，则在右侧由数组存放，如果小于参考值，则在左侧存放。这样一来，三个数，四个数都是如此的思路。我们就可以使用递归来处理了。
能执行的程序很短，内容如下：
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i<= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([5,11,3,5,8,2,6,7])如果给程序打上日志，简单补充几个print来看看每个节点的执行情况：
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
print("pivot:",pivot)
less = [i for i in array[1:] if i<= pivot]
print("less:",less)
greater = [i for i in array[1:] if i > pivot]
print("greater",greater)
print("sum:",(less) + [pivot] + (greater))
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([5,11,3,5,8,2,6,7])生成的日志如下：
D:\programs\python2.7\python.exe C:/python/kmp/db_ops/quicksort.py
('pivot:', 5)
('less:', [3, 5, 2])
('greater', [11, 8, 6, 7])
('sum:', [3, 5, 2, 5, 11, 8, 6, 7])
('pivot:', 3)
('less:', [2])
('greater', [5])
('sum:', [2, 3, 5])
('pivot:', 11)
('less:', [8, 6, 7])
('greater', [])
('sum:', [8, 6, 7, 11])
('pivot:', 8)
('less:', [6, 7])
('greater', [])
('sum:', [6, 7, 8])
('pivot:', 6)
('less:', [])
('greater', [7])
('sum:', [6, 7])
[2, 3, 5, 5, 6, 7, 8, 11]
Process finished with exit code 0对于分析问题还是大有帮助。程序本身不长，算是我见过最精炼的快排程序了。