设子数组A[0:k]和A[k+1:N-1]已排好序(0≤K≤N-1)。试设计一个合并这2个子数组为排好序的数组A[0:N-1]的算法。

设子数组A[0:k]和A[k+1:N-1]已排好序(0≤K≤N-1)。试设计一个合并这2个子数组为排好序的数组A[0:N-1]的算法。要求算法在最坏情况下所用的计算时间为O(N)，只用到O(1)的辅助空间。

//翻转字符串时间复杂度O(to - from)
void reverse(int *a, int from, int to) {
	int t;
	for (; from < to; ++from, --to) {
		t = a[from];
		a[from] = a[to];
		a[to] = t;

	}
}

//循环右移num位 时间复杂度O(n)
void RightRotate(int *a, int begin, int len) {
	reverse(a, 1, len - begin);
	reverse(a, len - begin + 1, len);
	reverse(a, 1, len);
}

void incoperateArray(int* arr, int len, int k) {
	int i = 0;
	int end = k + 1;
	while (end < len) {
		if (arr[i] > arr[end]) {
			RightRotate(arr + i - 1, 1, end - i + 1);
			end++;
		}
		i++;
	}
}

巴特西

设子数组A[0:k]和A[k+1:N-1]已排好序(0≤K≤N-1)。试设计一个合并这2个子数组为排好序的数组A[0:N-1]的算法。

最新文章

热门文章