|
|
問(wèn)題描述: 設(shè)子數(shù)組a[0:k]和a[k+1:n-1]已排好序（0<=k<=n-1).試設(shè)計(jì)一個(gè)合并這兩個(gè)子數(shù)組為排好序的數(shù)組a[0:n-1]的算法．要求算法在最壞的情況下所用的計(jì)算時(shí)間為O(n), 且只用到O(1)的輔助空間．
這一題比較簡(jiǎn)單,看代碼就知道了.
 #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是已經(jīng)排好序的數(shù)組,要求將它們按照順序合并到pArray中
//?排序之后的數(shù)組不會(huì)有重復(fù)的元素
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)??????????????????//?循環(huán)一直進(jìn)行到拷貝完某一個(gè)數(shù)組的元素為止
????{
????????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已經(jīng)被拷貝完畢就拷貝array2的元素
????{
????????while?(j?<?nLen2)
????????????pArray[n++]?=?pArray2[j++];
????}
????else?????????????????????????????????????????//?如果array2已經(jīng)被拷貝完畢就拷貝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;
}
|