计算在 C++ 中对数组进行排序的“前移”移动的最小次数

我们得到了一个介于 1 到 n 之间的数字数组。这里的目标是找到不。对给定数组进行排序所需的“移到前面”操作。数组没有重复。'move to front' 操作选取一个元素并放置在第一个位置，这里是索引 0。

我们将从末尾遍历数组，如果元素位于正确的位置，则不需要移动其他移动。对于从 1 到 n 的元素，元素 arr[i] 数组中的正确位置应位于索引 i+1。arr[0] 应该是 1，arr[1] 应该是 2 并且…….arr[n-1] 应该是 n。

输入

Arr[]= { 4,3,2,1 }

输出结果

Minimum move-to-front operations: 3

解释

Pull 3, 3,4,2,1 count=1
Pull 2, 2,3,4,1 count=2
Pull 1, 1,2,3,4 count=3

输入

Arr[]= { 6,1,2,5,4,3 }

输出结果

Minimum move-to-front operations: 5

解释

Pull 5, 5,6,1,2,4,3 count=1
Pull 4, 4,5,6,1,2,3 count=2
Pull 3, ,4,5,6,1,2 count=3
Pull 2, 2,3,4,5,6,1 count=4
Pull 1, 1,2,3,4,5,6 count=5

下面程序中使用的方法如下

• 整数数组 Arr[] 存储数字 1 到 n。

• 整数变量大小存储数组 Arr[] 的长度

• 函数 movetoFront(int arr[], int n) 接受一个数组及其长度作为输入，并返回对给定数组进行排序所需的最小“移动到前端”操作数。

• 计数变量用数组的大小初始化，因为在降序数组的情况下可以移动所有元素。

• 从最后一个索引开始遍历并向前移动，如果元素值与 count 相同，（对于 1 到 n 之间的排序元素，n 是最后一个，n-1 是倒数第二个，依此类推）然后将 count 作为该元素递减是在正确的位置。

• 这样在循环结束时，count就有了想要的结果。

示例

#include <bits/stdc++.h>
using namespace std;
// 计算排列阵列的最小移动次数
// 以递增的顺序。
int movetoFront(int arr[], int n){
   //计算所有元素都正确放置
   int count = n;
   // 从末尾遍历数组
   for (int i=n-1; i >= 0; i--){
      // 如果当前项目在其正确位置，
         //减少计数
      //范围是 1 到 n 所以每个 arr[i] 应该有值 i+1
      //1 在 0 索引，2 在 1 索引........
      if (arr[i] == count)
         count--;
   }
   return count;
}
int main(){
   int Arr[] = {5, 3, 4, 7, 2, 6, 1};
   int size = 7;
   cout <<"Minimum 'move-to-front' to sort array:"<< movetoFront(Arr, size);
   return 0;
}

输出结果

Minimum 'move-to-front' to sort array:6