O(1)时间合并算法

问题描述：

设子数组a[0:k-1]和a[k:n-1]已经排序（0<=k<=n-1）。请设计一个合并这两个子数组为排好序的数组a[0:n-1]的算法。要求算法在最坏情况下所用的计算时间为O(n)，且只用到O(1)的辅助空间。

分析与解答：

（1）向右循环换位合并

向右循环换位合并算法首先用二分搜索算法在数组段a[k:n-1]中搜索a[0]的插入位置，即找到位置p使得a[p]。数组段a[0:p]向右循环换位p-k+1个位置，使得a[k-1]移动到a[p]的位置。此时，原数组a[0]及其左边的所有元素均已经排好序。对剩余的数组元素重复上述过程，直到只剩下一个数组段，此时整个数组已经排好序。
    代码如下所示。

#include <iostream>
using namespace std;

#define MAXNUM 100

//下面函数将数组段a[s:t]中元素循环右移位k个位置
void shiftright(int a[], int s, int t, int k)
{
    int i = 0;
    int j = 0;
    for(i = 0; i < k; i++)
    {
        int tmp = a[t];
        for(j = t; j > s; j--)
        {
            a[j] = a[j-1];
        }
        a[s] = tmp;
    }
}

//下面函数用于在数组段中a[left:right]中搜索元素x的插入位置
int binarySearch(int a[], int x, int left, int right)
{
    int mid;
    while(left <= right)
    {
        mid = left + (right - left)/2;
        if(x == a[mid])
        {
            return mid;
        }
        if(x > a[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    if(x > a[mid])
    {
        return mid;
    }
    else
    {
        return mid - 1;
    }
}

//向右循环移位合并算法
//length:数组的长度
void mergefor(int a[], int k, int length)
{
    //merge a[0:k-1] and a[k:n-1]
    int i = 0;
    int j = k;
    while(i < j && j < length)
    {
        int p = binarySearch(a, a[i], j, length - 1);
        shiftright(a, i, p, p - j + 1);
        j = p + 1;
        i += p - j + 2;
    }
}

int main(int argc, char* argv[])
{
    //这里的 k = 5，即a[0:4]、a[5:8]
    int a[9] = {1, 3, 5 , 7, 9, 2, 4, 6, 8};
    int length = sizeof(a)/ sizeof(a[0]);

    cout << "原数组为：" << endl;
    for(int i = 0; i < length; i++)
    {
        cout << a[i] << "  ";
    }


    mergefor(a, 5, length);

    cout << endl << "排序后为：" << endl;
    for(int i = 0; i < length; i++)
    {
        cout << a[i] << "  ";
    }
    cout << endl;
    return 0;
}

        上述算法中，数组段a[0:k-1]中元素的移动次数不超过k次，数组段a[k:n-1]中元素最多移动一次。因此，算法的元素移动总次数为:k^2+(n-k)次。算法的比较次数不超过klog(n - k)（这个不明白）。当k <n^1/2时，算法的时间复杂度为O(n)；反之，则为O(n*n）。
        说实话，这个算法的过程，是比较难想的，因此，为了更加好的理解，特意举例如下。     
        
        
        


    


        参考：《算法设计与分析实验题解》



                                                            梦醒潇湘love
                                                        2013年4月16日 15:36