摘要：分治快速排序以下简称快排的核心思想是分治法。第二个元素大于，放于右侧第三个元素小于，放于左侧以此类推，最后一个元素放置完毕后是这样的重复。此时从左到右读出图中曾作为基准值的元素菱形，我们发现已经排序好了。
分治
快速排序（以下简称“快排”）的核心思想是分治法。可以说，分治提供了另一种解决问题的思路。举个例子来进行说明，抓稳扶好，直接开车了……
举例现有一个集合{4,8,2,5,7,-1,3}，我们将对它进行从小到大排序：
1.选取第一个元素4作为基准值，后面的元素逐个和这个基准值比较大小
显然，要么大于，要么小于（ 暂不考虑相等的情况）。
2.按比较大小结果进行安置：大于基准值的元素，置于它的左侧；小于基准值的元素，置于它的右侧（如果有相等情况，左右随意）
为好理解，画出了数轴，将"基准值4"作为中轴线。第二个元素8大于4，放于右侧；第三个元素2小于4，放于左侧……以此类推，最后一个元素放置完毕后是这样的
3.“重复”。先抛开右侧的big集合，专注于左侧集合{2,-1,3}。此时，我们把它当作source，重复第一步的操作。
如此重复下去，直到只剩下一个元素的情况。
此时从左到右读出图中曾作为基准值的元素（菱形）——-1,2,3,4，我们发现已经排序好了。最后给出完整的操作示意图：
每次根据条件划分成两部分，划分后每部分分别治理，即分治。
递归上面的例子中，第三步叫“重复”其实并不准确，真正的名字是递归。
每个递归函数都有两部分：
基线条件：函数不再调用自己，即退出无限循环调用的条件
递归条件：调用自己，且通过一次次调用会逐步靠拢基线条件
拿上一篇文章（【算】选择排序和二分查找）里聊过的二分查找举例：
/** * 二分查找，递归版 * @param target * @param source * @return */ public static int doFind(int target,List快排source){ if(CollectionUtils.isEmpty(source)){ throw new RuntimeException("集合为空"); } int halfIndex = source.size()/2; int halfElement = source.get(halfIndex).getVal(); if(target==halfElement){ //基线条件：如果目标target和中间数相等，bingo！找到了，返回索引 return source.get(halfIndex).getIndex(); }else if(source.size()==1){ //另一个基线条件：就剩下最后一个元素了，仍然与目标target不符，则返回“目标不存在” throw new RuntimeException("目标不存在"); }else{ //递归条件：选取符合条件的那一半集合，递归调用自己 if (target < halfElement) { List tempSource = source.subList(0, halfIndex); return doFind(target, tempSource); } else { List tempSource = source.subList(halfIndex, source.size()); return doFind(target, tempSource); } } }
掌握了递归和分治思想后，快速排序就只剩下编码部分了：
