我有以下代码
void mergesort(int size, int ar[], int temp[])
{
if(size <=1)
{
return;}
else
{
int i = 0;
int mid = size/2;
int *left = &ar[0];
int *right = &ar[mid];
int *rend = &ar[size];
int *lend = right;
mergesort(mid,left,temp);
mergesort(size-mid,right,temp);
for(i=0; i<size;i++)
{
if(left < lend && (*left < *right || right >= rend))
{
temp[i] = *left++;
}
else
{
temp[i] = *right++;
}
}
for(i = 0; i < size; i++)
{
ar[i] = temp[i];
}
}
}
我不明白这个if语句是如何工作的:
if(left < lend && (*left < *right || right >= rend))
{
temp[i] = *left++;
}
else
{
temp[i] = *right++;
}
你能告诉我里面发生了什么事吗为什么我们要比较地址(左=rend)
下面是如何从main调用mergesort函数
const int SIZE = 8;
int array[SIZE] = {3,6,1,-9,0,2,4,5};
int temp[SIZE];
mergesort(SIZE, array,temp);
最佳答案
为了在左或右序列之间选择输入,您需要知道序列是否已用尽。通过测试指针来检查它是否超出有效范围left < lend
如果左序列未用尽,则返回true
;如果右序列用尽,则返回right >= rend
因此,当左序列未用尽,且左项目小于右项目或右序列已用尽时,将采用true
。
如果您遵循标准库迭代器约定,则永远不会在比较中检查if
或<
。>
和left != lend
在您发布的代码中同样有效。
附:两个不属于你问题的想法:
正如评论中指出的,在比较中隐藏着未定义的行为。在检查右侧指针的值之前,需要测试右侧是否已用尽。
如果使用正确的比较,合并排序自然是稳定的你想从左边的序列中提取任何领带在排序的情况下,这无关紧要,因为你无法区分一个相同的right == rend
与另一个相同的int
,但如果这只是一个大结构的一部分的关键,它可能会有很大的关系这只是把int
替换为<
的问题。
综合以上所有建议,你最终会得到:
if (left != lend && (right == rend || *left <= *right))