快速排序基于分而治之的方法。 在 QuickSort(A, p, r) 中，首先，过程 Partition(A, p, r) 将数组 A[p..r] 分成两个子数组 A[p..q-1] 和 A[q+1 ..r] 使得 A[p..q-1] 的每个元素都小于或等于A[q]，反过来，A[q+1..r]的每个元素都大于或等于A[q]。
在运行过程中，两个子数组 A[p..q-1] 和 A[q+1..r] 通过递归调用QuickSort(A,p,q-1)和QuickSort(A,q+ 1,r)。
您的任务是读取序列 A 并根据以下伪代码执行分区：
Partition(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
do if A[j] <= x
then i = i+1
exchange A[i] and A[j]
exchange A[i+1] and A[r]
return i+1
请注意，在此算法中，Partition 始终选择元素 A[r] 作为主元元素，围绕该元素对数组 A[p..r] 进行分区。
输入
输入的第一行包含一个整数 n，即序列 A 中元素的数量。
在第二行 Ai (i = 1,2,...,n) 中，序列的元素以空格字符分隔。
输出
打印排序后的序列。序列的两个连续元素应由空格字符分隔。被选为分区主元的元素应用[ ]表示。
约束
1 ≤ n ≤ 100,000
0 ≤ Ai ≤ 100,000
输入样例
12
13 19 9 5 12 8 7 4 21 2 6 11
输出样例
9 5 8 7 4 2 6 [11] 21 13 19 12
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int Partition(int * a,int p,int r)
{
int x=a[r];
int i=p-1;
for(int j=p;j<r;j++)
{
if(a[j]<=x)
{
i++;
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
int t=a[i+1];
a[i+1]=a[r];
a[r]=t;
return i+1;
}
int main()
{
int n;
scanf("%d",&n);
int *a=(int *)malloc(n*sizeof(int));
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int k=Partition(a,0,n-1);
for(int i=0;i<n;i++)
{
if (i==k) {
printf("[%d] ",a[i]);
} else {
printf("%d ",a[i]);
}
}
return 0;
}