正经题解｜划分数组

【算法分析】

定义 $Divide$ 函数对 $a$ 数组递归的进行划分输出，参数有 $a$ 数组，$l$、$r$，$l$ 和 $r$ 分别表示划分前的第一个位置和最后一个位置。

递归的结束条件是划分到只有一个元素时：l >= r。

int mid = (l + r) / 2;，$mid$ 为划分的中间位置，先输出前半部分 $l$~$mid$，再输出后半部分 $mid+1$~$r$。然后划分前半部分并输出：Divide(a, l, mid);，再划分后半部分并输出：Divide(a, mid + 1, r);。

【参考代码】

#include <iostream>
using namespace std;

const int N = 110;
int a[N];

void Divide(int a[], int l, int r) {
	if (l >= r) return;
	int mid = (l + r) / 2;
	cout << "[";
	for (int i = l; i <= mid; i++) {
		cout << a[i] << " ";
	}
	cout << "],[";
	for (int i = mid + 1; i <= r; i++) {
		cout << a[i] << " ";
	}
	cout << "]" << endl;
	Divide(a, l, mid);
	Divide(a, mid + 1, r);
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	Divide(a, 1, n);
	return 0;
}

【时间复杂度】

$O(log_2n)$

【预计得分】

$100pts$