快速排序是一种非常高效的排序算法,其核心思想是 “分治法” (Divide and Conquer)。
快速排序的核心思想
- 选择基准：从待排序的数组中选择一个元素，称为 “基准”（Pivot）。
- 分区：重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆放在基准后面，在这个分区结束之后，基准就处于数组的中间位置，这个操作称为 分区 操作。
- 递归排序：递归地对基准左边和右边的子数组进行快速排序。
就是每次排序都能把一个元素放到它最终应该在的位置上,然后把剩下的数组分成两半，继续这个过程。
C 语言实现
我们将实现两个核心函数：
partition(): 分区函数，负责将数组分成两部分。quickSort(): 递归排序函数。
1 分区函数
分区是快速排序的灵魂,我们通常使用 “双指针法” 来实现分区。
算法步骤：
- 选择最右边的元素作为
pivot（基准）。 - 初始化一个指针
i，指向数组的起始位置-1，这个指针i的作用是记录最后一个小于pivot的元素的位置。 - 使用另一个指针
j从左到右遍历数组（从0到pivot的前一个位置）。 arr[j]小于或等于pivot，就将i向右移动一位，然后交换arr[i]和arr[j]。- 当遍历结束后,
pivot的正确位置就在i+1，将pivot放到这个位置，并返回这个位置的索引。
代码实现：
// 分区函数
// 返回基准值的最终位置
int partition(int arr[], int low, int high) {
// 选择最右边的元素作为基准
int pivot = arr[high];
// i 指向小于基准的最后一个元素的位置
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
// i 向右移动
i++;
// 交换 arr[i] 和 arr[j]
swap(&arr[i], &arr[j]);
}
}
// 将基准值放到正确的位置上 (i+1)
swap(&arr[i + 1], &arr[high]);
// 返回基准值的索引
return (i + 1);
}
辅助交换函数：
// 交换两个整数的值
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
2 递归排序函数
这个函数相对简单,它利用分区函数找到基准的位置，然后递归地对左右两部分进行排序。
代码实现：
// 快速排序主函数 (递归)
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi 是分区后基准的索引
int pi = partition(arr, low, high);
// 递归排序基准左边的子数组
quickSort(arr, low, pi - 1);
// 递归排序基准右边的子数组
quickSort(arr, pi + 1, high);
}
}
完整代码示例
下面是一个完整的、可运行的 C 语言程序，包含了 main 函数来测试我们的快速排序实现。
#include <stdio.h>
// 交换两个整数的值
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 分区函数
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最右边的元素作为基准
int i = (low - 1); // 小于基准的元素的边界
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
i++; // 扩小于基准的区域
swap(&arr[i], &arr[j]);
}
}
// 将基准放到正确的位置
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// 快速排序主函数 (递归)
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // pi 是分区点的索引
// 递归排序左半部分和右半部分
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 打印数组的函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 主函数，用于测试
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组: \n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
编译和运行：
gcc quicksort.c -o quicksort ./quicksort
输出：
原始数组:
10 7 8 9 1 5
排序后的数组:
1 5 7 8 9 10 算法分析
-
时间复杂度:
- 平均情况: O(n log n)，这是快速排序最常见的情况，每次分区都能将数组大致分成两半。
- 最好情况: O(n log n)，当每次分区都能将数组完美地分成两个大小相等的子数组时。
- 最坏情况: O(n²)，当数组已经有序（正序或逆序），并且我们总是选择第一个或最后一个元素作为基准时，每次分区只能减少一个元素，导致递归深度为 n。
-
空间复杂度:
O(log n)，主要来自于递归调用栈的深度，在平均情况下，递归深度为 log n，在最坏情况下，空间复杂度会退化到 O(n)。
-
稳定性:
- 不稳定，在分区过程中，相等的元素的相对位置可能会发生改变。
优化和变种
1 基准的选择优化
最坏情况 O(n²) 的发生很大程度上取决于基准的选择，为了避免总是选择到最差（如最大或最小）的元素，可以采用以下策略：
-
随机化基准: 在分区前，随机选择一个元素与
arr[high]交换，这使得算法对于任何输入数据的性能都趋向于平均情况。// 在 quickSort 函数中，partition 调用之前加入 int random = low + rand() % (high - low); swap(&arr[random], &arr[high]);
-
三数取中法: 选择
arr[low],arr[mid],arr[high]三个元素的中位数作为基准，这能有效避免在已排序或近似排序的数组上出现最坏情况。
2 小数组优化
对于非常小的子数组（长度小于 10），快速排序的递归开销可能比插入排序还要大，一个常见的优化是：当子数组长度小于某个阈值（如 10）时，改用插入排序。
// 在 quickSort 函数中
void quickSort(int arr[], int low, int high) {
// 当子数组长度小于 10 时，使用插入排序
if (high - low < 10) {
insertionSort(arr, low, high);
return;
}
// ... 其余代码不变
}
3 尾递归优化
标准的快速排序有两个递归调用,这可能导致栈空间深度达到 O(n)，可以通过将其中一个递归调用改为循环来优化，将递归深度限制在 O(log n)。
// 尾递归优化版本的 quickSort
void quickSort(int arr[], int low, int high) {
while (low < high) {
int pi = partition(arr, low, high);
// 先处理较小的子数组，以减少栈深度
if (pi - low < high - pi) {
quickSort(arr, low, pi - 1);
low = pi + 1;
} else {
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
这些优化在实际应用中非常重要,可以使快速排序的性能更加稳定和高效。
