－希尔排序
克服插入排序每次只能交换一对元素的缺点
5-间隔的排序，3-间隔的排序，1-间隔排序（最后必须是1-间隔）
最重要的性质：更小间隔的排序不会破坏较大间隔排序的大小序列
原始希尔排序
void Shell_sort ( ElementType A[ ], int N )
{
for ( D = N/2 ; D > 0 ; D /= 2 ) { // 希尔增量序列（eg：5、3、1）
for ( P = D ; P < N ; P ++ ) { // 插入排序
Tmp = A [ P ] ;
for ( i = p ; i >= D && A[ i - D ] > Tmp ; i -= D )
A[ i ] = A[ i - D ] ;
A[ i ] = Tmp ;
}
}
}
如果增量元素不互质，则小增量可能根本不起作用
＊更大增量序列：
Hibbard增量序列： Dk = 2的k次方－1；相邻的元素互质
Sedgewick增量序列：｛1，5，19，41，109，…｝；
－堆排序
选择排序中，从未排序序列中找出最小元素，取出放入最小位置。这一过程也是一个for循环，会提高时间复杂度，堆排序是在选择排序的基础上改进这一过程
void Heap_Sort ( ElementType A[ ], int N )
{
for ( i = N/2 ; i >= 0 ; i - - ) // 建立最小堆
PercDown ( A , i , N ) ; // i 对应根结点的位置，N对应当前堆里有多少元素
for ( i = N - 1 ; i > 0 ; i - - ){
Swap ( &A[ 0 ] , & A [ i ] ) ; // i 纪录当前最后元素的下标
PercDown ( A , 0 , i ) ; // 调整为最大堆
}
}
定理：堆排序处理N个不同元素的随机排列的平均比较次数是：2N logN - O ( N log logN )
虽然堆排序给出最佳平均时间复杂度，但实际效果不如用Sedgewick增量排序的希尔排序。
－归并排序
核心：两个有序子序列的归并
void Merge { ElementType A[ ] , ElementType TmpA[ ] , int L , int R , int RightEnd }
// A[ ]是原始待排的序列，TmpA[ ]是临时存放数组
{
LeftEnd = R - 1 ; // 左边终点位置。假设左右两列挨着，左边位置等于右边位置减1
Tmp = L ; // 存放结果的数组的初始位置
NumElements = RightEnd - L + 1 ; // 归并结束后元素数量
while ( L <= LeftEnd && R <= RightEnd ){
if ( A[ L ] <= A[ R ] ) TmpA [ Tmp ++ ] = A[ L++ ] ;
else TmpA [ Tmp ++ ] = A[ R++ ] ;
}
while ( L <= LeftEnd ) // 直接复制左边剩下的
TmpA [ Tmp ++ ] = A [ L++ ] ;
while ( R <= RightEnd ) // 直接复制右边剩下的
TmpA [ Tmp++ ] = A[ R++ ] ;
for ( i = 0 ; i < NumElements ; i ++ , RightEnd - - ) // 由于 RightEnd一直没变，从它开始讲TmpA倒入A
A[ RightEnd ] = TmpA[ RightEnd ] ;
}
递归算法（分而治之）
void MSort { ElementType A[ ] , ElementType TmpA[ ] , int L , int RightEnd }
{
int Center ;
if ( L < RightEnd ){
Center = ( L + RightEnd ) / 2 ;
MSort ( A , TmpA , L , Center ) / 2 ;
MSort ( A , TmpA , Center + 1 , RightEnd ) ;
Merge ( A , TmpA , L , Center + 1 , RightEnd ) ;
}
}
统一函数接口
void Merge_sort ( ElementType A[ ] , int N )
{
ElementType *TmpA ;
TmpA = malloc ( N * sizeof ( ElementType ) ) ; // 申请一块与原始序列同样大小的内存作为临时数组
if ( TmpA != NULL ){
MSort ( A , TmpA , 0 , N - 1 ) ;
free ( TmpA ) ; // 释放临时数组 TmpA
}
else Error ( “空间不足” ) ;
}
非递归算法
void Merge_pass { ElementType A[ ] , ElementType TmpA[ ] , int N , int length } // 当前有序子列的长度
{
for ( i = 0 ; i <= N - 2length ; i += 2length )
Merge1 ( A , TmpA , i , i + length , i + 2*length - 1 ) ; // 将A中元素归并到TmpA中
if ( i + length < N ) // 归并最后2个子列
Merge1 ( A , TmpA , i , i + length , N - 1 ) ;
else // 最后只剩1个子列
for ( j = 1 ; j < N ; j ++ ) TmpA[ j ] = A[ j ] ;
}
统一接口：
void Merge_sort ( ElementType A[ ] , int N )
{
ElementType *TmpA ;
TmpA = malloc ( N * sizeof ( ElementType ) ) ;
if ( TmpA != NULL ) {
while ( length < N ) {
Merge_pass ( A , TmpA , N , length ) ;
length += 2 ;
Merge_pass ( TmpA , A , N , length ) ;
length *= 2 ;
}
free ( TmpA ) ;
}
else Error ( “空间不足" )
}
它是稳定的，一般不做内排序，做外排序时非常有用
