思路
像合并排序一样，快速排序是基于分支模式的：
分解：数组A[n]被划分两个字数组A[0..q-1]和A[q+1..n],使得对于数组A[0..q-1]中的元素都小于A[q], A[q+1..n]中的元素都大于等于A[q]。此时A[q]就得排好序。
解决：通过递归调用快速排序，对字数组A[0..q-1]和A[q+1..n]进行排序
合并：因为两个字数组已经是就地排好序的了，整个数组已经排好序了。
参考代码
按照以上模式可以写出程序：
<a></a>
关键是找出划分元素的位置函数getPartition，程序如下：其中一次运行过程，如下：
图示
最后，数组的最后一个元素找到了自己最终的位置上，把左右分成了两个相对独立的数组。
通过图示可以看出规律：
测试
性能
时间复杂度：就平均性能而言，快速排序是目前被认为是最好的一种内部排序方法。通常认为快速排序在平均情况下的时间复杂度为O(nlogn)。若初始记录序列按关键字有序或基本有序，快速排序将蜕化为冒泡排序，其时间复杂度为O(n2)。
空间复杂度：最坏情况下，若每趟排序之后，枢轴位置均偏向子序列的一端（有序），栈的最大深度为n。如果在一趟划分之后比较分割所得两部分的长度，且先对长度短的子序列中的记录进行快速排序，则栈的最大深度可降为O(logn)。
性能改善：在区间选取随机数，把该数放在应在的位置，可以有效避免最坏情况。如下
稳定性
不稳定
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923771.html，如需转载请自行联系原作者