//快速排序

include <stdio.h>

include <stdlib.h>

define MAXSIZE 100

typedef struct SqList
{
int r[MAXSIZE + 1];
int length;
} SqList;
int Partition(SqList *L, int low, int high)
{ //对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置
int piv;
L->r[0] = L->r[low]; //用子表的第一个记录做枢轴记录
piv = L->r[low]; //枢轴记录关键字保存在piv中
while (low < high) //从表的两端交替地向中间扫描
{
while (low < high && L->r[high] >= piv)
{
high--;
}
L->r[low] = L->r[high]; //将比枢轴记录小的记录移到低端
while (low < high && L->r[low] <= piv)
{
low++;
}
L->r[high] = L->r[low]; //将比枢轴记录小的记录移到高端
}
L->r[low] = L->r[0]; //枢轴记录到位
return low; //返回枢轴位置
}
void QSort(SqList *L, int low, int high) //对顺序表L中的子序列L->r[low]到L->[high]做快速排序
{
int piv;
if (low < high) //长度大于1
{
piv = Partition(L, low, high); //将L->r[low]到L->r[high]一分为二，piv是枢轴位置
QSort(L, low, piv - 1); //对左子表递归排序
QSort(L, piv + 1, high); //对右子表递归排序
}
}
void QuickSort(SqList *L)
{
QSort(L, 1, L->length); //对顺序表L做快速排序
}
int main()
{
SqList *L;
int i;
L = (SqList *)malloc(sizeof(SqList));
printf("请输入长度：");
scanf("%d", &L->length);
printf("请输入元素:");
for (i = 1; i <= L->length; i++)
{
scanf("%d", &L->r[i]);
}
printf("排序前：");
for (i = 1; i <= L->length; i++)
{
printf("%d ", L->r[i]);
}
printf("\n");
QuickSort(L);
printf("排序后：");
for (i = 1; i <= L->length; i++)
{
printf("%d ", L->r[i]);
}
printf("\n");
return 0;
}