快速排序 Quick Sort
快速排序
1. 基本原理
快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序,它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地求解这些子问题,然后将这些子问题的解组合为原问题的解。
2. 算法步骤
- 从序列中挑出一个元素,作为"基准"(pivot)
- 把所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准值的后面(相同的数可以放到任一边),这个操作称为分区(partition)操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序,直到所有子序列的大小为0或1,这时整体已经排好序了
3. 算法图解
传送门 坐在马桶上看算法:快速排序
4. 动画演示
5. 参考实现
import java.util.Arrays;
import java.util.LinkedList;
/**
* @author wylu
*/
public class QuickSort {
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int partition(int[] arr, int left, int right) {
int i = left, j = right, pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
while (i < j && arr[i] <= pivot) i++;
if (i < j) swap(arr, i, j);
}
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
public static void recursiveSort(int[] arr, int left, int right) {
if (left < right) {
int idx = partition(arr, left, right);
recursiveSort(arr, left, idx - 1);
recursiveSort(arr, idx + 1, right);
}
}
public static void nonRecursiveSort(int[] arr, int left, int right) {
LinkedList<Integer> stack = new LinkedList<>();
stack.push(left);
stack.push(right);
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
if (left < right) {
int idx = partition(arr, left, right);
stack.push(left);
stack.push(idx - 1);
stack.push(idx + 1);
stack.push(right);
}
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 9, 6, 0, 7, 2, 5, 8};
// QuickSort.recursiveSort(arr, 0, arr.length - 1);
QuickSort.nonRecursiveSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
partition的另一种写法,选取最右元素作为基准
public static int partition2(int[] arr, int left, int right) {
int j = left - 1;
for (int i = left; i < right; i++) {
if (arr[i] <= arr[right]) swap(arr, i, ++j);
}
swap(arr, ++j, right);
return j;
}
6. 复杂度分析
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
快速排序 | In-place | 不稳定 |