快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
public static void main(String[] args) {
// int[] p = { 34, 34, 54, 21, 54, 18, 23, 76, 38, 98, 45, 33, 27, 51,
// 11, 20, 79, 30, 89, 41 };
int[] p = { 34, 11, 10, 79, 41, 51, 23 };
printerInfo(p, 0, p.length - 1);
System.out.println("------------------------");
long start = System.currentTimeMillis();
Sort.qsort(p, 0, p.length - 1);// 快速排序
System.out.println("所用时间：" + (System.currentTimeMillis() - start));
printerInfo(p, 0, p.length - 1);
}
private static void printerInfo(int[] arr, int low, int high) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("[" + low + "," + high + "]");
}
private static void qsort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high); // 将数组分为两部分
qsort(arr, low, pivot - 1); // 递归排序左子数组
qsort(arr, pivot + 1, high); // 递归排序右子数组
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low]; // 枢轴记录
while (low < high) {
while (low < high && arr[high] >= pivot)
--high;
arr[low] = arr[high]; // 交换比枢轴小的记录到左端
while (low < high && arr[low] <= pivot)
++low;
arr[high] = arr[low]; // 交换比枢轴大的记录到右端
printerInfo(arr, low, high);
}
// 扫描完成，扫描的长度为一开始的(high-low),但是此时low=high，枢轴到位
arr[low] = pivot;
// printerInfo(arr, low, high);
// 返回的是枢轴的位置
return low;
}
算法性能/复杂度
可以看出，每一次调用partition()方法都需要扫描一遍数组长度（注意，在递归的时候这个长度并不是原数组的长度n，而是被分隔出来的小数组，即n*(2(-i))），其中i为调用深度。而在这一层同样长度的数组有2i个。那么，每层排序大约需要O(n)复杂度。而一个长度为n的数组，调用深度最多为log(n)层。二者相乘，得到快速排序的平均复杂度为O(n ㏒n)。
通常，快速排序被认为是在所有同数量级的排序方法中，平均性能最好。
从代码中可以很容易地看出，快速排序单个栈的空间复杂度不高，每次调用partition方法时，其额外开销只有O(1)。所以，最好情形下快速排序空间复杂度大约为O(㏒n)。
