正文之前
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼 * 霍尔提出。在平均状况下，排序n个项目要O(nlogn)次比较，在最坏情况下则需要O(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 ——Wikipedia
本文将介绍以下内容
排序原理
算法实现（JAVA）
测试阶段
算法分析
正文
排序原理
和归并排序划清界限：
归并排序：将一个数组分成两个字数组，分别排序两部分，将有序的子数组归并得到整个有序数组
快速排序：将一个数组分成两个字数组，分别排序两部分，当两个子数组有序时，整个数组自然就有序了
快速排序使用一个切分元素来划分数组，切分元素左边的数组元素小于切分元素，右边的数组元素大于于切分元素，所以两个子数组有序就会得到整个有序的数组
算法实现
1. 切分数组
private static int partition(int[] a, int low, int high){
int i = low, j = high + 1; //由两边向中间扫描
int p = a[low]; //切分数组的元素
while(true){
while(a[++i] < p){ // i 的值会一直递增至 a[++i] >= p
if(i == high){ //扫描结束
break;
}
}
while(a[--j] > p){ // j 的值会一直递减至 a[++i] >= p
if(j == low){ //扫描结束
break;
}
}
if(i >= j){ // j 的位置就是切分元素在有序数组中的位置
break;
}
int temp = a[i]; //交换元素顺序
a[i] = a[j];
a[j] = temp;
}
int temp = a[low]; //将切分元素交换至中间位置
a[low] = a[j];
a[j] = temp;
return j;
}
2. 数组排序
这一部分的代码和归并排序的排序代码相似
private static void quickSort(int[] a){
sort(a, 0, a.length - 1);
}
private static 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);
}
sort方法递归调用自己，将数组划分至最小，每次都将子序列中的第一个元素作为切分元素，来将数组排序
整个排序过程的代码：
public class QuickSort {
private static int partition(int[] a, int low, int high){
int i = low, j = high + 1; //由两边向中间扫描
int p = a[low]; //切分数组的元素
while(true){
while(a[++i] < p){ // i 的值会一直递增至 a[++i] >= p
if(i == high){ //扫描结束
break;
}
}
while(a[--j] > p){ // j 的值会一直递减至 a[++i] >= p
if(j == low){ //扫描结束
break;
}
}
if(i >= j){ // j 的位置就是切分元素在有序数组中的位置
break;
}
int temp = a[i]; //交换元素顺序
a[i] = a[j];
a[j] = temp;
}
int temp = a[low]; //将切分元素交换至中间位置
a[low] = a[j];
a[j] = temp;
return j;
}
private static void quickSort(int[] a){
sort(a, 0, a.length - 1);
}
private static 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);
}
}
测试阶段
public static void main(String[] args){
int[] a = new int[10];
for (int i = 0; i < 10; i++) {
a[i] = (int)(Math.random() * 100);
System.out.print(a[i] + " ");
}
quickSort(a);
System.out.println();
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
生成10个随机数字并调用快速排序方法，最后输出结果：
算法分析
1. 特点
快速排序实现简单，应用广泛，比一般算法要快很多，并且是原地排序（借助辅助栈）
2. 时间复杂度
设数组的长度为N，用 T(N) 表示排序一个长度为N的数组所需要的比较次数，可想而知，T(0) 和 T(1) 为0
切分的成本为N + 1，左子数组排序的平均成本为(C1 + C2 + ... + CN - 2 + CN - 1)/N，右子数组排序的平均成本为(CN - 1 + CN - 2 + ... + C2 + CN)/N
CN = N + 1 + (C1 + C2 + ... + CN - 2 + CN - 1)/N + (CN - 1 + CN - 2 + ... + C2 + CN)/N
经过化简之后得到：CN ~ 2(N + 1)(1/3 + 1/4 + ... + 1/(N + 1))
积分得到CN ~ 2NlogN
所以，算法复杂度为 O(nlogn)
3. 稳定性
举个例子，一个数组a = [6,4,3,2,3,7,8,7,9]，a[0]和a[4]交换，第二个 3 就移动到了第一个 3 的前面，所以是不稳定的，不稳定性体现在切分元素交换的时候
关于快速排序的介绍就到这里了，谢谢！
