#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
#define Cutoff (3)

void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void WithSentrySort(ElementType A[],int N)
{
int i,j;
for(i=2;i<N;i++)
{
A[0]=A[i];
for(j=i-1;A[j]>A[0];j--)
{
A[j+1]=A[j];
}
A[j+1]=A[0];
}
}

ElementType Median3(ElementType A[], int Left, int Right)
{
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
swap(&A[Center], &A[Right]);

swap(&A[Center], &A[Right - 1]);
return A[Right - 1];
}

void QSort(ElementType A[], int Left, int Right)
{
int i, j;
ElementType Pivot;
if (Left + Cutoff <= Right){
Pivot = Median3(A, Left, Right);
i = Left; j = Right - 1;
for (;;){
while (A[++i] < Pivot);
while (A[--j] > Pivot);
if (i < j)
swap(&A[i], &A[j]);
else
break;
}
swap(&A[i], &A[Right - 1]);
QSort(A, Left, i - 1);
QSort(A, i + 1, Right);
}
else
WithSentrySort(A + Left, Right - Left + 1);
}

void QuickSort(ElementType A[], int N)
{
QSort(A, 0, N -1);
}

void Print(int A[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
}

int main()
{
const int MAX_ELEMENTS=10;
int list[MAX_ELEMENTS];
int i=0;
for(i=0;i<MAX_ELEMENTS;i++)
list[i]=rand();
printf("排序之前：");
Print(list,MAX_ELEMENTS);
QuickSort(list,MAX_ELEMENTS);

printf("排序之后：");
Print(list,MAX_ELEMENTS);
return 0;
}