void InsertionSort( ElementType A[ ], int N ){    int j, P;    ElementType Tmp;    for( P = 1; P < N; P++ )    {        Tmp = A[ P ];        for( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- )            A[ j ] = A[ j - 1 ];        A[ j ] = Tmp;    }}

#define LeftChild( i )  ( 2 * ( i ) + 1 )void PercDown( ElementType A[ ], int i, int N ){    int Child;    ElementType Tmp;    for( Tmp = A[ i ]; LeftChild( i ) < N; i = Child )    {        Child = LeftChild( i );        if( Child != N - 1 && A[ Child + 1 ] > A[ Child ] ) // A[ Child + 1 ] < A[ Child ]            Child++;        if( Tmp < A[ Child ] )          //Tmp > A[ Child ]            A[ i ] = A[ Child ];        //两边的比较同时更改的话，就变成从大到小排序        else            break;    }    A[ i ] =Tmp;}void Heapsort( ElementType A[ ], int N ){    int i;    for( i = N / 2; i >= 0; i-- )  /* BuildHeap */        PercDown( A, i, N );    for( i = N - 1; i > 0; i-- )    {        Swap( &A[ 0 ], &A[ i ] );  /* DeleteMax */        PercDown( A, 0, i );    }}

void Merge( ElementType A[ ], ElementType TmpArray[ ],int Lpos, int Rpos, int RightEnd ){    int i, LeftEnd, NumElements, TmpPos;    LeftEnd = Rpos - 1;    TmpPos = Lpos;    NumElements = RightEnd - Lpos + 1;    /* main loop */    while( Lpos <= LeftEnd && Rpos <= RightEnd )        if( A[ Lpos ] <= A[ Rpos ] )            TmpArray[ TmpPos++ ] = A[ Lpos++ ];        else            TmpArray[ TmpPos++ ] = A[ Rpos++ ];    while( Lpos <= LeftEnd )  /* Copy rest of first half */        TmpArray[ TmpPos++ ] = A[ Lpos++ ];    while( Rpos <= RightEnd ) /* Copy rest of second half */        TmpArray[ TmpPos++ ] = A[ Rpos++ ];    /* Copy TmpArray back */    for( i = 0; i < NumElements; i++, RightEnd-- )        A[ RightEnd ] = TmpArray[ RightEnd ];}void MSort( ElementType A[ ], ElementType TmpArray[ ],int Left, int Right ){    int Center;    if( Left < Right )    {        Center = ( Left + Right ) / 2;        MSort( A, TmpArray, Left, Center );        MSort( A, TmpArray, Center + 1, Right );        Merge( A, TmpArray, Left, Center + 1, Right );    }}void Mergesort( ElementType A[ ], int N ){    ElementType *TmpArray;    TmpArray = malloc( N * sizeof( ElementType ) );    if( TmpArray != NULL )    {        MSort( A, TmpArray, 0, N - 1 );        free( TmpArray );    }    else        FatalError( "No space for tmp array!!!" );}

/* Return median of Left, Center, and Right *//* Order these and hide the pivot */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 ] );    /* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */    Swap( &A[ Center ], &A[ Right - 1 ] );  /* Hide pivot */    return A[ Right - 1 ];                /* Return pivot */}#define Cutoff ( 3 )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 ] );  /* Restore pivot */        Qsort( A, Left, i - 1 );        Qsort( A, i + 1, Right );    }    else  /* Do an insertion sort on the subarray */        InsertionSort( A + Left, Right - Left + 1 );}/* This code doesn‘t work; it‘s Figure 7.15. *///A[i] = A[j] = Pivot时，程序死循环#if 0/* START: fig7_15.txt */i = Left + 1;j = Right - 2;for( ; ; ){    while( A[ i ] < Pivot ) i++;    while( A[ j ] > Pivot ) j--;    if( i < j )        Swap( &A[ i ], &A[ j ] );    else        break;}#endifvoid Quicksort( ElementType A[ ], int N ){    Qsort( A, 0, N - 1 );}