时间复杂度
平均情况：O(nlgn)
最坏情况：O(n*n)，发生在当数据已经是排序状态时
快排算法的基本原理
1、从数据中选取一个值a[i]作为参考
2、以a[i] 为参考，将数据分成2部分：P1、P2，P1中的数据全部≤a[i]，P2中的数据全部＞a[i]，数据变为｛｛P1｝｛a[i]｝｛P2｝｝
3、将P1、P2重复上述步骤，直到各部分中只剩1个数据
4、数据完成升序排列
基本示例：
原始数据：
第1步：选取第1个数据：3
第2步：将数据分成2部分，左边≤3，右边大于>3：
第3步：将各部分重复以上步骤，直到每部分只剩1个数据：
第4步：数据完成升序排列：
程序中数据通常保存在数组中，以int类型的数组为例，可以将上面的步骤写成一个quickSort函数原型：
算法优化
上面这个快速排序算法可以说是最基本的快速排序，因为它并没有考虑任何输入数据。但是，我们很容易发现这个算法的缺陷：这就是在我们输入数据基本有序甚至完全有序的时候，这算法退化为冒泡排序，不再是O(n㏒n)，而是O(n^2)了。
究其根源，在于我们的代码实现中，每次只从数组第一个开始取。如果我们采用“三者取中”，即arr[low],arr[high],arr[（low+high）/2]三者的中值作为枢轴记录，则可以大大提高快速排序在最坏情况下的性能。但是，我们仍然无法将它在数组有序情形下的性能提高到O(n)。还有一些方法可以不同程度地提高快速排序在最坏情况下的时间性能。
此外，快速排序需要一个递归栈，通常情况下这个栈不会很深，为log(n)级别。但是，如果每次划分的两个数组长度严重失衡，则为最坏情况，栈的深度将增加到O(n)。此时，由栈空间带来的空间复杂度不可忽略。如果加上额外变量的开销，这里甚至可能达到恐怖的O(n^2)空间复杂度。所以，快速排序的最差空间复杂度不是一个定值，甚至可能不在一个级别。
为了解决这个问题，我们可以在每次划分后比较两端的长度，并先对短的序列进行排序（目的是先结束这些栈以释放空间），可以将最大深度降回到O(㏒n)级别。
这里提出对快速排序的3点优化思路：
对于小数组，可以采用插入排序，避免递归调用。例如，当if(hi <= lo + M)时，就可以转到插入排序。
采用子数组的一部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。
如果数组中含有大量的重复元素，可以采用三向切分。将数组切分为三部分，分别对应于小于、等于和大于切分元素的数组元素。代码实现如下：
