アルゴリズムの集計秩序配列を誰もが書く(要求:元の配列を利用し,時間複雑度O(n)

タイトル:
配列Aの空間サイズはm+nであり、配列Aにはn個の昇順の整数要素が保存されている.配列Bには、m個の昇順の整数要素が保存されている.
配列Bを配列Aに挿入し、Aを秩序正しくし、時間的複雑さを最小限に抑えてください.
分析:
配列は秩序化されており,配列Aの空間は挿入された配列Bを格納するのにちょうど十分であるため,二つの配列が秩序化された特性を用いて,大きいものから小さいものまで順次取り出し,比較し,挿入することを構想した.
下付き変数index_a初期値はn−1であり、配列Aの最後の位置を表す.
下付き変数index_bはm−1に初期化され、配列Bの最後の位置を表す.
下付き変数indexはn+m-1に初期化され、挿入する位置を表します.
ルールの比較と挿入:
1.
B[index_b]>A[index_a]の場合、B[index_b]はA[index]に格納され、同時に下付きindex=index-1、index_b= index_b-1.
2.
B[index_b]3.
B[index_b]==A[index_a]の場合、A[index_a]はA[index_a]に、index=index-1、B[index_b]はA[index]に、下付きindex=index-1、index_a =  index_a  -1,index_b= index_b-1.
コード:
#include
using namespace std;
void MergeSortedArray(int a[], int b[], int n, int m)
{
    int indexA = n-1;
    int indexB = m-1;
    int index = n+m-1;
    
    while(indexB >= 0)
    {
        if(b[indexB] > a[indexA])
        {
            a[index] = b[indexB];
            indexB--;
            index--;
        }
        else if(b[indexB] < a[indexA])
        {
            a[index] = a[indexA];
            indexA--;
            index--;
        }
        else
        {
            a[index] = b[indexB];
            index--;
            a[index] = a[indexA];
            index--;
            indexA--;
            indexB--;
        }
    }
}
int main()
{
int arrayA[14] = {1,3, 4,5,7,9,10,12};
int arrayB[6] = {2,3,6,8,9,11};
        
    //int arrayA[14] = {1,2,3,4,5,6,7,8};
//int arrayB[6] = {9,10,11,12,13,14};
    //int arrayA[14] = {21,22,23,24,25,26,27,28};
//int arrayB[6] = {9,10,11,12,13,14};
    int n = 8;//numbers in array A
    int m = 6;//numbers in array B
    MergeSortedArray(arrayA, arrayB, n, m);
    for(int i =0; i
    {
        cout<
    }
    
    getchar();
}
注意:コンパイル環境は、特別な説明がない限りVisual Studio 2008です.C++11規格をサポートする
Visual Studio 2012.
オリジナル記事:
転載を歓迎します.出典を明記してください.ビジネス用途に使用する場合は、本人に連絡し、出典を明記してください.ありがとう!