[数据结构与算法]有两个顺序表LA和LB，其元素，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排序。

有两个顺序表LA和LB，其元素，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排序。

C语言版

解法一：

#include <stdio.h>

typedef struct {
    int *elem;
    int len
} SqList;

void MergeList(SqList *LA, SqList *LB, SqList *LC) {
    int i, j, n;
    for (i = LA->len - 1, j = LB->len - 1, n = i + j + 1; n >= 0;) {
        LC->elem[n--] = (LA->elem[i] > LB->elem[j]) ? LA->elem[i--] : LB->elem[j--];
        if (i == -1 || j == -1)
            LC->elem[n--] = (i == -1) ? LB->elem[j--] : LA->elem[i--];
    }
}

int main() {
    int a[] = {-1, 1, 2, 5,25}, b[] = {-3, 0, 2, 10,30,35}, c[11];
    SqList LA = {a, 5}, LB = {b, 6}, LC = {c, 11};
    MergeList2(&LA, &LB, &LC);
    for (int i = 0; i < 11; ++i) {
        printf("%d\t", LC.elem[i]);
    }
    return 0;
}

解法二：

#include <stdio.h>

typedef struct {
    int *elem;
    int len
} SqList;

void MergeList(SqList *LA, SqList *LB, SqList *LC) {
    int as = 0, bs = 0, s = 0, i, j;
    if (LA->len < LB->len) {
        SqList *temp = LA;
        LA = LB;
        LB = temp;
    }
    for (i = 0; i < LA->len; i++) {
        for (j = bs; j < LB->len; j++) {
            if (LA->elem[i] < LB->elem[j]) {
                LC->elem[s++] = LA->elem[i], as++;
                break;
            } else if (LA->elem[i] > LB->elem[j]) {
                LC->elem[s++] = LB->elem[j], bs++;
            } else {
                LC->elem[s++] = LA->elem[i], LC->elem[s++] = LB->elem[j];
                as++, bs++;
                break;
            }
        }
    }
    if (bs == LB->len)
        for (; as < LA->len; as++)
            LC->elem[s++] = LA->elem[as];
}


int main() {
    int a[] = {-1, 1, 2, 5,25}, b[] = {-3, 0, 2, 10,30,35}, c[11];
    SqList LA = {a, 5}, LB = {b, 6}, LC = {c, 11};
    MergeList2(&LA, &LB, &LC);
    for (int i = 0; i < 11; ++i) {
        printf("%d\t", LC.elem[i]);
    }
    return 0;
}

JavaScript语言版

对解法一进行修改：

	function mergeArray(arr1,arr2){
		let arr3=[], i, j, n;
        for (i = arr1.length - 1, j = arr2.length - 1, n = i + j + 1; n >= 0;) {
            if (arr1[i] > arr2[j]) arr3[n--] = arr1[i--];
            else arr3[n--] = arr2[j--];
            if (i == -1 || j == -1) {
                if (i == -1) arr3[n--] = arr2[j--];
                else arr3[n--] = arr1[i--];
            }
        }
        return arr3;
     }
     let arr1=[-1,1,2,6], arr2=[-3,0,2,10,12], arr3=mergeArray(arr1,arr2);
     console.log(arr3);

对解法二进行修改：

		function mergeArray(a, b) {
            let c = [], as = 0, bs = 0, s = 0
            if (a.length < b.length) [a, b] = [b, a]    // 交换数组
            for (let i = 0; i < a.length; i++) {
                for (let j = bs; j < b.length; j++) {
                    if (a[i] < b[j]) {
                        c[s++] = a[i]
                        as++
                        break
                    } else if (a[i] > b[j]) {
                        c[s++] = b[j]
                        bs++
                    } else {
                        c[s++] = a[i]
                        c[s++] = b[j]
                        as++
                        bs++
                        break
                    }
                }
            }
            if (bs == b.length)
                for (; as < a.length; as++) c[s++] = a[as]
            return c
        }
        let a = [-1, 1, 2, 5, 10, 12], b = [-3, 0, 2, 10, 12, 18, 20], c = mergeArray(a, b)
        console.log(c)

在此感谢大佬提供的解法一代码~~