快速排序是C语言中应用非常广泛的高效排序算法，核心思想基于分治策略，通过选择一个基准元素将待排序数组划分为两个子数组，再对子数组递归执行相同操作，最终完成整个数组的排序。它的平均时间复杂度为O(n log n)，在很多场景下比冒泡排序、插入排序效率更高。
快速排序的基础分治实现逻辑
快速排序的分治过程主要包含三个步骤：首先是选择基准元素，通常可以选择数组的第一个、最后一个或者中间的元素作为基准；其次是对数组进行划分，将小于基准的元素放到基准左侧，大于基准的元素放到基准右侧；最后是对左右两个子数组递归执行上述两个步骤，直到子数组长度为1或0时停止递归。
划分操作是快速排序的核心，下面是基于第一个元素作为基准的基础划分实现：
#include <stdio.h>
// 划分函数，返回基准元素的最终位置
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为基准
int i = low;
int j = high;
while (i < j) {
// 从右向左找第一个小于基准的元素
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
// 从左向右找第一个大于基准的元素
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
// 将基准元素放到最终位置
arr[i] = pivot;
return i;
}
基础递归实现完整快速排序
有了划分函数之后，只需要递归调用划分函数就可以完成整个快速排序的实现，基础递归版本的完整代码如下：
#include <stdio.h>
// 划分函数声明
int partition(int arr[], int low, int high);
// 快速排序递归函数
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pivot_pos = partition(arr, low, high);
// 递归排序左子数组
quick_sort(arr, low, pivot_pos - 1);
// 递归排序右子数组
quick_sort(arr, pivot_pos + 1, high);
}
}
// 打印数组函数
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组：");
print_array(arr, size);
quick_sort(arr, 0, size - 1);
printf("排序后的数组：");
print_array(arr, size);
return 0;
}
// 划分函数定义
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
return i;
}
快速排序的递归优化方案
基础版本的快速排序存在一些不足，比如当数组本身已经有序时，每次选择第一个元素作为基准会导致划分极度不平衡，递归深度会达到O(n)，不仅效率下降到O(n²)，还可能引发栈溢出。下面介绍几种常见的优化方式。
1. 基准元素选择优化
为了避免有序数组下的极端情况，可以采用三数取中法选择基准，即取数组左端、中间、右端三个元素的中值作为基准，这样能让划分更平衡。
// 三数取中法选择基准，调整三个位置的元素，返回基准位置
int median_three(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
// 排序三个位置的元素，让arr[low]是中间值
if (arr[low] > arr[mid]) {
int temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;
}
if (arr[low] > arr[high]) {
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
if (arr[mid] > arr[high]) {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
}
return mid;
}
// 优化后的划分函数，使用三数取中法选基准
int partition_optimized(int arr[], int low, int high) {
int pivot_index = median_three(arr, low, high);
// 将基准元素交换到low位置，方便后续划分
int temp = arr[pivot_index];
arr[pivot_index] = arr[low];
arr[low] = temp;
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
return i;
}
2. 小范围数组切换插入排序
当递归到子数组长度很小时，快速排序的递归开销会超过其效率优势，此时可以切换到插入排序来处理小范围数组，提升整体效率。
// 插入排序函数，用于小范围数组排序
void insertion_sort(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 优化后的快速排序，小范围数组用插入排序
void quick_sort_optimized(int arr[], int low, int high) {
// 子数组长度小于10时切换插入排序
if (high - low + 1 <= 10) {
insertion_sort(arr, low, high);
return;
}
if (low < high) {
int pivot_pos = partition_optimized(arr, low, high);
quick_sort_optimized(arr, low, pivot_pos - 1);
quick_sort_optimized(arr, pivot_pos + 1, high);
}
}
3. 尾递归优化
基础版本的快速排序递归调用两次，当子数组长度不平衡时，递归深度会较大。可以对递归进行优化，每次只递归处理长度更小的子数组，减少递归深度。
// 尾递归优化后的快速排序
void quick_sort_tail_recursion(int arr[], int low, int high) {
while (low < high) {
int pivot_pos = partition_optimized(arr, low, high);
// 优先递归处理长度更小的子数组
if (pivot_pos - low < high - pivot_pos) {
quick_sort_tail_recursion(arr, low, pivot_pos - 1);
low = pivot_pos + 1;
} else {
quick_sort_tail_recursion(arr, pivot_pos + 1, high);
high = pivot_pos - 1;
}
}
}
优化后完整测试代码
将上面的优化方案整合后，完整的优化版快速排序测试代码如下：
#include <stdio.h>
// 三数取中法选择基准
int median_three(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid]) {
int temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;
}
if (arr[low] > arr[high]) {
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
if (arr[mid] > arr[high]) {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
}
return mid;
}
// 优化后的划分函数
int partition_optimized(int arr[], int low, int high) {
int pivot_index = median_three(arr, low, high);
int temp = arr[pivot_index];
arr[pivot_index] = arr[low];
arr[low] = temp;
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
return i;
}
// 插入排序
void insertion_sort(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 尾递归优化+小范围插入排序的快速排序
void quick_sort_optimized(int arr[], int low, int high) {
while (low < high) {
if (high - low + 1 <= 10) {
insertion_sort(arr, low, high);
return;
}
int pivot_pos = partition_optimized(arr, low, high);
if (pivot_pos - low < high - pivot_pos) {
quick_sort_optimized(arr, low, pivot_pos - 1);
low = pivot_pos + 1;
} else {
quick_sort_optimized(arr, pivot_pos + 1, high);
high = pivot_pos - 1;
}
}
}
// 打印数组
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90, 1, 3, 2, 5, 4, 7, 6, 8};
int size = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组：");
print_array(arr, size);
quick_sort_optimized(arr, 0, size - 1);
printf("排序后的数组：");
print_array(arr, size);
return 0;
}
通过上述优化，快速排序在应对有序数组、小范围数组等场景时的效率和稳定性都会有明显提升，开发者可以根据实际业务场景选择对应的优化方案。