快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种[排序算法]，最早由[东尼 · 霍尔]提出。在平均状况下，排序n个项目要[Ο](n log n) 次比较。在最坏状况下则需要Ο(n^2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为 "基准"（pivot），
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
public class QuickSort {
public static void sort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
/**
* 递归划分子序列
*
* @param arr
* @param left
* @param right
*/
public static void quickSort(int[] arr, int left, int right) {
System.out.println("quickSort：" + print(arr));
if (left >= right) {
return;
}
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos - 1);
quickSort(arr, pivotPos + 1, right);
}
/**
* 稍优的划分逻辑
* 一次划分流程
*
* 按照把左边第一个数字作为基准数的话，逻辑如下：
* 1. 右指针从右往左找到比基准数小的数字，找到时指针停止移动，且给左指针数字赋值为右指针对应的数字
* 2. 左指针从左往右找到比基准数大的数字，找到时指针停止移动，且给右指针数字赋值为左指针对应的数字
* 3. 交换相遇时的数字和基准数
* 4. 此时基准数左边都是比基准数小的数字，基准数右边都是比基准数大的数字
* 5. 此时一轮划分执行完毕
*
* @param arr
* @param left 左指针
* @param right 右指针
* @return
*/
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivotKey) {
right--;
}
arr[left] = arr[right]; //把小的数字移动到左边
System.out.println(print(arr));
while (left < right && arr[left] <= pivotKey) {
left++;
}
arr[right] = arr[left]; //把大的移动到右边
System.out.println(print(arr));
}
arr[left] = pivotKey; //最后把pivot赋值到中间
System.out.println(print(arr));
return left;
}
/**
* 代码中基准数已经在 pivotKey 中保存了，所以不需要每次交换都设置一个 temp 变量，
* 在交换左右指针的时候只需要先后覆盖就可以了。
* 这样既能减少空间的使用还能降低赋值运算的次数
*
* 一次划分流程
*
* 按照把左边第一个数字作为基准数的话，逻辑如下：
* 1. 右指针从右往左找到比基准数小的数字，找到时指针停止移动
* 2. 左指针从左往右找到比基准数大的数字，找到时指针停止移动
* 3. 交换这两个数字
* 4. 重复步骤1和步骤2，如果两者相遇时，则停止移动
* 5. 交换相遇时的数字和基准数
* 6. 此时基准数左边都是比基准数小的数字，基准数右边都是比基准数大的数字
* 7. 此时一轮划分执行完毕
*
* @param arr
* @param left 左指针
* @param right 右指针
* @return
*/
public static int partitionOld(int[] arr, int left, int right) {
int pivotKey = arr[left];
int initLeft = left;
while (left < right) {
while (left < right && arr[right] >= pivotKey) {
right--;
}
while (left < right && arr[left] <= pivotKey) {
left++;
}
swap(arr, left, right);
System.out.println(print(arr));
}
swap(arr, initLeft, left);
System.out.println(print(arr));
return left;
}
public static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
