merge_sort.cpp

在数据结构中

/* 二路归并排序算法的源程序*/
//本算法是从小到大进行排序

#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define MaxNum 100
typedef struct RecordNode
{  
	int num;       //排序码序号
	int value;
}RecordNode;

void Merge(RecordNode r[], RecordNode r1[], int low, int m, int high)
{               //r[low]到r[m]和r[m+1]到r[hign]是两个有序文件
  int i,j,k;i=low;j=m+1;k=low;
  while((i<=m)&&(j<=high))
  {
	  if(r[i].value<=r[j].value)      //从两个有序文件中的第一个记录中选出小的记录
      r1[k++]=r[i++];
      else  r1[k++]=r[j++];
  }
  while(i<=m)  
	  r1[k++]=r[i++];       //复制第一个文件的剩余记录
  while(j<=high) 
	  r1[k++]=r[j++];       //复制第二个文件的剩余记录
}

//对r做一趟归并，结果放在r1中
void MergePass(RecordNode r[], RecordNode r1[], int n, int length)
{    
	int i,j;i=0;                       //length为本趟归并的有序子文件的长度
    while(i+2*length-1<n)
	{
		Merge(r,r1,i,i+length-1,i+2*length-1);     //归并长度为length的两个子文件
        i+=2*length;
	}
    if(i+length-1<n-1)                             //剩下两个子文件，其中一个长度小于 length 
      Merge(r,r1,i,i+length-1,n-1);
    else
      for(j=i;j<n;j++)                             // 将最后一个子文件复制到数组r1中
      r1[j]=r[j];
}

void Merge_Sort(RecordNode *Seq,int m)
{
	//seq[]是待排序的数组，m是排序元素的个数
	RecordNode *record;
	record=(RecordNode *)malloc(m*sizeof(RecordNode));
    int length=1;
    while(length<m)
	{
		MergePass(Seq,record,m,length);   //一趟归并，结果存放在数组r1中
        length*=2;
        MergePass(record,Seq,m,length);   //一趟归并，结果存放在数组r中
        length*=2;
  }
}

int main()
{
	int i;
//	int data;
	RecordNode *array;
	int test[]={49,38,65,97,76,13,27,50};
	array=(RecordNode *)malloc(MaxNum*sizeof(RecordNode));
	for(i=0;i<8;i++){
		(array+i)->num=i;
//        scanf("%d",&data);
		(array+i)->value=test[i];
	}
	int len=8;
	Merge_Sort(array,len);
	for(i=0;i<8;i++)
	 printf("%d ",(array+i)->value);
	printf("\n");
	return 1;
}