基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,
一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤：
1 从数列中挑出一个元素，称为 “基准”（pivot），
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
算法实现(java):
public class QuickSort {
public static void main(String[] args) {
int[] a={5,2,0,7,1,9,45,21,3,-23};
quickSort(a, 0,9); // 0表示第0个数，9表示长度
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
private static void quickSort(int a[],int low,int high){
if(low<high){
int pivot=partition(a, low, high);//将数组分为两部分
quickSort(a, low, pivot-1); //递归排序左子数组
quickSort(a, pivot+1, high); //递归排序右子数组
}
}
private static int partition(int a[],int low,int high){
int pivot=a[low]; //枢轴记录
while(low<high){
while(low<high && a[high]>=pivot)
high--;
a[low]=a[high]; //交换比枢轴小的记录到左端
while(low<high && a[low]<=pivot)
low++;
a[high]=a[low]; //交换比枢轴小的记录到右端
}
a[low]=pivot; //扫描完成，枢轴到位
return low; //返回的是枢轴的位置
}
}
算法分析：
时间复杂度：
可以看出，每一次调用partition()方法都需要扫描一遍数组长度（注意，在递归的时候这个长度并不是原数组的长度n，而是被分隔出来的小数组，即n*(2^(-i))），其中i为调用深度。而在这一层同样长度的数组有2^i个。那么，每层排序大约需要O(n)复杂度。而一个长度为n的数组，调用深度最多为log(n)层。二者相乘，得到快速排序的平均复杂度为O(n ㏒n)。
通常，快速排序被认为是在所有同数量级的排序方法中，平均性能最好。
从代码中可以很容易地看出，快速排序单个栈的空间复杂度不高，每次调用partition方法时，其额外开销只有O(1)。所以，最好情形下快速排序空间复杂度大约为O(㏒n)。
空间复杂度：
很明显，其空间复杂度为O(㏒n)。
算法优化
上面这个快速排序算法可以说是最基本的快速排序，因为它并没有考虑任何输入数据。但是，我们很容易发现这个算法的缺陷：这就是在我们输入数据基本有序甚至完全有序的时候，这算法退化为冒泡排序，不再是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)级别。
算法稳定性
快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。
算法适用场景
快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。
快排的非递归实现
按照通常的理论，我们知道递归算法一般比较直观自然，容易理解和书写；而非递归算法一般更为晦涩，但是性能比递归算法更优良，因为其省去了大量的函数调用开销。快速排序肯定有非递归实现的版本，例如这篇博客。有趣的是，这位作者认为快速排序的非递归实现比递归还要慢，并做出了分析。
快速排序的Java非递归实现当然有，通常都是用自己实现的栈来模拟递归操作（实际上，前面两位使用C++的同学也是如此做的）。但是我并不认为它们比递归的方式有极大的性能提升，反而丢失了可读性，晦涩难懂。因此，我个人不提倡使用非递归方式。
