简单实现
快速排序是比较经典、常用的算法，下面简要介绍其思路。对于一个数组，选取某个元素作为切分元素（比如第一个元素），然后把比这个元素小的都放到它前面，比这个元素大的都放到它后面，这样切分元素的最终位置就确定了，并且数组被划分为两个子数组。然后再用同样的方法分别对子数组进行排序，最终整个数组将变成有序的。
这里的关键是实现数组划分的方法，这里举例说明。假如要对数组a={5,3,6,5,8,4,7}排序，选取a[0] 作为切分元素，排序过程如下：
5,3,6,5,8,4,7
i j
5,3,6,5,8,4,7
i j
5,3,4,5,8,6,7
ij
如上所示，刚开始i指向数组第一个元素，而j指向数组末尾元素后一个位置，i从前往后扫描，直到找到一个大于等于切分元素时停下（这里是6），j从后往前扫描，直到找到一个小于等于切分元素的时候停下（这里是4），然后交换这两个元素。然后继续寻找直到两个指针相遇，则本轮扫描结束。此时j<=i，j右边的元素均大于切分元素，交换a[j]与切分元素即可。接着对两个子数组{5,3,4}以及{8,6,7}继续用刚才的方法排序，最终数组将全部有序。代码实现如下：
void sort(int[] a, int lo, int hi) {
if (hi <= lo)
return;
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
int partition(int[] a, int lo, int hi) {
int i = lo, j = hi + 1;
int v = a[lo];
while (true) {
while (a[++i] < v)
if (i == hi)
break;
while (a[--j] > v)
if (j == lo)
break;
if (i >= j)
break;
swap(a, i, j); //交换元素
}
swap(a, lo, j);
return j;
}对于快速排序有几点说明：
- 快速排序是原地排序（只需要一个辅助栈）
- 一般情况下快速排序的时间复杂度是
O(NlgN)，因为平均而言划分的子数组是对半分的。但如果切分不均匀，那么时间可能会变成平方级别。例如对于一个已经有序的数组，快速排序的性能反而很差。 - 在每次扫描时，左侧扫描遇到大于等于切分元素时停下，右侧扫描则是遇到小于等于切分元素时停下。这样会将一些等值元素交换，但可以避免在数组中含有大量重复值的时候运行时间变成平方级别。
优化
对于快速排序有3点优化思路：
- 对于小数组，可以采用插入排序，避免递归调用。例如，当
if(hi <= lo + M)时，就可以转到插入排序。 - 采用子数组的一部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。
-
如果数组中含有大量的重复元素，可以采用三向切分。将数组切分为三部分，分别对应于小于、等于和大于切分元素的数组元素。代码实现如下：
private static void sort1(int[] a, int lo, int hi) { if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a[lo]; while (i <= gt) { if (a[i] < v) { swap(a, lt++, i++); } else if (a[i] > v) { swap(a, i, gt--); } else { i++; } sort(a, lo, lt - 1); sort(a, gt + 1, hi); }}
另一种实现：单向扫描
快速排序的数组切分还有另一种单向扫描的版本，具体步骤是选择数组中最后一个元素作为切分元素，同样设置两个指针，指针i指向数组中第一个元素前面一个位置，j则指向数组中第一个元素。j从前左右往右扫描，遇到小于等于切分元素时就把i加一，然后交换i和j指向的元素。最后把i+1位置的元素和切分元素交换即可完成一次数组划分。代码实现如下：
int partition(int[] a, int lo, int hi) {
int i = lo - 1, j = lo;
int v = a[hi];
while (j < hi) {
if (a[j] <= v) {
swap(a, ++i, j);
}
j++;
}
swap(a, i + 1, hi);
return i + 1;
}
