二路归并正确.txt

完成排序的算法 具体方式为二路归并~~~ ~~~ ~~~ ~~`

#include<iostream>
using namespace std;

typedef struct
{
	int key;
}recordtype;


void merge(recordtype r1[],int low,int mid, int high,recordtype r2[])
//已知r1[low...mid]和r1[mid+1...high]分别按关键字有序排列，将他们合并成一个有序序列，存放在r2[low...high]中；当有序子序列为奇数个或虽为偶数个但最后一个有序子序列长度小于len时的两种情况做特殊处理。
{	int i,j,k;
	i=low;j=mid+1;k=low;
	while((i<=mid)&&(j<=high))
	{
		if(r1[i].key<=r1[j].key	)
		{
			r2[k]=r1[i];++i;
		}
		else
		{
			r2[k]=r1[j];++j;
		}
		++k;
	}
	while(i<=mid)
	{r2[k]=r1[i];k++;i++;}
	while(j<=high)
	{r2[k]=r1[j];k++;j++;}
}//merge end


void mergepass(recordtype r[],int len,int n,recordtype r1[])//依次对R[]中相邻的两个长度为len的有序子序列归并存放在R1[]中，子序列长度为len,
   
 {
	int i=0;
     
	while(i+2*len<=n)//若子序列为偶数并且最后一个有序子序列等于len时
    
   	{
		merge(r,i,i+len-1,i+2*len-1,r1);//合并两相邻子序列
        i=i+2*len; 
	}
   
  	if(i+len<n)//若子序列为偶数但最后一个有序子序列长度小于len时
     
   	 merge(r,i,i+len-1,n,r1); 
 
        else
        
        while(i+1<=n)//若子序列为奇数时
       
       	{
			r1[i]=r[i];  i++; 
		}
   
 }    //mergepass end

  void mergesort(recordtype r[],int n)//二路归并非递归
   
 {
	int len=1;
   	recordtype r1[40];
    
 	while(len<n)
      
  	{
	  mergepass(r,len,n,r1);
      
  	  len=2*len;
      
   	  mergepass(r1,len,n,r);
   
		len=2*len; 
	}
   
 }//mergesort end
 
void main()
 {	
	int n=8;
	recordtype r[]={19,13,5,27,1,26,31,16};
	mergesort(r,n);
	for(int i=0;i<n;i++)
	{
		cout<<r[i].key<<endl;
		
	}


}
红唇  1.2
人气天后 2.2
暗夜－蝶 6
Qeople杂志3.5
春日心情  3.9

沉醉