快速排序算法
介绍
快速排序（Quick Sort）是一种高效的分治排序算法，由英国计算机科学家 Tony Hoare 于 1960 年提出。它是实际应用中最常用的排序算法之一。快速排序的基本思想是：选择一个"基准"（pivot）元素，通过一次排序将待排序列分割成独立的两部分，一部分所有元素均小于基准，另一部分所有元素均大于基准，然后递归地对这两部分分别进行快速排序。分治策略的运用让快速排序在平均情况下能达到 O(nlogn) 的时间复杂度，大大优于简单排序算法的 O(n²) 性能。
算法步骤
- 从数列中选择一个元素作为"基准"（pivot），本文采用最左侧元素作为基准
- 将所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（分区操作）
- 对基准左右两个子序列分别重复步骤1和2，直到子序列只有一个元素或为空
核心特性
- 分治策略：将问题分解为更小的子问题，逐步解决
- 原地排序：只需要 O(logn) 的额外空间复杂度（主要用于递归调用的栈空间）
- 时间复杂度：平均情况为 O(nlogn)，最坏情况为 O(n²)，最好情况为 O(nlogn)
- 不稳定性：相等元素的相对位置在排序后可能会改变
- 高效性：在实际应用中，快速排序通常是最快的排序算法之一
基础实现
接下来大家一起看下快速排序的部分主流语言实现：
代码实现
Java实现
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low + 1;
for (int j = low + 1; j <= high; j++) {
if (arr[j] < pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[low];
arr[low] = arr[i - 1];
arr[i - 1] = temp;
return i - 1;
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("排序前的数组：");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组：");
printArray(arr);
}
}注意，在上述代码里，通过：
for (int j = low + 1; j <= high; j++) {
if (arr[j] < pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}将小于基准的元素移到左侧，然后通过：
int temp = arr[low];
arr[low] = arr[i - 1];
arr[i - 1] = temp;修正基准的位置，实现基准左侧都小于基准、基准右侧大于等于基准。
优化策略
随机选择基准元素
使用最左侧元素作为基准可能会在数组已经排序或接近排序时导致最坏性能，随机选择基准可以降低这种风险：
private static int randomPartition(int[] arr, int low, int high) {
int randomIndex = low + (int)(Math.random() * (high - low + 1));
int temp = arr[randomIndex];
arr[randomIndex] = arr[low];
arr[low] = temp;
return partition(arr, low, high);
}三数取中法
选择左端、中间和右端三个元素的中值作为基准，可以进一步优化快速排序：
private static int medianOfThreePartition(int[] arr, int low, int high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[low])
swap(arr, mid, low);
if (arr[high] < arr[low])
swap(arr, high, low);
if (arr[high] < arr[mid])
swap(arr, high, mid);
swap(arr, mid, low);
return partition(arr, low, high);
}优缺点
优点
- 平均情况下非常高效，时间复杂度为 O(nlogn)
- 原地排序，空间复杂度低
- 缓存友好，数据局部性好
- 适合处理大规模数据
- 在许多实际应用中表现优秀
缺点
- 最坏情况下性能退化至 O(n²)，比如当数组已经排序时
- 不稳定的排序算法
- 对于小数组，快速排序可能比其他基础排序慢
- 递归实现可能导致栈溢出（可以使用迭代方式解决）
应用场景
- 需要高效排序大量数据的情况
- 作为系统库中的排序函数（如 C++ 的 std::sort、Java 的 Arrays.sort）
- 需要就地排序且对空间复杂度敏感的场景
- 需要平均情况下高性能的应用
扩展
双轴快速排序
Java 的 Arrays.sort() 使用的是双轴快速排序，它使用两个枢轴(基准)，可以进一步提高性能：
public static void dualPivotQuickSort(int[] arr, int low, int high) {
if (high <= low) return;
if (arr[low] > arr[high]) {
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int pivot1 = arr[low];
int pivot2 = arr[high];
int lt = low + 1;
int gt = high - 1;
int i = low + 1;
while (i <= gt) {
if (arr[i] < pivot1) {
int temp = arr[lt];
arr[lt] = arr[i];
arr[i] = temp;
lt++;
i++;
}
else if (arr[i] > pivot2) {
int temp = arr[i];
arr[i] = arr[gt];
arr[gt] = temp;
gt--;
}
else {
i++;
}
}
arr[low] = arr[lt - 1];
arr[lt - 1] = pivot1;
arr[high] = arr[gt + 1];
arr[gt + 1] = pivot2;
dualPivotQuickSort(arr, low, lt - 2);
dualPivotQuickSort(arr, lt, gt);
dualPivotQuickSort(arr, gt + 2, high);
}测验
这里准备了一些测试题，方便大家判断自己的掌握情况：
- 快速排序的平均时间复杂度是多少？
- 快速排序是稳定的排序算法吗？
- 使用最左侧元素作为基准的快速排序在什么情况下会出现最坏性能？
- 快速排序的空间复杂度是多少？为什么？
测验答案
- O(nlogn)。
- 不是，因为基准元素的移动可能会改变相等元素的相对位置。
- 当数组已经排序或接近排序时，每次分区只能减少一个元素，时间复杂度退化为O(n²)。
- O(logn)，主要是递归调用占用的栈空间，最坏情况下为O(n)。
相关的 LeetCode 热门题目
给大家推荐一些可以用来练手的 LeetCode 题目：
- 215. 数组中的第K个最大元素 - 可以使用快速选择算法（快速排序的变体）求解，练习分区思想
- 912. 排序数组
- 75. 颜色分类 - 一个经典的荷兰国旗问题，可以使用类似快速排序的分区思想解决
来自: 快速排序 - 算法导航