以c++语言写个代码:给出序列A和序列B,判断序列B是否序列A经过m趟插入排序后得到的非降序结果。是的话,给出序列A第m+1趟插入排序的结果。不是的话,给出序列A第m趟插入排序的结果
时间: 2024-03-19 18:46:23 浏览: 55
用C++实现插入排序的算法
好的,以下是一个C++的代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
bool is_sorted_after_m_insertion_sorts(vector<int>& A, vector<int>& B, int m) {
// 判断序列B是否是序列A经过m趟插入排序后得到的非降序结果
for (int i = 0; i < m; i++) {
// 执行一次插入排序
int j = i;
while (j > 0 && A[j-1] > A[j]) {
swap(A[j-1], A[j]);
j--;
}
}
return A == B;
}
vector<int> get_m_plus_one_insertion_sort(vector<int>& A, int m) {
// 获取序列A经过m+1趟插入排序后的结果
int n = A.size();
for (int i = 0; i <= m; i++) {
int j = i;
while (j > 0 && A[j-1] > A[j]) {
swap(A[j-1], A[j]);
j--;
}
}
return A;
}
vector<int> get_m_insertion_sort(vector<int>& A, int m) {
// 获取序列A经过m趟插入排序后的结果
int n = A.size();
for (int i = 0; i < m; i++) {
int j = i;
while (j > 0 && A[j-1] > A[j]) {
swap(A[j-1], A[j]);
j--;
}
}
return A;
}
int main() {
vector<int> A = {3, 1, 4, 2};
vector<int> B = {1, 2, 3, 4};
int m = 2;
if (is_sorted_after_m_insertion_sorts(A, B, m)) {
// 序列B是序列A经过m趟插入排序后得到的非降序结果
vector<int> C = get_m_plus_one_insertion_sort(A, m);
cout << "序列A第" << m+1 << "趟插入排序的结果为:";
for (int i = 0; i < C.size(); i++) {
cout << C[i] << " ";
}
cout << endl;
} else {
// 序列B不是序列A经过m趟插入排序后得到的非降序结果
vector<int> C = get_m_insertion_sort(A, m);
cout << "序列A第" << m << "趟插入排序的结果为:";
for (int i = 0; i < C.size(); i++) {
cout << C[i] << " ";
}
cout << endl;
}
return 0;
}
```
其中,`is_sorted_after_m_insertion_sorts(A, B, m)`函数用于判断序列B是否是序列A经过m趟插入排序后得到的非降序结果。`get_m_plus_one_insertion_sort(A, m)`函数用于获取序列A经过m+1趟插入排序后的结果。`get_m_insertion_sort(A, m)`函数用于获取序列A经过m趟插入排序后的结果。
希望这个代码示例能够帮助到你。
阅读全文