一、算法简介
在排序算法中，冒泡排序和选择排序因为简单被大多数人所熟知,然而在实际的排序需求中，快速排序算法才是最好的选择。选择快速排序算法的原因，是因为它有如下的优点
- 它的平均性能非常好，平均时间复杂度为nlgn，并且常数因子n非常小。
- 能够进行原址排序，甚至在虚存环境中也能很好的工作
注：原址排序来源于《算法导论》，意思是在原数组上操作就可以完成排序，不需要临时数组。
二、算法思想
与归并排序算法一样,快速排序算法也使用了分治的思想，乍一看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。
快速排序的大多数情况下复杂度是O(nlogn)，但最坏情况下可能就会变成O(n^2)，最坏情况就是每次将一组数据划分为两组的时候，分界线都选在了边界上，使得划分了和没划分一样，最后就变成了普通的选择排序了。
而所有分治的都需要如下的步骤
划分，解决，合并
三、算法步骤
分解 是将输入数组A[p..r]划分成两个(可能为空)的子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。其中，计算下标q也是划分过程的一部分。
解决 是通过递归调用快速排序方法，对子数组A[p..q-1]和A[q+1..r]进行排序。
合并 是递归到最深层，已经不能再划分成更小的子序列了。而最小的子序列 是两个元素的数组，他们已然是有序，并且数组排序时是原址排序，所以整体也就是有序，合并这个操作就不需要了
// 这里递归调用快速排序方法，不断减小问题规模
public static void QuickSort(int[] a, int left, int right) {
if (left < right) { // 这里的判定要求数组中至少有两个元素
int p = partition(a, left, right);
QuickSort(a, left, p - 1);
QuickSort(a, p + 1, right);
}
}
// 这里划分子数组,并且返回划分位置
private static int partition(int[] a, int left, int right) {
int x = a[right];
int p = left - 1;
for (int i = left; i < right; i++) {
if (a[i] <= x) {
p++;
swap(a, p, i);
}
}
swap(a, p+1, right);
return p+1;
}
// 交换方法
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
QuickSort(int[] a,int left,int right)这个函数就是根据返回值，设置递归边界，然后递归处理左序列，在处理右序列
接下来讲解partition(int[] a, int left, int right)
int x = a[right];
这行代码的作用是选中最右边为标志位，然后根据这个标志位将数组划分为他的左边比他小，他的右边比他大。
int p = left - 1;
这行是初始化比标志位小的第一个位置，可以看到后面实际交换时都有+1操作，所以他的初始位置就是最左边
for (int i = left; i < right; i++) {
if (a[i] <= x) {
p++;
swap(a, p, i);
}
}
这几行就是，从左到右不断的循环，发现a[i]<=标志位则交换p和i的位置，并且p移动到下一位
swap(a, p+1, right);
遍历完以后，直接交换p的下一位为标志位。这样，p的左边都小于等于p，右边大于p
注: 这里的p是p位置的值
return p+1;
最后返回标志位的位置，继续递归调用直到划分的数组小于2时到达终态，整个数组就有序了。
具体流程，如图所示
算法执行图
四、快速排序算法的优化
上面实现的快速排序算法，标志位每次都选择数组的最右边的元素。当序列为有序时，会发现划分出来的两个子序列中，有一个里面没有元素，而另一个则只比原来少一个元素。为了避免这种情况，引入一个随机化量来破坏这种有序状态。
五、算法性能评测
参考
算法导论第三版
网友评论