快速排序（Quick Sort）
- 基本思想
- 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
- 快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
- 算法步骤
- 先从数列中取出一个数作为key值。
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边。
- 对左右两个小数列重复第二步，直至各区间只有1个数。
-
动图演示
quickSort.gif 代码实现
三个小方法，使用递归实现该算法
public static void quickSort(int[] arr) {
if (null == arr || arr.length < 1) return;
quickSort(arr, 0, arr.length - 1);
}
/**
* 快速排序 主方法 - 递归实现
* @param arr 主数组
* @param left 排序起始索引
* @param right 排序终止索引
*/
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
/**
* 选取一个基准点，使小于该值置于左边，大于该值置于右边
* @param arr 排序数组
* @param left 左索引
* @param right 右索引
* @return 返回调整后该基准点位置
*/
public static int partition(int[] arr, int left, int right) {
// 选取第一个数为基准点
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
- 时间复杂度分析
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
优化
- 基准值（pivot）的选取可以有多种形式，例如中间数或者随机数，分别会对算法的复杂度产生不同的影响。
