面试题：在O(1)空间复杂度范围内对一个数组中前后连段有序数组进行归并排序

题目：数组al[0,mid-1]和al[mid,num-1]是各自有序的，对数组al[0,num-1]的两个子有序段进行merge，得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注：al[i]元素是支持'<'运算符的。

分析

代码实例：

View Code

新的解体思路

设定两个指针left和right，初始状态下分别指向两个排序数组的首元素，

然后比较a[left]和a[right]大小，

1. 如果a[left]<=a[right]，那么数组中元素位置不发生改变，然后left往前进一步。
2. 如果a[left]>a[right]，则表明前半段元素中存在大于后半段的元素，那么我们将后半段这个小的元素移到前半段来。但是在移动之前，我们得为这个元素空留出地方。这就有了元素移动的操作。比如{1,3,5,7,2,4,6,8,10}这样子序列，我们发现后半段的2小于前半段的3，那么我们将2放入临时变量temp中，然后将{3,5,7}往后移动一个位置，然后将空出来的位置放入temp的值。
3. 这里总体的循环是while(left<right&&right<len)

代码实现

View Code

上面程序的输出结果是

View Code

 本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/05/08/2490343.html，如需转载请自行联系原作者