【数据结构与算法】原地合并递增递减顺序表为单一递增顺序表的算法 C++实现（归并排序+顺序表）

设顺序表A有n+m个元素，前n个元素递增有序，后m个元素递减有序。设计一个算法，把这两部分合并成一个全部递增有序的顺序表，并分析算法的时间复杂度，要求空间复杂度为O(1)。

思路

首先，定义一个顺序表结构体SqList，包含元素指针elem，元素个数length，以及列表大小listSize。

然后，定义一个初始化顺序表的函数initList，该函数为顺序表分配内存，并设置元素个数为0，列表大小为m。如果内存分配失败，则退出程序。

接下来，定义一个反转顺序表的函数reverse，该函数将顺序表的前n个元素和后m个元素进行反转。

之后，定义一个合并顺序表的函数merge，该函数将反转后的顺序表进行合并排序。具体实现是通过两个指针i和j，分别指向顺序表的第n个元素和第n+1个元素，如果i指向的元素大于j指向的元素，则交换这两个元素，并向后检查，如果存在逆序对，则继续交换，直到没有逆序对为止。

最后，定义main函数，首先定义一个包含n+m个元素的数组A，前n个元素递增有序，后m个元素递减有序。然后初始化一个顺序表L，并将数组A的元素复制到顺序表L。然后反转顺序表L的后m个元素，最后调用merge函数，将顺序表L合并为一个全部递增有序的顺序表。

这个算法的时间复杂度是$O((n+m{)}^2)$，因为在最坏的情况下，每次交换都可能需要扫描整个顺序表。空间复杂度是$O(1)$，因为除了输入的顺序表外，没有使用额外的空间。

代码

#include <algorithm> #include <iostream> #define AUTHOR "HEX9CF" using namespace std; using Status = int; using ElemType = int;  const int TRUE = 1; const int FALSE = 0; const int OK = 1; const int ERROR = 0; const int INFEASIBLE = -1; const int OVERFLOW = -2;  struct SqList { 	ElemType *elem; 	int length; 	int listSize; };  void print(SqList &L) { 	for (int i = 0; i < L.length; i++) { 		cout << L.elem[i] << " "; 	} 	cout << "\n"; }  Status initList(SqList &L, int m) { 	L.elem = (ElemType *)malloc(m * sizeof(ElemType)); 	if (!L.elem) { 		exit(OVERFLOW); 	} 	L.length = 0; 	L.listSize = m; 	return OK; }  Status reverse(SqList &L, int n, int m) { 	int i = n; 	int j = n + m - 1; 	while (i < j) { 		swap(L.elem[i], L.elem[j]); 		i++; 		j--; 	} }  Status merge(SqList &L, int n, int m) { 	int l = 0; 	int r = n + m - 1; 	int i = n - 1; 	int j = n; 	while (1) { 		// cout << i << " " << j << endl; 		if (L.elem[i] > L.elem[j]) { 			swap(L.elem[i], L.elem[j]); 			int k = j + 1; 			while (k <= r) { 				if (L.elem[k - 1] > L.elem[k]) { 					swap(L.elem[k - 1], L.elem[k]); 					k++; 				} else { 					break; 				} 			} 			k = i - 1; 			while (l <= k) { 				if (L.elem[k + 1] < L.elem[k]) { 					swap(L.elem[k + 1], L.elem[k]); 					k--; 				} else { 					break; 				} 			} 			if (k == i - 1) { 				break; 			} 		} 		// print(L); 	} 	return OK; }  int main() { 	int A[] = {1, 3, 5, 7, 9, 12, 10, 8, 6, 4, 2}; 	int n = 6; 	int m = 5;  	SqList L; 	initList(L, n + m);  	for (int i = 0; i < n + m; i++) { 		L.elem[i] = A[i]; 		L.length++; 	}  	print(L); 	reverse(L, n, m); 	// print(L); 	merge(L, n, m); 	print(L); 	return 0; }