#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Cutoff 10
typedef int ElementType;
/交换地址的函数/
void Swap(ElementType a, ElementTypeb){
ElementType *c;
c=*a;
*a=*b;
b=c;
}
/下面的是插入排序，当数组元素个数不多时用插入排序/
void InsertionSort(ElementType A[],int N){
int p,i;
ElementType Tmp;
for(p=1;p<N;p++){
Tmp=A[p];
for(i=p;i>0&&A[i-1]>Tmp;i--){
A[i]=A[i-1];
}A[i]=Tmp;
}
}
/下面的找基准，提高快速排序的效率/
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]; / 返回基准Pivot /
}
/下面是快速排序主要程序，采用递归的形式/
void Qsort( ElementType A[], int Left, int Right )
{ / 核心递归函数 /
int Pivot, Low, High;
if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
Pivot = Median3( A, Left, Right ); /* 选基准 */
Low = Left; High = Right-1;
while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( A[++Low] < Pivot ) ;
while ( A[--High] > Pivot ) ;
if ( Low < High ) Swap( &A[Low], &A[High] );
else break;
}
Swap( &A[Low], &A[Right-1] ); / 将基准换到正确的位置 /
Qsort( A, Left, Low-1 ); / 递归解决左边 /
Qsort( A, Low+1, Right ); / 递归解决右边 /
}
else InsertionSort( A+Left, Right-Left+1 ); / 元素太少，用简单插入排序 */
}
int main(){
int i,n;
scanf("%d",&n);
int A[n];
for(i=0;i<n;i++){
scanf("%d",&A[i]);
}
for(i=0;i<n;i++){
printf(" %4d",A[i]);
}
printf("\n");
Qsort(A,0,n-1);
for(i=0;i<n+10;i++){
printf(" %4d",A[i]);
}}
