1 题目

设m+n个元素顺序存放在数组A[1…m+n]中，前m个元素递增有序，后n个元素递增有序，试设计一个在时间和空间两方面都尽可能高效的算法，使得整个顺序表递增有序。

2 思路

2.1 思路1（直接插入法）

把数组A看作是两个长度分别为m和n的有序表L1、L2，把L2的每个元素依次插入到L1中的合适位置即可。

• 1，取表L2中第一个元素A[m+1]，暂存为tmp，把tmp插入到L1中合适的位置（L[i]<tmp<L1[i+1]）；
• 2，重复操作1，把A[m+2]、A[m+3]…A[m+n]依次插入到L1中，直至整个数组有序。

时间复杂度：O(mn)
空间复杂度：O（1）

2.2 思路2（归并）

• 1，把数组A前m个元素和后n个元素视为两个归并段L1、L2，增加一个辅助数组B[1…m+n]存储临时归并的结果。设k1、k2、k3分别指向L1，L2的首位和数组B的下一个结果位置。
• 2，当k1<=m并且k2<=m+n时，执行3，否则执行4:
• • 3，比较两个归并段指针所指元素的大小，若A[k1]<A[k2]，那么B[k3++]=A[k1++]，否则B[k3++]=A[k2++]，执行2；
• • 4，若k1>m，则把第二归并段剩余的元素复制到数组B末尾；若k2>m+n,则把第一个归并段剩余的元素复制到数组B，最后把数组B复制到数组A。

时间复杂度：O(m+n)
空间复杂度：O(m+n)

3 实现

3.1 思路1

#include<cstdio>void solution1(int *A, int m, int n){int tmp, j;for(int i = m+1; i <= m+n;i++){tmp = A[i];//暂存元素，防止后面移动元素时，元素丢失for(j = i-1;j > 0 && A[j] > tmp;j--)//当L1中的元素大于tmp时，就是插入tmp的位置A[j+1] = A[j];A[j+1] = tmp;}
}void print(int* A, int n){for(int i = 0;i < n;i++){printf("%d ", A[i]);}printf("\n");
}int main(){int A[] = {0, 1,4,7,2,3,6};solution(A, 3, 3);print(A, sizeof(A)/sizeof(A[0]));return 0;
}

3.2 思路2

#include<cstdio>void solution2(int *A, int m, int n){int B[m+n+1];int k1 = 1, k2 = m+1, k3 = 1;//三个指针while(k1<=m && k2<= m+ n){//归并，把较小的元素复制到B中if(A[k1] < A[k2]) B[k3++] = A[k1++];else B[k3++] = A[k2++];}if(k1 > m) //把没有比较完的归并段的剩余元素复制到B中while(k2 <= m+n) B[k3++] = A[k2++];if(k2 > m+n)while(k1 <= m) B[k3++] = A[k1++];for(int i = 1;i <= m+n;i++){//把数组B复制到数组A中A[i] = B[i];}
} void print(int* A, int n){for(int i = 0;i < n;i++){printf("%d ", A[i]);}printf("\n");
}int main(){int A[] = {0, 1,4,7,2,3,6};solution2(A, 3, 3);print(A, sizeof(A)/sizeof(A[0]));return 0;
}