问题描述:
设子数组a[0:k]和a[k+1:n-1]已排好序（0<=k<=n-1).试设计一个合并这两个子数组为排好序的数组a[0:n-1]的算法．要求算法在最坏的情况下所用的计算时间为O(n), 且只用到O(1)的辅助空间．
这一题比较简单,看代码就知道了.
#include?<stdio.h>
void?DisplayArray(int?*pArray,?int?nLen)
{
????for?(int?i?=?0;?i?<?nLen;?++i)
????{
????????printf("array[%d]?=?%d\n",?i,?pArray[i]);
????}
}
//?pArray1和pArray2是已经排好序的数组,要求将它们按照顺序合并到pArray中
//?排序之后的数组不会有重复的元素
void?MergeArray(int?*pArray1,?int?nLen1,?int?*pArray2,?int?nLen2,?int?*pArray)
{
????int?i,?j,?n;
????i?=?j?=?n?=?0;
????while?(i?<?nLen1?&&?j?<?nLen2)??????????????????//?循环一直进行到拷贝完某一个数组的元素为止
????{
????????if?(pArray1[i]?<?pArray2[j])????????????????//?拷贝array1的元素
????????{
????????????pArray[n++]?=?pArray1[i++];
????????}
????????else?if?(pArray1[i]?>?pArray2[j])????????????//?拷贝array2的元素
????????{
????????????pArray[n++]?=?pArray2[j++];???????????????????????
????????}
????????else??????????????????????????????????????????//?相等的元素拷贝
????????{
????????????pArray[n++]?=?pArray2[j++];???????????????????????
????????????++i;
????????}
????}
????if?(i?==?nLen1)??????????????????????????????//?如果array1已经被拷贝完毕就拷贝array2的元素
????{
????????while?(j?<?nLen2)
????????????pArray[n++]?=?pArray2[j++];
????}
????else?????????????????????????????????????????//?如果array2已经被拷贝完毕就拷贝array1的元素
????{
????????while?(i?<?nLen1)
????????????pArray[n++]?=?pArray1[i++];
????}
}
int?main()
{???????
????int?array1[]?=?{1,?4,?5,?7};
????int?array2[]?=?{2,?3,?6,?8};
????int?array3[8];
????MergeArray(array1,?4,?array2,?4,?array3);
????printf("Merge?Array:\n");
????DisplayArray(array3,?8);
????return?1;
}
|