前言
最近不太忙，有空oj上刷刷水题，遇到几道排序题目，鄙人习惯用java语言，也深知很多直接用java封装好的sort函数能够直接解决问题。但所谓饮水思源，项目之外，还是应该多多关注众多排序算法的内部细节。就先总结平均效率最高的快速排序算法吧。
特点
平均效率最高，但不稳定。平均时间复杂度o(nlogn),最坏时间复杂度o(n^2)。
思路（升序）
快速排序基于比较和分治，核心是先让一个元素找准其位置，使其左边的元素都不比它大，右边的元素都不比它小。然后再使其左边集合和右边集合都递归下去，直到最终有序。
方法
- 选取一个基准（参照物），默认选择第一个元素（当然选择其他元素也可以）。并确定两个游标，左游标和右游标。
- 右游标从右到左扫描，若发现一个小于基准的元素，停止扫描，将该元素赋值到基准位置，同时新的基准位置调整到该元素原来位置。倘若没发现，则当左右游标重合时停止扫描。
- 左游标从左向右扫描，若发现一个大于基准的元素，停止扫描，将该元素赋值到基准位置，同时新的基准位置调整到该元素原来位置。倘若没发现，则当左右游标重合时停止扫描。
- 2和3一直进行，直到左右游标重合，即基准已找到其位置，将基准值赋值到游标重合位置。
- 虽然已经确定了基准的位置，但总体来看并不一定是有序的，则还需要对其左边集合和右边集合分别进行排序，使用递归即可。
例子
代码实现
public static void quickSort(int a[],int l, int r) {
if(l < r) {
int s = a[l]; //基准
int i = l; //左游标
int j = r; //右游标
while(i < j) {
//从右向左扫描，当左右游标重合或者扫描到小于基准的值时扫描停止
while(i < j && a[j] > s) {
j--;
}
//将小于基准的值赋值到基准位，右游标位置为新的基准位
a[i] = a[j];
//从左向右扫描，当左右游标重合或者扫描到大于基准的值时扫描停止
while(i < j && a[i] < s) {
i++;
}
//将大于基准的值赋值到基准位，左游标位置为新的基准位
a[j] = a[i];
}
//左右游标重合，基准值的最终位确定
a[j] = s;
//对左边部分递归
quickSort(a,l,i-1);
//对右边部分递归
quickSort(a,j+1,r);
}
}
这是升序的实现，如要排成降序，可在扫描时改变判断方向，即从右到左找大于基准的，从左到右找小于基准的。很容易实现，这里就不多说了。
结语
根据快速排序的算法可以知道，快速排序并非在任何情况都是最优的，比如说当集合是有序的时候，基准选到了最大或者最小的元素，这样每次只能定一个元素的位置，就等于冒泡排序了，时间复杂度变成了o(n^2)。不过绝大数情形，快速排序是优于其他排序的。
