c++归并排序递归函数-开闭区间的细节

  • 时间:
  • 浏览:
  • 来源:互联网

今天在重写归并函数的时候,当我把闭区间改成开区间后(即把小于等于改为小于)发现运行结果不对:

void Merge_sort(int A[], int temp[], int l, int r)
{
	if (l >= r)return;

	int mid = l + (r - l) / 2;
	int i1 = l, i2 = mid;
	int j1 = mid + 1, j2 = r;
	Merge_sort(A, temp, i1, i2);
	Merge_sort(A, temp, j1, j2);
	int x = l;
	while (i1 <= i2 && j1 <= j2)  //把小于等于改成小于
	{
		temp[x++] = A[i1] < A[j1] ? A[i1++] : A[j1++];
	}
	while (i1 <= i2)	//把小于等于改成小于
		temp[x++] = A[i1++];
	while (j1 <= j2)	//把小于等于改成小于
		temp[x++] = A[j1++];

	for (int j = l; j <= r; j++)	//把小于等于改成小于
		A[j] = temp[j];

}
void mergeSort(int A[], int len)
{
	int *temp=new int[len];
	Merge_sort(A,temp,0,len-1);		//最后一个参数改为len
}

第一次学这个排序的时候已经发现了这个问题,当时没留意,如今再次遇到了,在草稿纸上画了一下,发现如果改为开区间,当递归到最里层的时候 j1==j2,所以while (i1 < i2 && j1 < j2)无法进去,导致第一次归并失败。

本文链接http://www.dzjqx.cn/news/show-617483.html