堆排序、归并排序

堆排序

堆排序伪代码描述：(自底向上建堆)

• 建立最大堆，将最大的元素存在数组末尾)

void Heap_Sort(ElementType A[],int N)
{
    for(i=N/2-1;i>=0;i--)                   //BuildHeap
        PercDown(A,i,N);
    for(i=N-1;i>0;i--)                      //DeleteMax(取出最大元素并在0-i之间构建最大堆)
        Swap(&A[0],&A[i])
        PercDown(A,0,i);
}

将较大的元素放到最后，然后将前面的元素重新建立最小堆
注意，在常规的堆中第0个元素应该存放哨兵，但是对某个数组进行排序时数组可能并没有存放哨兵，此时

• 对于下标为i的元素，其左、右孩子的下标分别为：2i+1, 2i+2

定理：堆排序处理N个不同元素的随机排列的平均比较次数是$2NlogN-O(Nlog(logN))$

• 虽然堆排序给出最佳平均时间复杂度，但实际效果不如用Sedgewick增量序列的希尔排序

堆排序演示

/* 浙江大学示例程序 */
typedef int ElementType;
void Swap( ElementType *a, ElementType *b )
{
     ElementType t = *a; *a = *b; *b = t;
}
 
void PercDown( ElementType A[], int p, int N )
{ /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
  /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;

    X = A[p]; /* 取出根结点存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= A[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

void HeapSort( ElementType A[], int N ) 
{ /* 堆排序 */
     int i;
      
     for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
         PercDown( A, i, N );
     
     for ( i=N-1; i>0; i-- ) {
         /* 删除最大堆顶 */
         Swap( &A[0], &A[i] ); /* 见代码7.1 */
         PercDown( A, 0, i );
     }
}

归并排序

核心：有序子列的归并
例：序列$[1,13,24,26,2,15,27,38]$

• 分为有序子列1：$[1,13,24,26]$，有序子列2：$[2,15,27,38]$
  • 分别在两个子列中进行归并
    • 1和2比较，1是较小的元素，因此将1作为合并后序列的第一个元素
    • 2和13比较，2较小，将2作为第二个元素
    • 以此类推，分别将子列1和子列2中的元素依次比较，选择两个没加入合并序列元素中较小的一个加入合并序列
• 如果两个子列一共有N个元素，则归并的时间复杂度是$T(N)=O(N)$
• 和选择排序一样，归并排序的性能不受输入数据的影响，时间复杂度为$O(NlogN)$

有序子列归并

归并排序：有序子列归并的伪代码描述

void Merge(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd)
//L=左边起始位置，R=右边起始位置，RightEnd=右边终点位置
{
    LeftEnd=R-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--)   //将归并范围内的结果复制到A中
        A[RightEnd]=TmpA[RightEnd];
}

递归实现

归并排序递归算法伪代码描述：分而治之

void MSort(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd)
{
    int Center;
    if(L<RightEnd){
        Center=(L+RightEnd)/2;
        MSort(A,TmpA,L,Center);
        MSort(A,TmpA,Center+1,RightEnd);
        Merge(A,TmpA,L,Center+1,RightEnd);
    }
}

由递推式：$T(N)=T(N/2)+T(N/2)+O(N)$——>$T(N)=O(NlogN)$
稳定性：稳定
递归算法额外空间复杂度$O(N)$

统一函数接口：

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);
    }
    else Error("空间不足");
}

如果只在Merge中声明临时数组:
void Merge(ElementType A[],int L,int R,int RightEnd);
void MSort(ElementType A[],int L,int RightEnd);

• 此时需要不断地在merge中malloc/free这个临时数组TmpA，虽然参数少了，但实际上增加了很多不必要的开销

非递归实现

归并排序非递归算法伪代码描述：

void MSort(ElementType A[],ElementType TmpA[],int N,int length)
//length=当前有序子列的长度
{
    for(i=0;i<=N-2*length;i+=2*length)
        Merge(A,TmpA,i,i+length,i+2*length-1);      //将A中元素归并到TmpA
    if(i+length<N)                                  //归并最后两个子列(还剩两个子列但最后一个子列不满的情况)
        Merge(A,TmpA,i,i+length,N-1);
    else                                            //最后只剩一个子列(只剩一个子列的情况)
        for(j=i;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){                            //每个while循环里做两次merge，保证跳出循环后最终结果一定存在A中
            MSort(A,TmpA,N,length);
            length*=2;
            MSort(TmpA,A,N,length);
            length*=2;                              //一次循环后length实际变成4*length
        }
        free(TmpA);
    }
    else Error("空间不足");
}

• 稳定性：稳定
• 额外空间复杂度：$O(N)$
  • 此算法以length开始进行分组一对一对进行归并A并复制到TmpA中，再以同样过程归并TmpA并复制回A中，直到length等于N
    • 即一个元素与相邻元素构成有序数组，再与旁边数组构成有序数组，直至整个数组有序
• 归并排序由于需要额外空间，并且要在临时数组中来来回回地反复导数据，因此在实际应用中较少用在内排序中
• 在外排序中，归并排序是一个比较有用的工具

归并排序演示

/* 归并排序 - 递归实现 */
#include<cstdio>
#include<cstdlib>
typedef int ElementType;
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }

     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */ 
     int Center;
     
     if ( L < RightEnd ) {
          Center = (L+RightEnd) / 2;
          Msort( A, TmpA, L, Center );              /* 递归解决左边 */ 
          Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */  
          Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */ 
     }
}

void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
     ElementType *TmpA;
     TmpA = (ElementType *)malloc(N*sizeof(ElementType));
     
     if ( TmpA != NULL ) {
          Msort( A, TmpA, 0, N-1 );
          free( TmpA );
     }
     else printf( "空间不足" );
}

/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */

/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j;
      
     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}

void Merge_Sort( ElementType A[], int N )
{ 
     int length; 
     ElementType *TmpA;
     
     length = 1; /* 初始化子序列长度*/
     TmpA = (ElementType*)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 printf( "空间不足" );
}