本文共 1289 字，大约阅读时间需要 4 分钟。
1. 思路
快速排序基于这样一种想法：给定一个序列，排完之后，数据小的一定在左侧，数据大的一定在右侧。根据这一特性，随机的在序列中取一个数k，只需要把比这个数大的数据换到右侧，比这个数小的数据换到左侧，就完成了一次排序。然后以k为中心，将数组分成两部分，再分别对这两部分做如上操作，直到排完成个序列。这种策略很像老顽童的左右互搏术，或者乾坤大挪移之类的功法，说白了就是来回倒腾。
接下来我们简单描述一下排序过程
a. 对以下数组，取中间数6，我们需要两个索引i和j。其中i从左向右偏移，j从右向左偏移。初始化状态如下图
b. 先走j，[j]<6,所以j不动，而i需要连续索引直到在i=3的位置碰到7.如下
c. 互换[i]与[j]的位置，如下
d. j与i继续索引前行，j停在8位置，i停到4位置
e. [i]与[j]互换结果
f. 继续
g. 结果
h. 直到 i与j相遇，既i==j
最终
由此我们得到了一个大致有序的序列，并且以6为中点，将数组分成了两部分。我们可以分别对两个数组进行如上操作，递归的把整个数组处理完毕。这里再不赘述余下部分。
注：整个过程实际上基于两个目的：第一，大踏步互换位置；第二，确定k的最终位置。
2.代码片段
A. 外部调用接口
B. 排序核心逻辑
C. 执行过程
绿色为本次选中的数，红色为出现交换的数，黑色位置不变
3.时间复杂度分析。
我们这里不用复杂的数据逻辑来证明，只给出一个感官上的认识。如果你对数学方面的证明非常好奇，可以参考这篇。
最好情况，数组每次进行折半排序，折半的两个数组是均匀的。这时候层数为logN（折半过程就是把线性N化成logN的过程），对于每一层，比较次数依然我N，所以整个排序的时间复杂度为O(NlogN).
最坏的情况。假设每次取到的都是最小的或者最大的，那么每次折半后数组被分成了0长度和N长度两个数组，有一个数组折半失效了，这个时候的时间复杂度为O(N2)
4.总结与思考
如果大家熟悉归并排序，就会发现这两个排序貌似有点什么关系，而二者又不太一样。实际上，他们的思想是相似又相反的。他们都是源于分治思想，都采用了递归。但是合并算法是先分解后排序，而快速排序是先排序会分解，他们的过程是相反的。
快速排序是不稳定的排序算法，每次取值对他的性能影响非常大。如果能够每次取到中间值，那么算法的性能将会得到改善。典型的优化方法之一就是“三值取中法”，即取序列的第一个值、最后一个值、以及中间值，从这三个值中找出中间值做为参考值来进行每一次排序。这种方法可以避免取到极值的情况（最大值，最小值）。还有一种优化方法叫做“小区间优化法”。根据快速排序过程，我们不难想象，经过若干次分解后，得到的各个小数组是大致有序的。如果大家熟悉的特性，就会马上意识到，这种大致有序的小数组正是插入排序的最爱。所以当数组被到分解到一定程度（一般建议为5---13）,选择插入排序能够极大的提升整体性能。
没有一个万能的算法能够适应所有情况，我们能做的就是根据已知序列的特点以及各个算法的特性来进行合理的组合，最终得到可接受的预期值。