快速排序（Quicksort）是一种高效的排序算法，最早由Tony Hoare在1960年提出。它是一个基于分治法的排序算法，通过将数组划分为两个子数组，递归地对两个子数组进行排序，从而实现整个数组的排序。快速排序在实际应用中非常流行，因其在平均情况下具有很好的性能表现。
快速排序的基本思想
- 选择一个基准元素：从数组中选择一个元素作为基准（pivot）。
- 分区操作：将数组重新排序，所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边（等于基准的元素可以任意分到一边）。此操作称为分区（partition）。
- 递归排序：递归地对基准左边和右边的子数组进行快速排序。
快速排序的特点
- 平均时间复杂度：O(n log n)
- 最坏时间复杂度：O(n^2)（当每次选择的基准都是数组的最大或最小元素时）
- 空间复杂度：O(log n)（递归调用消耗的栈空间）
- 不稳定排序：相同元素的相对位置可能会改变
快速排序的C语言实现
#include <stdio.h>
// 函数声明
void quicksort(int array[], int low, int high);
int partition(int array[], int low, int high);
void swap(int* a, int* b);
int main() {
int array[] = {34, 7, 23, 32, 5, 62, 32};
int n = sizeof(array) / sizeof(array[0]);
printf("未排序数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
quicksort(array, 0, n - 1);
printf("排序后数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
// 快速排序主函数
void quicksort(int array[], int low, int high) {
if (low < high) {
// 获取分区点
int pi = partition(array, low, high);
// 递归调用，对左子数组进行排序
quicksort(array, low, pi - 1);
// 递归调用，对右子数组进行排序
quicksort(array, pi + 1, high);
}
}
// 分区函数
int partition(int array[], int low, int high) {
int pivot = array[high]; // 选择最后一个元素作为基准
int i = (low - 1); // i是较小元素的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于基准
if (array[j] <= pivot) {
i++; // 增加较小元素的索引
swap(&array[i], &array[j]); // 交换元素
}
}
swap(&array[i + 1], &array[high]); // 将基准元素放到正确的位置
return (i + 1); // 返回分区点
}
// 交换两个元素的函数
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
代码详细说明
main函数：定义一个数组并打印未排序的数组，然后调用quicksort函数对数组进行排序，最后打印排序后的数组。quicksort函数：递归地对数组进行排序。首先通过partition函数获取分区点，然后递归地对基准左边和右边的子数组进行排序。partition函数：选择数组的最后一个元素作为基准，将数组重新排列，小于基准的元素移到基准的左边，大于基准的元素移到基准的右边，返回基准的位置。swap函数：交换两个整数的值，用于在分区时交换元素的位置。