1.插入排序-O(N2)
插入排序由N-1趟排序组成。对于P=1趟和P=N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。
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的元素都被排序。希尔排序的实质是执行多趟间隔为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)。
建堆(大顶堆)过程为，由完全二叉树的最后一个非叶节点(秩为(N-2)/2)开始执行下滤操作，直到堆顶元素为止。删除堆顶元素过程为，将堆顶元素与数组末尾元素互换，新的二叉堆(除去数组后端被置换出的堆顶元素)，再次执行堆顶元素的下滤操作。如此循环，直到堆中只有一个元素。此时，排序完成。此排序无需额外空间，为就地排序。
#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 ] )
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)
归并排序实质是将序列分成左右两个子序列，分别排序，然后再合并成一个有序序列。
/* 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()函数合并两个有序子序列；
void MSort()归并排序递归实现，递归基是Left>=Right，此时序列中只有一个元素；
void Mergesort()分配空间，调用归并函数，释放空间。
5.快速排序-O(NlogN)
设数组S，快速排序为quicksoet(S)，算法为，
1.如果S中元素个数是0或1，则返回；
2.取S中任一元素v，称之为枢纽元(pivot)；
3.将S-{v}(S中其余元素)分成两个不相交的集合；分别为大于等于v的元素集S1和小于等于v的元素集S2；
4.递归实现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()函数选取枢纽元，这是三数中值分割法，对于数组S的N-1个元素，取S[0],S[N-1],S[(N-1)/2]三个数中的中位数作为枢纽元。它还完成了第一次比较，即将三者中最小值放在数组最左端，最大值放在数组最右端，中间值即枢纽元放在数组靠右第二的位置并返回之。
对于只有小于等于Cufoff个的序列，实行插入排序，因为对于很小的数组，快速排序不如插入排序。
每次调整后，都能确定枢纽元的位置，该位置在序列中是稳定的，即为排序后最终位置，可以利用这一点构造寻找数组中第k小数的算法，即快速选择算法，该算法的平均花费为O(N)。算法具体为，每次确定枢纽元的位置i后，与k比较，如果k=i＋1，则寻找成功，如果k<＝i，则继续在前半部分寻找，否则在后半部分寻找。
/* 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 ); |
|
