|
|
問題描述: 設子數組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;
}
|