原题链接:http://www.dotcpp.com/oj/problem1169.html (大家可以自行提交)
解题思路: 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] );
}