数据结构
网络
关系型数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究计算数组排序所需操作的 C++ 代码
假设我们有一个包含 n 个元素的数组 A（n 为奇数）。A 包含前 n 个自然数的排列。将有一个函数 f(i) 以 0 到 n-2 范围内的单个参数 i 作为自变量，并执行以下操作：如果 A[i] > A[i+1]，则交换 A[i] 和 A[i+1] 的值。我们必须计算首次让数组 A 排序所需的迭代次数。
因此，如果输入类似于 A = [4, 5, 7, 1, 3, 2, 6]，那么输出将为 5，因为数组在每次迭代后的状态依次是：[4, 5, 1, 7, 2, 3, 6]、[4, 1, 5, 2, 7, 3, 6]、[1, 4, 2, 5, 3, 7, 6]、[1, 2, 4, 3, 5, 6, 7]、[1, 2, 3, 4, 5, 6, 7]。
步骤
要解决此问题，我们将按照以下步骤进行 −
n := size of A f := 0 Ans := 0 for initialize Ans := 0, do: f := 0 for initialize j := 0, when j < n - 1, update (increase j by 1), do: if A[j] > A[j + 1], then: f := 1 if not f is non-zero, then: Come out from the loop for initialize j := (Ans AND 1), when j < n - 1, update j := j + 2, do: if A[j] > A[j + 1], then: swap A[j] and A[j + 1] (increase Ans by 1) return Ans
示例
让我们看看以下实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
bool f = 0;
int Ans = 0;
for (Ans = 0;;){
f = 0;
for (int j = 0; j < n - 1; j++)
if (A[j] > A[j + 1])
f = 1;
if (!f)
break;
for (int j = (Ans & 1); j < n - 1; j += 2)
if (A[j] > A[j + 1])
swap(A[j], A[j + 1]);
Ans++;
}
return Ans;
}
int main(){
vector<int> A = { 4, 5, 7, 1, 3, 2, 6 };
cout << solve(A) << endl;
}输入
{ 4, 5, 7, 1, 3, 2, 6 }输出
5
更新于：2022 年 3 月 15 日
261 次浏览
广告