上一篇介绍了归并排序，本文介绍快速排序，顾名思义，应该是综合性能最好的排序了。在具体实现上，往上也有很多的版本，虽然大体思想一致，但是我觉得掌握其中一种最实用的方式就够了，本文的快排思想基于荷兰国旗问题演变，即所谓的三路快排，对于重复元素较多的场景是非常适合的，对于普通场景来说，性能也不弱。

从本文开始就要介绍O(nlogn)复杂度级别的排序算法了，首先登场的是归并排序，这个排序可以解决一些问题，会在文章的后面给出，并且是一个经典的分治思想，即先分隔再合并，将复杂的大问题瓦解为小问题，将若干小问题解决了之后大问题也就迎刃而解了。下面我们来学习一下归并排序的基本原理。

排序算法毋庸置疑，是最重要最重要的基础算法，真正的实际应用中，往往是几种排序算法的组合，因为没有完美的算法，只有适合的算法。学好算法的第一步应该是熟练手写出基本的排序算法，本文应该被放在一篇文章，但是命运的巧合，我还是选择了递归。因为排序算法就摆在那，思想比较清晰，理解上没有难度，但是递归也摆在那，好像简单但是又无从下手。本文先从复杂度比较高但是比较简单的几种排序算法入手。这几种都是O(n^2)的时间复杂度。

掌握对树的基本操作是很重要的，这里所谓的操作是指对树的遍历，以及对树的构造等等。下面通过一些题目来好好研究研究。由于篇幅、时间以及精力有限，本文着重提取两种题型进行分析，都是高频面试问题。

数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3树、红黑树等等。普通的二叉树其实没什么好讲的，就是最多只有两个孩子的树，而二叉搜索树赋予了它一些额外的条件，使得它有了使用的价值，例如根据它的性质，那么中序遍历出来的结果恰好就是有序的结果，故本文着重说明二叉搜索树。

二分查找是比较常见的查找算法，但是它需要一个条件就是数组有序，因此当面试中听到有序数组这个关键词的时候，不妨往二分查找法想一想，或许它就是解开问题的钥匙。

在第一篇文章中为了说明递归如何写，所以对于链表的操作都是用递归来写的，我们发现递归写起来比较简洁，但是执行的过程有点复杂，并且往往在实际的算法中都是要将递归改成循环来做，可以一定程度上减少开销提高性能。下面我们来看看循环如何实现的。

为什么还要再来说说递归问题，因为数据结构中二叉树是比较重要也是比较难的数据结构，它的结构是天生递归的，所以对于二叉树的很多操作都可以用递归来实现，因此递归这一关能尽量理解是最好的，本章从汉诺塔的问题出发，来看看递归的实现原理。

算法入门系列以递归开头，我们知道，递归的编码往往是比较简单的，但是递归的思想往往又是难以理解。在写完这篇笔记之后仍然无法得递归之要领，不过对于如何写递归是有了一定得章法，一句话就是用数据归纳法，先尝试n得情况，再去考虑0或者1得情况，并且保证范围在逐渐缩小并且一定可以结束，下面我们来详细说一说递归。

分布式锁在分布式系统中是非常常见的，redis以及ZK都可以实现分布式锁，在文章Curator从实战的层面进行了实际的分布式锁的实现，具体看这个文章即可。下面是再唠叨唠叨。