重新开贴 讨论一道算法题

题目:将数组[a1,a2,...,an,b1,b2,...,bn],变成[a1,b1,a2,b2,...,an,bn]要求时间复杂度为O(n),并分析空间复杂度
俺实现了目标不过,时间复杂度不是O(n)(代码中函数是sort_arr2),

还有一个函数sort_arr1功能是,能将b对应的元素插入到正确的位置,但是原先a元素位置无法实现,猜想一定是有某种公式,按照这种公式移动b元素后,a元素位置也能确定,并且只需一次循环.
期待高人,搞定O(n)算法,俺实在搞不定,以后慢慢想..

#include "stdafx.h"

#include "iostream"

using namespace std;



int main(int argc, char* argv[])

{

	int arr[] = {11,12,13,14,15,16,17,21,22,23,24,25,26,27};

	void sort_arr1(int array[],int n);//实现将b系列元素插入到正确位置

	void sort_arr2(int array[],int n);//实现功能,但是时间复杂度不符合要求

	void PrintArr(int NumArr[],int n);//打印所有元素



	sort_arr2(arr,7);//函数调用 注意 这里传入的参数为n,而数组元素一共有2n个元素



	return 0;

}



void PrintArr(int NumArr[],int n)

{

	int *p = NumArr;

	while( p < NumArr+n ) cout<<*p++<<" ";

	cout<<endl;

}



void sort_arr1(int array[],int n)

{

	int i,j,temp;

	j = 1; //从数组的第二项开始

	for (i=n;i<2*n-1;i++)

	{

		temp = array[i-n+j];

		array[i-n+j] = array[i];

		array[i] = temp;

		j++;

		printf("第%d趟 ",j-1);

		PrintArr(array,n*2);	

	}

}



void sort_arr2(int array[],int n)

{

	int i,j,k,temp;

	j = 1;

	for(i=n;i<2*n-1;i++)

	{

		temp = array[i-n+j];//保存被b代替的a位置元素

		array[i-n+j] = array[i];//用b位置元素代替a位置元素

		//将当前a位置和b位置之间的所有元素后移一位

		k = i;

		while(k>i-n+j)

		{

			array[k] = array[k-1];

			k--;

		}

		array[i-n+j+1] = temp; //后移后 出现一个空位(即当前a元素的后一个元素),用先前保存过的被b替换过的a 代替

		j++;

		printf("第%d趟 ",j-1);

		PrintArr(array,n*2);

	}

}

运行结果
第1趟 11 21 12 13 14 15 16 17 22 23 24 25 26 27
第2趟 11 21 12 22 13 14 15 16 17 23 24 25 26 27
第3趟 11 21 12 22 13 23 14 15 16 17 24 25 26 27
第4趟 11 21 12 22 13 23 14 24 15 16 17 25 26 27
第5趟 11 21 12 22 13 23 14 24 15 25 16 17 26 27
第6趟 11 21 12 22 13 23 14 24 15 25 16 26 17 27
Press any key to continue