单选题 适中
#20822

下面程序的 Merge_Sort 函数时间复杂度为( )。 void Merge ( int a [ ] , int left , int mid , int…

下面程序的 Merge_Sort 函数时间复杂度为( )。

void Merge(int a[], int left, int mid, int right) {
	int temp[right - left + 1];
	int i = left;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= right) {
		if (a[i] < a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	while (i <= mid)
		temp[k++] = a[i++];
	while (j <= right)
		temp[k++] = a[j++];
	for (int m = left, n = 0; m <= right; m++, n++)
		a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right) {
	if (left == right)
		return;
	int mid = (left + right) / 2;
	Merge_Sort(a, left, mid);
	Merge_Sort(a, mid + 1, right);
	Merge(a, left, mid, right);
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析

归并排序基于分治

时间复杂度为O(nlogn)。空间复杂度O(n);