mergesortarray.cpp

来自「可以重复数值的算法排列 这个算法可以得出最优解」· C++ 代码 · 共 91 行

	#include <iostream.h>
	#define n 100  //定义数组的最大个数
    int size=0;

	void Merge( int c[], int d[],int l,int m,int r)
	{ //合并c[l:m]和c[m+1:r]到d[l:r]
		   
		int i=l,j=m+1,k=l;
		   
		while((i<=m)&&(j<=r))
            if(c[i]<=c[j])d[k++]=c[i++];
			else d[k++]=c[j++];
			  
		if(i>m) for(int q=j;q<=r;q++)d[k++]=c[q];
			 else for(int q=i;q<=m;q++)d[k++]=c[q];
		
	}

	int Find(int a[],int Tag[])  //查询每个排好序的子系列的最后一个数字的索引值序列
	{
		
		int j=0;
		Tag[j++]=0;   //第一个数索引值为0
		for(int i=0;i<size;i++)
		{
		   if(i+1<size)
		   {
			   if(a[i]>a[i+1])
			       if(i!=0)Tag[j++]=i;
		   }
		}
		Tag[j]=size-1;  //最后一个数字附加
	
		return j;
	}

	void main()
	{
		
	    int c;     //输入数组的数字
		int	k=0;   
		int	Border=0;
		int number=0;   //输入数字个数
		int a[n],temp[n],d[n],Tag[n];  // a数组存储输入的数字 temp数组记录合并子序列的中间结果
									   //d数组作为辅助数组  tag数组记录每个子序列的最后一个数字的标志符
   
	    cout<<"Please input the numbers to the array (-1 to end):"<<endl;
	    
        while(c!=-1&&number<n)
		{
            cin>>c;
			if(c!=-1)
			temp[number]=d[number]=a[number]=c;   //将所有的数组赋相同的值
			number++;
		}
		size=number-1;
		if ( size != 1 )
		{
	    Border=Find(a,Tag);  //Border记录tag数组的最后一个索引值
		if(k>=Border-1 && a[0]>=a[1])  //只输入2个数
		{ 
			int m = 0;
			m = d[0];
			d[0] = d[1];
			d[1] = m;
		}
		while(k<Border-1)  //循环条件：tag[]不止2个数，
		{
			if(temp[0]>temp[1]) //a数组中第一个数大于第2个数
			{	
				Merge(temp,d,Tag[0],Tag[0],Tag[1]);
				Border=Find(temp,Tag);
			}
			else
			{
				Merge(temp,d,Tag[k],Tag[k+1],Tag[k+2]);
			    Tag[k+1]=Tag[k];
			    k++;
			}
			for(int j=0;j<=Tag[k+1];j++)
				temp[j]=d[j];
		
		}
		}
		//打印出排序后的数组
		for(int i=0;i<size;i++)
		   cout<<d[i]<<" ";
		cout<<endl;

     }