分段有序数组合并成有序（空间复杂度为O(1)）

题目描述：

数组A，长度为n，其中A[0, m-1] 和 A[m, n-1]，都分别有序。将其合并成有序数组A[0,n-1]，要求空间复杂度为O(1)。

现在的题目条件是数组分段有序，前后两部分已经有序，如果没有空间复杂度的限制，可以通过建立一个长度为n的空间，然后在O(n)时间内归并成一个有序的数组。

（1）直接插入排序

常见的比较排序算法我们都知道，我们知道在已经基本排序的基础上，直接插入排序的效率是比较高的，所以首先我们能想到的就是利用直接插入排序的方法来解决这个问题，时间复杂度T(n) = m*(n-m)，这是因为每次确定插入位置时，最多需要比较和移动m次，因为前面已经插入的元素已经是在最终位置上了（A[m, n -1]也是有序的原因）。

具体代码如下：

template <typename Type>
void DirectInsertMerge(Type *array, int low, int high, int m)
{
    if (array == NULL || low >= high || low < 0 || m < low || m > high)
    {
        return;
    }

    Type exchange;
    int j;

    for (int i = m; i <= high; ++i)
    {
        exchange = array[i];

        for (j = i - 1; j >= low; --j)
        {
            if (exchange < array[j])
            {
                array[j + 1] = array[j];
            }
            else
            {
                break;
            }
        }

       if( i == j + 1) break;//插入位置为当前所在位置，整个数组已经有序
 
       array[j + 1] = exchange;
    }
}

(2)另一种解法

将A[m]与A[0...m-1]的元素依次顺序比较，当A[m] < A[i]时，将A[m]<--->A[i]进行交换，然后对A [m...n - 1]进行重新排序使其有序（可采用直接插入），然后依次重复上述步骤，不过是A[m]与A[i+1...m-1]的元素依次顺序比较。因为i前面的元素已经在起该在的位置上了。如下图：

这种算法的时间复杂度和直接插入排序一样，T(n) = m*(n-m)，源代码如下：

template <typename Type>
void MergePartialSeq(Type *array, int low, int high, int m)
{
    if (array == NULL || low >= high || low < 0 || m < low || m > high)
    {
        return;
    }

    Type exchange;

    int i = low;
    while( i < m)
    {
        while (i < m && array[m] >= array[i])
            ++i;

        if(i == m) 
            break;

        exchange = array[i];
        array[i] = array[m];
        array[m] = exchange;

        int j = m + 1;
        exchange = array[m];

        while(j <= high && array[j] < exchange)
        {
            array[j - 1] = array[j];
            ++j;
        }

        array[j - 1] = exchange;

        ++i;
    }
}

May 28, 2013 @lab