1.插入排序-O(N2)
插入排序由N-1趟排序組成。對于P=1趟和P=N-1趟，插入排序保證從位置0到位置P上的元素為已排序狀態(tài)。
typedef int ElementType;
void Swap( ElementType *Lhs, ElementType *Rhs )
{
ElementType Tmp = *Lhs;
*Lhs = *Rhs;
*Rhs = Tmp;
}
/* 插入排序 */
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;
}
}
2.希爾排序-O(N2)
希爾排序使用一個增量序列h1,h2,...,ht,其中h1=1。每次選擇ht,ht-1,..,h1進行排序，對于每個增量hk排序后，有A[i]<=A[i+hk]，即所有相隔hk的元素都被排序。希爾排序的實質(zhì)是執(zhí)行多趟間隔為hk的元素間的插入排序。
/* 希爾排序 */
void Shellsort( ElementType A[ ], int N )
{
int i, j, Increment;
ElementType Tmp;
for( Increment = N / 2; Increment > 0; Increment /= 2 )
for( i = Increment; i < N; i++ )
{
Tmp = A[ i ];
for( j = i; j >= Increment; j -= Increment )
if( Tmp < A[ j - Increment ] )
A[ j ] = A[ j - Increment ];
else
break;
A[ j ] = Tmp;
}
}
3.堆排序-O(NlogN)
堆排序由兩個過程組成，一是建堆-O(N)，二是N-1次刪除堆頂元素-O(NlogN)。
建堆(大頂堆)過程為，由完全二叉樹的最后一個非葉節(jié)點(秩為(N-2)/2)開始執(zhí)行下濾操作，直到堆頂元素為止。刪除堆頂元素過程為，將堆頂元素與數(shù)組末尾元素互換，新的二叉堆(除去數(shù)組后端被置換出的堆頂元素)，再次執(zhí)行堆頂元素的下濾操作。如此循環(huán)，直到堆中只有一個元素。此時，排序完成。此排序無需額外空間，為就地排序。
#define LeftChild( i ) ( 2 * ( i ) + 1 )
/* 下濾過程，構(gòu)建大頂堆 */
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 ] )
Child++;
if( Tmp < A[ Child ] )
A[ i ] = A[ Child ];
else
break;
}
A[ i ] =Tmp;
}
/* 就地堆排序 */
void Heapsort( ElementType A[ ], int N )
{
int i;
for( i = (N - 2) / 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 );
}
}
4.歸并排序-O(NlogN)
歸并排序?qū)嵸|(zhì)是將序列分成左右兩個子序列，分別排序，然后再合并成一個有序序列。
/* Lpos = start of left half, Rpos = start of right half */
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!!!" );
}
void Merge()函數(shù)合并兩個有序子序列；
void MSort()歸并排序遞歸實現(xiàn)，遞歸基是Left>=Right，此時序列中只有一個元素；
void Mergesort()分配空間，調(diào)用歸并函數(shù)，釋放空間。
5.快速排序-O(NlogN)
設(shè)數(shù)組S，快速排序為quicksoet(S)，算法為，
1.如果S中元素個數(shù)是0或1，則返回；
2.取S中任一元素v，稱之為樞紐元(pivot)；
3.將S-{v}(S中其余元素)分成兩個不相交的集合；分別為大于等于v的元素集S1和小于等于v的元素集S2；
4.遞歸實現(xiàn)quicksort(S1)和quicksort(S2)。
/* 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 );
}
void Quicksort( ElementType A[ ], int N )
{
Qsort( A, 0, N - 1 );
}
使用Median3()函數(shù)選取樞紐元，這是三數(shù)中值分割法，對于數(shù)組S的N-1個元素，取S[0],S[N-1],S[(N-1)/2]三個數(shù)中的中位數(shù)作為樞紐元。它還完成了第一次比較，即將三者中最小值放在數(shù)組最左端，最大值放在數(shù)組最右端，中間值即樞紐元放在數(shù)組靠右第二的位置并返回之。
對于只有小于等于Cufoff個的序列，實行插入排序，因為對于很小的數(shù)組，快速排序不如插入排序。
每次調(diào)整后，都能確定樞紐元的位置，該位置在序列中是穩(wěn)定的，即為排序后最終位置，可以利用這一點構(gòu)造尋找數(shù)組中第k小數(shù)的算法，即快速選擇算法，該算法的平均花費為O(N)。算法具體為，每次確定樞紐元的位置i后，與k比較，如果k=i＋1，則尋找成功，如果k<＝i，則繼續(xù)在前半部分尋找，否則在后半部分尋找。
/* Places the kth smallest element in the kth position */
/* Because arrays start at 0, this will be index k-1 */
void Qselect( ElementType A[ ], int k, 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 */
if( k <= i )
Qselect( A, k, Left, i - 1 );
else if( k > i + 1 )
Qselect( A, k, i + 1, Right );
}
else /* Do an insertion sort on the subarray */
InsertionSort( A + Left, Right - Left + 1 ); |
|
