//快速排序

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)
{ //對(duì)順序表L中的子表r[low..high]進(jìn)行一趟排序，返回樞軸位置
int piv;
L->r[0] = L->r[low]; //用子表的第一個(gè)記錄做樞軸記錄
piv = L->r[low]; //樞軸記錄關(guān)鍵字保存在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) //對(duì)順序表L中的子序列L->r[low]到L->[high]做快速排序
{
int piv;
if (low < high) //長(zhǎng)度大于1
{
piv = Partition(L, low, high); //將L->r[low]到L->r[high]一分為二，piv是樞軸位置
QSort(L, low, piv - 1); //對(duì)左子表遞歸排序
QSort(L, piv + 1, high); //對(duì)右子表遞歸排序
}
}
void QuickSort(SqList *L)
{
QSort(L, 1, L->length); //對(duì)順序表L做快速排序
}
int main()
{
SqList *L;
int i;
L = (SqList *)malloc(sizeof(SqList));
printf("請(qǐng)輸入長(zhǎng)度：");
scanf("%d", &L->length);
printf("請(qǐng)輸入元素:");
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;
}