2012年百度校园实习招聘题目及解答（一）

题目

5、算法题2
数组al[0,mid-1] 和 al[mid,num-1]，都分别有序。将其merge成有序数组al[0,num-1]，要求空间复杂度O(1)

我的实现：

将从前半段移除的值，用插入排序插入到后半段数组中，保持有序，这样将前半部分排序完，就这个数组有序了

可以运行的程序地址和word文档：http://download.csdn.net/detail/cq20110310/5196158

希望共同讨论，会不断的发笔试和面试的题目及答案，希望大家支持

void test_merge(int a[],int num,int mid)
{
	int i=0;
	int j=mid;
	int temp;

	while (i<mid)
	{
		if (a[i]<=a[mid])
		{
			i++;
		

		}
		else
		{
			temp=a[i];
			a[i]=a[mid];
			//将从前半段移除的值，用插入排序插入到后半段数组中，保持有序，这样将前半部分排序完，就这个数组有序了

			for (j=mid+1;j<num;j++)
			{
				
				if (temp <=a[j] )
				{
					a[j-1]=temp;

					break;
				}
				else
				{
					a[j-1]=a[j];
				}

				if (j==num-1)
				{
					a[j]=temp;

					break;
				}
			}
			i++;
		}
	}

}