百度实习生笔试题 数组内Merge
题目：

算法和程序设计二：数组al[0...mid-1]和al[mid...num-1]两个部分都已经分别排好序。要求合并使得整个数组al有序。请给出合并merge的代码。要求空间复杂度为O(1)。

我的想法的时间复杂度可能到了o(n^2)了，所以想求教大家的思路。

[解决办法]
我的想法是：定义两个游标，分别指向两段的未处理的数据，然后根据游标来插入数据，并且将第二段之前的数据进行后移一格。估计时间复杂度也很高。
[解决办法]

C/C++ code

void mergeArray(int a[], int first, int mid ,int last){    int i, j = mid +1;    int k, flag = 0;    while ( a[j] < a[j-1] && j <= last )    {        k = flag;        for ( i = j-1; i >= k ; i--)            if ( a[i] > a[i+1] )            {                Swap( a[i], a[i+1] );                flag = i;            }        j ++;    }}
[解决办法]
很简单，前半段的小那么不用操作，后半段的小，就把后半段和前半段交换，然后后半段做一个插入排序（因为交换前后半段<前半段，所以交换后需向后做插入排序）。
[解决办法]
探讨

题目：

算法和程序设计二：数组al[0...mid-1]和al[mid...num-1]两个部分都已经分别排好序。要求合并使得整个数组al有序。请给出合并merge的代码。要求空间复杂度为O(1)。

我的想法的时间复杂度可能到了o(n^2)了，所以想求教大家的思路。

[解决办法]
探讨


算法复杂度最低应该是O(n)

[解决办法]
C/C++ code
#include <stdio.h>#include <stdlib.h>#include <string.h>int lower_bound(int *arr, int begin, int end, int target) {    while (begin <= end) {        int middle = begin + (end - begin) / 2;        if (target <= arr[middle]) {            end = middle - 1;        } else {            begin = middle + 1;        }    }    return end + 1;}int merge(int *arr, int num) {    if (arr == NULL) {        return -1;    }     if (num <= 1) {        return 0;    }    int l_begin = 0, l_end = (num / 2) - 1;    int r_begin = l_end + 1, r_end = num -1;        while (l_begin <= l_end) {        if (arr[l_begin] > arr[r_begin]) {            int temp = arr[l_begin];            arr[l_begin] = arr[r_begin];            /* 慢速版            int ndx = r_begin + 1;                        while (ndx <= r_end && temp > arr[ndx]) {                arr[ndx - 1] = arr[ndx];                ++ ndx;            }            arr[ndx - 1] = temp;            */             /* 二分版 */            if (r_end - r_begin + 1 > 1) {                int ndx = lower_bound(arr, r_begin + 1, num - 1, temp);                if (ndx == r_begin + 1) {                    arr[r_begin] = temp;                } else {                    memmove(arr + r_begin, arr + r_begin + 1,                         sizeof(int) * (ndx - r_begin - 1));                    arr[ndx - 1] = temp;                }            } else {                arr[r_begin] = temp;            }        }        ++ l_begin;    }    return 0;}int main(int argc, char* const argv[]) {    int arr[] = {1, 4, 4, 5, 6, 6, 1, 2, 2, 3, 3, 4, 5};    int ret = merge(arr, sizeof(arr) / sizeof(arr[0]));        if (!ret) {        int i = 0;                for ( ; i < sizeof(arr) / sizeof(arr[0]); ++ i ) {            printf("%d ", arr[i]);        }        printf("\n");    }    return 0;}