百度笔试算法题一道。
一个数组a[0-n-1],a[0-mid]和a[mid+1-n-1]是各自升序的，现在要把a[0-n-1]排成有序的。要求空间复杂度o(1)，时间复杂度尽量低。
我想到的方法就是将后面序列的每个元素对前面序列进行插入排序。搜索插入位置的时候考虑从上一个插入元素位置之后开始搜索。
说明一下这个方法时间复杂度最坏应该是o(n^2)，网上有o(n)解法。
#include <stdlib.h>int insert(int* a, int begin, int end, int x){int pos = end;//插入位置 int last = a[end];int exchange = 0;int i;//寻找插入位置 for(i = begin; i <= end; i++){if(a[i] > x){pos = i;exchange = 1;break;}}if(exchange){//移动元素 for(i = end; i > pos; i--){a[i] = a[i-1];}a[end+1] = last;a[pos] = x;}else{pos = end+1;}return pos;}void print_r(int* a, int n){int i = 0;while(i<n){printf("%d\t",a[i++]);}printf("\n");}void merge(int* a, int n, int mid){int search_begin = 0;int i;for(i = mid; i < n; i++){search_begin = insert(a,search_begin, i, a[i+1]);}}int main(){int a[10] = {1,2,3,7,9,0,4,10,18,20};int mid = 4;merge(a,10,mid);print_r(a,10);return 0;}