回 帖 发 新 帖 刷新版面

主题:大家帮看下这个归并排序的程序,哪里错了

排序结果不对
template <class T>
void merge(T* array,int p,int q,int r)
{
    int len1=q-p+1;
    int len2=r-q;    

    T* arr1=new T[len1];
    T* arr2=new T[len2];

    for(int i=0; i<len1; i++)
        arr1[i]=array[p+i];
    for(int j=0; j<len2; j++)
        arr2[j]=array[q+j+1];

    i=j=0;
    int k=0;
    
    
    while(i<len1 && j<len2)
    {
        if(arr1[i]<=arr2[j])
        {
            array[k++]=arr1[i++];            
        }
        else
        {
            array[k++]=arr2[j++];
        
        }        
    }

    while(i<len1)        //拷贝arr1剩余的元素
    {
        array[k++]=arr1[i++];                
    }
    while(j<len2)        //拷贝arr2剩余的元素
    {
        array[k++]=arr2[j++];
    }
    
    delete []arr1;
    delete []arr2;    
}

template <class T>
void merge_sort(T* array,int p,int r)        //p,r为待排序数组的起始,终止索引
{
    if(p<r)
    {
        int q=(p+r)/2;
        merge_sort(array,p,q);
        merge_sort(array,q+1,r);
        merge(array,p,q,r);
    }    
}

回复列表 (共1个回复)

沙发

昨天郁闷了半天都没看出来,今天一下子就看出来了,看来人这思维定势挺严重的
int k=0;应改为int k=p;下标从p开始

这人气也忒差了吧,还是回到CSDN吧,昨天愣是在CSDN上发布了帖

我来回复

您尚未登录,请登录后再回复。点此登录或注册