一，快速排序介绍
快速排序与归并排序一样，也是基于分治的递归算法，体现在：在每一趟快速排序中，需要选出枢轴元素，然后将比枢轴元素大的数组元素放在枢轴元素的右边，比枢轴元素小的数组元素都放在枢轴元素的左边。然后，再对分别对 枢轴元素左边 和 枢轴元素右边的元素进行快速排序。
二，快速排序算法分析
①相比于直接插入排序，快排合适于数据量大（上百万）的情形，而插入排序适合于小数据量的情形。因为，在数据量小的情形下，快排的递归是需要一定的开销的。
②相比于归并排序，归并排序的比较次数要比快速排序少，但是它需要一个额外的临时数组，而且移动的元素多。而快速排序不需要显示地声明一个临时数组，它用的是递归栈。在C++四使用它来作为标准的排序程序，而Java中则是用归并排序来作为标准的排序。
③快速排序主要有两个基本操作：一是选取枢轴元素，另一个则是递归分割数组。枢轴元素的选取对快速排序的效率至关重要，因为它决定了递归的深度。如果枢轴元素刚好处于数组的中间值，那么，数组在分割时就分成了平均的两部分。这样的递归的效率就好。如果每次选取的枢轴元素都是最大/最小 的那个元素，则快排复杂度达到了O(N^2)，而且还用了递归栈空间。
④枢轴元素的选取可以采用三数取中法。所谓三数取中法，即给定一个数组，选取数组中的第一个元素，最后一个元素，和中间那个元素。哪个元素的值位于中间，则它作为枢轴元素。比如，a[0]=5 , a[4]=1, a[9]=10, 那么 a[4]<a[0]<a[9] ，故a[0]是枢轴元素。
采用三数取中法时，会有一个问题，就是当数组不断的递归划分变小之后，枢轴左边的元素个数不足3，这样三数取中法就失去了应有的意义。此外，正如前面提到，对于小数组而言，插入排序反而比快速排序的效率更高。
正是基于以上两个原因，我们可以将快速排序与插入排序结合。当递归划分的数组变小之后，达到某个值（CUTOFF）时，采用插入排序。（代码83行）
三，快速排序算法实现
public class QuickSort {
private static final int CUTOFF = 10;
/**
*
* @param arr
* 待排序的数组
*/
public static <T extends Comparable<? super T>> void quickSort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* 快排的基本操作:通过三数取中法来选取枢轴元素
*
* @param arr
* 在[left, right]之间选择pivot element
* @param left
* index of arr to chose pivot element
* @param right
* index of arr to chose pivot element
* @return pivot element
*/
private static <T extends Comparable<? super T>> T media3(T[] arr,
int left, int right) {
int center = (left + right) / 2;
if (arr[center].compareTo(arr[left]) < 0)
swapReference(arr, center, left);
if (arr[right].compareTo(arr[left]) < 0)
swapReference(arr, right, left);
// 参考前面两个if比较之后,最小的元素被放置在
// arr[left],然后下面再比较中间与最右的元素,将最大的元素放在arr[right],而arr[center]存放中间元素(pivot)
if (arr[right].compareTo(arr[center]) < 0)
swapReference(arr, right, center);
swapReference(arr, center, right - 1);//将枢轴元素放在 arr[right-1]上.便于快排交换元素
return arr[right - 1];
}
private static <T extends Comparable<? super T>> void swapReference(
T[] arr, int from, int to) {
T tmp = arr[from];
arr[from] = arr[to];
arr[to] = tmp;
}