当前位置：首页 > news >正文

高级排序算法（一）：快速排序详解

news 2025/7/18 14:30:00

引言

当我们处理大规模数据时，像冒泡排序、选择排序这样的基础排序算法就有点力不从心了。这时候，快速排序（Quick Sort）就派上用场了。
作为一种基于分治法的高效排序算法，快速排序在大多数情况下可以在O(n log n)的时间内完成排序。它不仅理论上效率高，而且在实际应用中表现也非常优异，是排序算法中的经典之作。

这篇文章将带你深入理解快速排序的原理、实现细节以及优化策略。

一、快速排序的核心思想

快速排序的核心是分治法（Divide and Conquer），它将问题分为更小的子问题逐一解决。快速排序的主要步骤如下：

选择一个基准值（Pivot）：通常选取数组中的一个元素作为基准。
分区：
- 将小于基准值的元素放到左侧。
- 将大于基准值的元素放到右侧。
递归排序：
- 对左右两个部分分别递归地应用快速排序。

二、快速排序的分区方法

分区是快速排序的核心操作，它直接决定了算法的性能。常见的分区方法有两种：

1. Lomuto分区法

选取数组的最后一个元素作为基准值。
使用一个指针i将数组分为两部分：
- 左侧：小于基准值的元素。
- 右侧：大于基准值的元素。
最后将基准值放到正确的位置。


int lomutoPartition(int arr[], int low, int high) {int pivot = arr[high];  // 基准值int i = low - 1;        // 指针 i 初始化在 low 的前面for (int j = low; j < high; j++) {if (arr[j] < pivot) {  // 如果当前元素小于基准值i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;  // 交换 i 和 j 的元素}}// 将基准值放到正确的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;  // 返回基准值的索引
}

2. Hoare分区法

使用两个指针：
- 左指针i从左向右移动，找到第一个大于基准值的元素。
- 右指针j从右向左移动，找到第一个小于基准值的元素。
交换i和j的元素，直到两个指针相遇。
与Lomuto相比，Hoare分区法交换次数更少，适合大规模数据。


int hoarePartition(int arr[], int low, int high) {int pivot = arr[low];  // 基准值int i = low - 1;int j = high + 1;while (1) {do {i++;} while (arr[i] < pivot);  // 从左向右找到大于等于 pivot 的元素do {j--;} while (arr[j] > pivot);  // 从右向左找到小于等于 pivot 的元素if (i >= j) return j;  // 指针相遇，返回分区点int temp = arr[i];arr[i] = arr[j];arr[j] = temp;  // 交换 i 和 j 的元素}
}

三、快速排序的完整实现

以下是快速排序的完整实现，使用Lomuto分区法。


#include <stdio.h>// Lomuto 分区法
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}// 快速排序
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);  // 分区点quickSort(arr, low, pi - 1);         // 排序左部分quickSort(arr, pi + 1, high);        // 排序右部分}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("排序后的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

四、快速排序的时间复杂度

快速排序的时间复杂度取决于分区点的选择：

最优情况：每次分区将数组均分为两部分，时间复杂度为 O(n log n)。
最坏情况：每次分区只分出一个元素，时间复杂度为 O(n²)。
平均情况：分区较为均衡，时间复杂度为 O(n log n)。

优化策略：

随机化基准值：随机选择基准值，避免最坏情况。
切换到插入排序：当子数组长度小于一定阈值时，使用插入排序提高效率。

五、快速排序与归并排序的对比

特性	快速排序	归并排序
时间复杂度	平均 O(n log n)，最坏 O(n²)	始终 O(n log n)
空间复杂度	原地排序，O(log n)	O(n)
稳定性	不稳定	稳定
适用场景	数据量大且内存有限	数据量大且对稳定性有要求