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