一道百度算法笔试小题

昨天陪同学在北大，发现百度在笔试招实习生，现场笔试。顺道也霸笔了一把。有这样一道小题，一个数组a,????????????????????a[0,1....mid-1]是有序的,a[mid,.....num]也是有序的，现在要把这两部进行merge，如何在空间复杂度为0(1)的情况下进行合并，使得a整体有序。a[i]支持<运算。

?

下边是我的一个算法的实现:

?public static void main(String[] args) {??int a[]={2,3,6,10,23,39 ,1,4,5,7,8,9,100? };??test(a,6);?}??public static void test(int a[],int mid){??int tmp;??int p;??for(int i=0;i<mid;i++){???p=mid;???if(a[p]<a[i]){????tmp=a[i];????a[i]=a[p];????a[p]=tmp;????for(int j=mid+1;j<a.length;j++){?????if(a[j]<a[p]){??????tmp=a[j];??????a[j]=a[p];??????a[p]=tmp;??????p++;?????}else{??????break;?????}?????????}???}??}??for(int k=0;k<a.length;k++){???System.out.println(a[k]);??}?}

?

这里的tmp是所谓的 空间复杂度，仅仅用到了一个中间变量。思路是：仅仅需要遍历前半部分，同时去比较后半部分的第一个元素，在比较的过程中，如果出现了有较小的值，就去互换，同时让后半部分保持有序。效率可能不是最好的。这个题目算是比较基础的。?