小结主要排序算法

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;
　　　　　　　　}
}