Manchester- 【绝对值排序】(合并排序详解+图解)

解题思路:
1.采用分治法思想，把整个序列，拆分为多个子序列，分别对多个子序列排序，再把排好序的子序列合并起来，具体如图：

拆分过程实现：

void Mesort(int *A,int *B,int left,int right)//B[],用于合并排序时
{
 if(left<right)   //子序列长度大于一，则继续分
 {
    int i=(left+right)/2;   //求中点  
      Mesort(A,B,left,i);    //左半部分拆分
      Mesort(A,B,i+1 ,right);  //右半部分拆分
 }
}

合并加排序实现：

void Merge(int *A,int *B,int left,int middle,int right)
{
int  i=left,j=middle+1,k=left;  //i为右半部分第一个数的下标，j为左半部分第一个数的下标
                                //B[]用于存放排好序的序列
while((i<=middle)&&(j<=right))  //左右两部分同时遍历
{
    if(fabs(A[i])>=fabs(A[j]))  //把左右两部分的绝对值大的存入B[]
      B[k++]=A[i++];
     else
      B[k++]=A[j++];
}
//这里把剩余部分存到B[]里，因为每一个子序列都是排好序的，直接存放就可
if(i>middle)    
    for(int q=j;q<=right;q++)  //左半部分序列有剩余
       B[k++]=A[q];
else
    for(int q=i;q<=middle;q++) //右半部分序列有剩余
       B[k++]=A[q];

}

把排好序的部分B[],复制回A[].

void copy(int *A,int *B,int left,int right)
{
   for(;left<=right;left++)
       A[left]=B[left];
}

完整递归：

void Mesort(int *A,int *B,int left,int right)
{
 if(left<right)
 {
    int i=(left+right)/2;
      Mesort(A,B,left,i);
      Mesort(A,B,i+1 ,right);
      Merge(A,B,left,i,right);
    copy(A,B,left,right);
 }
}

注意：只以0结束的话，提交会输出超限，得加上以文件末尾结束

参考代码:

#include <stdio.h>
#include <malloc.h>
#include <math.h>
void input( int *A, int n );
void output( int *A, int n );
void Mesort( int *A, int *B, int left, int right );
void Merge( int *A, int *B, int left, int middle, int right );
void copy( int *A, int *B, int left, int right );

/*--------------------------------------------------------*/
int main()
{
    int    *A, *B;
    int    n;
    while ( scanf( "%d", &n ) != EOF && n != 0 )
    {
        A    = (int *) malloc( n * sizeof(int) );
        B    = (int *) malloc( n * sizeof(int) );
        input( A, n );
        Mesort( A, B, 0, n - 1 );
        output( A, n );
        free( A );
        free( B );
    }
    return(0);
}


/*--------------------------------------------------------*/
void Mesort( int *A, int *B, int left, int right )
{
    if ( left < right )
    {
        int i = (left + right) / 2;
        Mesort( A, B, left, i );
        Mesort( A, B, i + 1, right );
        Merge( A, B, left, i, right );
        copy( A, B, left, right );
    }
}


/*--------------------------------------------------------*/
void Merge( int *A, int *B, int left, int middle, int right )
{
    int i = left, j = middle + 1, k = left;

    while ( (i <= middle) && (j <= right) )
    {
        if ( fabs( A[i] ) >= fabs( A[j] ) )
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    }

    if ( i > middle )
        for ( int q = j; q <= right; q++ )
            B[k++] = A[q];
    else
        for ( int q = i; q <= middle; q++ )
            B[k++] = A[q];
}

/*--------------------------------------------------------*/
void copy( int *A, int *B, int left, int right )
{
    for (; left <= right; left++ )
        A[left] = B[left];
}

/*-------------------------*/
void input( int *A, int n )
{
    for ( int i = 0; i < n; i++ )
        scanf( "%d", &A[i] );
}

/*-------------------------*/
void output( int *A, int n )
{
    for ( int i = 0; i < n - 1; i++ )
        printf( "%d ", A[i] );
    printf( "%d\n", A[n - 1] );
}

别忘点赞哦-.-

附带一个选择排序实现：详解见1129题（在选择排序基础上加上个绝对值）

#include <stdio.h>
#include <malloc.h>
#include <math.h>
void sort( int n );
void input( int *A, int n );
void output( int *A, int n );
/*----------------------------------------------------*/
int main()
{
    int n;
    while ( scanf( "%d", &n ) != EOF && n != 0 )
        sort( n );
    return(0);
}

/*----------------------------------------------------*/
void sort( int n )
{
    int    *A;
    int    maxi, term;
    A = (int *) malloc( n * sizeof(int) );

    input( A, n );

    for ( int i = 0; i < n; i++ )
    {
        maxi = i;
        for ( int j = i; j < n; j++ )
        {
            if ( fabs( A[maxi] ) < fabs( A[j] ) )
                maxi = j;
        }

        if ( i != maxi )
        {
            term    = A[i];
            A[i]    = A[maxi];
            A[maxi] = term;
        }
    }

    output( A, n );
    return;
}
/*----------------------------------------------------*/
void input( int *A, int n )
{
    for ( int i = 0; i < n; i++ )
        scanf( "%d", &A[i] );
}
/*----------------------------------------------------*/
void output( int *A, int n )
{
    for ( int i = 0; i < n - 1; i++ )
        printf( "%d ", A[i] );
    printf( "%d\n", A[n - 1] );
}

别忘点赞哦-.-