快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边，然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1。
2.1 时间复杂度
- 在最好情况下，快速排序算法的时间复杂度为O(nlogn)
- 在最坏情况下，待排序的序列为正序或者逆序，每次划分只得到一个臂上次划分少一个记录的子序列，而且另一个序列还为空。如果递归树画出来，它就是一棵斜树。此时需要执行(n-1)次递归调用，且第i次划分需要经过i-1次关键字的比较才能找到第i个记录，即中轴元素的位置，因此比较次数为：n-1+n-2+n-3+…+1 = n*(n-1)/2 时间复杂度为O(n^2)
2.2 空间复杂度
- 在最好情况下，递归树的深度为logn，其时间复杂度为O(logn)
- 在最坏情况下，需要进行n-1次递归调用，其空间复杂度为O(n)
3.1 普通快速排序
普通快速排序代码如下
3.2 快速排序优化1—-三数取中&&优化不必要的交换
优化点：
优化选取中轴元素
以上代码target 选取的位置是认定了数组元素的首位，但是若这个数值的大小不在整个数组的中间位置，会大大降低快排的性能。target = array[low] 这句就成了一个潜在的性能瓶颈。因此快速排序的速度还取决于这个target关键元素在数组中的位置。
【改进方法】
三数取中法：去三个元素先进行排序，将中间数作为中轴元素，下面的代码选取数组的左、中、右三个数；
优化交换
将上一个代码中的交换改成直接赋值，减少了多次交换数据的操作，在性能上又得到了部分提高
优化1的快速排序代码如下：
3.3 快速排序优化2—-优化递归操作：
递归对性能是有一定影响的，快排在其尾部有两次递归操作，如果待排序的序列划分极端不平衡，递归深度将趋近于n，而不是平衡时的logn。这就不仅仅是速度快慢的问题了，栈的大小是有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多，因此，减少递归会大大提高性能
- 下面是用一次迭代来换取一次递归的代码，此代码主要对快排的递归部分修改，中轴元素的选取和排序部分代码沿用优化1方案的。
3.4 快速排序优化3—-优化小数组时的排序方案
以上两种优化方法是充分利用了快速排序解决大数组排序强大的功能，那么相反的情况，当数组非常小，其实快速排序不如直接插入排序来的好。
本质原因还是因为快速排序用到了递归，在大量数据排序时，这点性能影响可以通过上面的优化方法忽略掉，但是对于一个只有几个元素的数组需要排序时，用快排就像“大炮打蚊子”。
解决方案就是设定一个判断分支：
当数组长度大于7，则使用优化2的快排
当数组长度小于7，则使用直接插入排序