主题:大家帮看下这个归并排序的程序,哪里错了
排序结果不对
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);
}
}
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);
}
}