本文是 Java排序算法面试手写精讲 的分章阅读版。
分治:选一个基准值(pivot),将数组分为小于pivot和大于pivot两部分,递归排序。
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
// 三数取中法选pivot(避免最坏情况)
int mid = left + (right - left) / 2;
if (arr[left] > arr[mid]) swap(arr, left, mid);
if (arr[left] > arr[right]) swap(arr, left, right);
if (arr[mid] > arr[right]) swap(arr, mid, right);
swap(arr, mid, right - 1); // pivot放到right-1位置
int pivot = arr[right - 1];
int i = left, j = right - 1;
while (true) {
while (arr[++i] < pivot); // 从左找>=pivot的
while (arr[--j] > pivot); // 从右找<=pivot的
if (i >= j) break;
swap(arr, i, j);
}
swap(arr, i, right - 1); // pivot归位
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
public static void quickSort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int pivot = arr[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (arr[j] < pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, hi);
quickSort(arr, lo, i - 1);
quickSort(arr, i + 1, hi);
}
import java.util.Random;
public class QuickSort3Way {
private static final Random RNG = new Random();
public static void sort(int[] arr) {
shuffle(arr); // 随机打乱,消除输入依赖
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
// --- 小数组切换插入排序(优化递归开销)---
if (hi - lo + 1 < 16) {
insertSort(arr, lo, hi);
return;
}
// --- 三路分区:Dijkstra荷兰国旗 ---
int pivot = arr[lo];
int lt = lo; // [lo..lt-1] < pivot
int gt = hi; // [gt+1..hi] > pivot
int i = lo + 1; // [lt..i-1] == pivot
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr, lt++, i++);
} else if (arr[i] > pivot) {
swap(arr, i, gt--);
} else {
i++;
}
}
// 现在:arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
sort(arr, lo, lt - 1);
sort(arr, gt + 1, hi);
}
// --- 辅助方法 ---
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
private static void shuffle(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
int j = RNG.nextInt(i + 1);
swap(arr, i, j);
}
}
private static void insertSort(int[] arr, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
int key = arr[i];
int j = i - 1;
while (j >= lo && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}
三路分区的关键: 大量重复元素时,等于pivot的区间被整体跳过,不再递归。极端情况(全部相同元素)一次partition就结束,复杂度退化为O(n)。
面试话术: "快排平均O(nlogn),最坏O(n^2)(已排序数组)。三数取中法选pivot可避免最坏情况,三路分区可解决大量重复元素退化。不稳定(交换可能改变相等元素的相对顺序)。Java的Arrays.sort()对基本类型用双轴快排(DualPivotQuicksort)。"