定第一个元素为中间值
然后一直分两半递归
#include<stdio.h>
#include<stdlib.h>
int n, a[105]; // n 为数组元素个数，a 为待排序数组（下标从 1 开始）
/*
* 快速排序函数
* 参数：a[] - 待排序数组
* l - 左边界（起始下标）
* r - 右边界（结束下标）
* 空间复杂度：O(logn)（递归栈深度）
* 稳定性：不稳定
* 平均时间复杂度：O(nlogn)
* 最坏时间复杂度：O(n^2)（当数组已经有序或逆序时）
*/
void Qsort(int a[], int l, int r)
{
int p; // 基准值
if (l < r) // 当区间长度大于1时才需要排序
{
int i = l, j = r;
p = a[l]; // 选取当前区间第一个元素作为基准值
while (i < j) // 当左右指针未相遇时
{
// 从右向左扫描，找到第一个小于基准值的元素
while (i < j && a[j] > p) j--;
if (i < j) // 找到后放入左边的空位
{
a[i] = a[j];
i++; // 左指针右移一位
}
// 从左向右扫描，找到第一个大于基准值的元素
while (i < j && a[i] < p) i++;
if (i < j) // 找到后放入右边的空位
{
a[j] = a[i];
j--; // 右指针左移一位
}
}
// 循环结束时 i == j，即为基准值的最终位置
a[i] = p;
// 递归处理基准值左边的子区间
Qsort(a, l, i - 1);
// 递归处理基准值右边的子区间
Qsort(a, i + 1, r);
}
}
int main()
{
// 输入元素个数
scanf("%d", &n);
// 输入数组元素（下标从 1 开始）
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
// 调用快速排序
Qsort(a, 1, n);
// 输出排序后的数组
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}