C說話完成在數組A上有序歸並數組B的辦法

C說話完成在數組A上有序歸並數組B的辦法。本站提示廣大學習愛好者：（C說話完成在數組A上有序歸並數組B的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話完成在數組A上有序歸並數組B的辦法正文

本文實例講述了C說話完成在數組A上有序歸並數組B的辦法，分享給年夜家供年夜家參考。詳細剖析以下：

標題：數組A和數組B均有序，數組A有足夠年夜內存來包容數組B，將數組B有序歸並到數組A中

剖析：假如由前至後歸並，龐雜度將會是O(N2)，如許的龐雜度明顯不是最優解，應用兩個指針指向兩個數組的尾部，從後往前遍歷，如許的龐雜度為O(n2)

由此可以寫出上面的代碼：

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int arrayA[10] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};
const int sizeB = sizeof arrayB / sizeof *arrayB;
const int sizeA = sizeof arrayA / sizeof *arrayA - sizeB;

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = sizeB - 1;

 while (posA >= 0 && posB >= 0)
 {
 if (arrayA[posA] < arrayB[posB])
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 else
 {
  arrayA[posA + posB + 1] = arrayA[posA];
  posA--;
 }
 copy(arrayA, arrayA + 10, ostream_iterator<int>(cout, " "));
 system("pause");
 }

 return arrayA;
}

void main()
{
 int *result = mergeArray(arrayA, sizeA, arrayB, sizeB);

 copy(result, result + 10, ostream_iterator<int>(cout, " "));
 cout << endl;
}

代碼寫完後仿佛完成了所需功效，但還不止於此，必需對上述代碼做UT

1. 硬朗性

arrayA或arrayB為空，長度小於0

2. 界限用例

arrayA為空，長度為1；arrayB不為空，長度年夜於1
首元素用例
const int size = 6;
int arrayA[size] = {2};
int arrayB[] = {0, 1, 1, 1, 1};
反之
const int size = 6;
int arrayA[size] = {0, 1, 1, 1, 1};
int arrayB[] = {2};

3. 正經常使用例：

const int size = 10;
int arrayA[size] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};

const int size = 10;
int arrayA[size] = {2, 4, 6, 8, 10};
int arrayB[] = {1, 3, 5, 7, 9};

const int size = 10;
int arrayA[size] = {1, 2, 3, 4, 5};
int arrayB[] = {6, 7, 8, 9, 10};

const int size = 10;
int arrayA[size] = {6, 7, 8, 9, 10};
int arrayB[] = {1, 2, 3, 4, 5};

經由下面的測試，不難發明在界限前提用例中，代碼曾經不克不及准確運轉出成果，在測試用例的驅動下，不難寫出准確代碼以下：

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = sizeB - 1;

 while (posA >= 0 && posB >= 0)
 {
 if (arrayA[posA] < arrayB[posB])
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 else
 {
  arrayA[posA + posB + 1] = arrayA[posA];
  posA--;
 }
 copy(arrayA, arrayA + size, ostream_iterator<int>(cout, " "));
 system("pause");
 }

 //湧現兩種情況：
 //1. posA < 0 && posB >= 0
 //2. posA >= 0 && posB < 0
 //只要第1種情況須要停止處置
 if (posA < 0 && posB >= 0)
 {
 while (posB >= 0)
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 } 
 return arrayA;
}

信任本文所述對年夜家C法式算法設計的進修有必定的自創價值。