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