快速排序是一种排序算法，速度比选择排序快得多，其主要基于“分而治之”的思想对集合进行排序，本文将对该算法进行分析。
2. 分而治之(D&C)的思想D&C主要指利用递归的方式来不断的缩小需要处理问题的规模，最终使问题容易解决。使用D&C解决问题的过程包括两个步骤。
(1) 找出递归的终止条件，这种条件必须尽可能简单（称为基线
条件）。
(2) 不断将问题分解（或者说缩小规模），直到符合递归的终止条件(称为归纳条件)。
为了便于理解，举个例子。
假设有一个数组A=[2,4,6], 想要统计A所有元素的和，可以使用两种方式
遍历A,并将结果一个一个的加起来使用D&C思想，通过不断缩小集合的规模，最终把每次递归的结果加起来，流程如下
代码如下：
快速排序的流程大概分为两步：
确定递归的终止条件：对于排序操作而言，如果数组为空或只包含一个元素，则只需原样返回数组且不用排序。因此数组为空或只包含一个元素可以作为循环结束的条件
如果没有满足递归终止条件，需要将数组分解，并做以下操作，直到满足递归终止条件。
2.1. 从数组中选择一个元素，这个元素被称为基准值
2.2. 将数组分成两个子数组：小于基准值的元素和大于基准值的元素
2.3. 对步骤2产生的两个子数组再执行快速排序操作
假设要对[2,1,3,5,4]进行排序，选择了3为基准值，则流程大概如下：
对于快速排序，在基线条件中，我证明这种算法对空数组或包含一个
元素的数组管用。在归纳条件中，如果快速排序对包含一个元素的数组管用，对包含两个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，以此类推。因此，可以说明快速排序对任何长度的数组都管用。
快速排序的平均情况运行的时间复杂度为O(n log n),但在最糟糕的情况下其复杂度将为O(n^2),下面对两种情况进行分析
4.1 最糟糕情况下面来看看到底啥时候才会出现最糟糕的情况，考虑如下的排序：
快速排序的性能高度依赖于你选择的基准值。假设你总是将第一个元素用作基准值，且要处
理的数组是有序的。由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序，需要进行N层操作，每层需要比较N个数。所以算法复杂度为O(n^2)
考虑如下排序:
该图也是对有序数组进行排序，但每次都选择中间的元素作为基准值，此时递归的次数变成了3次(logN),每次也是需要比较N个元素，所以算法复杂度为O(n log n)
5. 代码实现为了简单演示，代码都始终选用第一个元素作为基准值
Python版本：
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([3,5,6,2,6,2]) 总结 D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。快速排序的平均运行时间为O(n log n)。当数组有序，始终选择第一元素作为基准值时，快速排序将出现最糟情况当数组有序，始终选择中间元素作为基准值时，快速排序将出现最佳情况