How to reduce number of move operations in an array?
The example in the question

The minimum number of moves needed for the example in the question, from [0, 1, 2, 3, 4, 5] to [2, 1, 4, 0, 5, 3] is 3.

            // [0, 1, 2, 3, 4, 5], where 2, 4, 5 are good.
move(2, 1); // [0, 2, 1, 3, 4, 5], where 2, 1, 4, 5 are good.
move(0, 4); // [2, 1, 3, 4, 0, 5], where 2, 1, 4, 0, 5 are good.
move(2, 5); // [2, 1, 4, 0, 5, 3], where 2, 1, 4, 0, 5, 3 are good.


The idea is to split the target array into two subsequences, 2, 4, 5 and 1, 0, 3 where the first subsequence is the longest increasing subsequence. Keeping the order of elements in the first subsequence, we will move the remaining elements  from left to right to their expected positions respectively, i.e, first moving 1 to its expected positions and so on.

An algorithm

Input: Array $A = [0, 1, 2, ..., n-1]$ and array $B[0], B[1], ..., B[n-1]$ which is a permutation of $0, 1, 2, ..., n-1$.

Output: A list of minimum size each of whose elements is an operation of the form move(fromIndex, toIndex) such that after performing that list of operations on $A$, $A$ becomes $B$.

Procedure: $B$ is intact while $A$ will be changed move by move.


Let $B[s_1], B[s_2], \cdots, B[s_m]$ be the longest increasing subsequence of $B$. This can be done as described in this Wikipedia article. It can also be done as described in this Wikipedia article since the longest increasing subsequence of $B$ is the longest common subsequence of $A$ and $B$.  Let $s_{-1}=-1$ and $s_{m+1}=n$. 
Let $O$ be an empty list of operations. For $i$ from -1 to $m$ inclusive do:


For $j$ from $1$ inclusive to $s_{i+1} - s_i $ exclusive do:


Find $x$, the index of $B[s_i]$ in $A$. If $i=-1$, let $x=0$.
find $y$, the index of $B[s_j + j]$ in $A$.
Move $A[y]$ to the $j$-th place after the place of $A[x]$.
Add $\text{move}(y, x + j)$ to $O$.


Now all numbers in $B$ up to index $s_{i+1}$ are good, i.e., sorted in the same order in $A$ and in $B$, although the same number might be at different indices in $A$ and in $B$.



Correctness

It is clear that at the end of the algorithm, all numbers in $A$ are sorted in the same order in $B$ and in $B$, i.e., $A$ is $B$. The total number of moves in the algorithm is $$(s_0-s_{-1}-1) + (s_1-s_{0}-1)+\cdots + (s_{m+1}-s_{m}-1) = s_{m+1}-s_0-(m+1)=n.$$

On the other hands, each move(fromIndex, toIndex) in any algorithm can increase the common longest subsequence between $A$ and $B$ by at most 1. So $n-m$ moves are needed.

This is pointed out by xskxzr first.

Complexity

It takes $O(n\log n)$ or $O(n^2)$ to find the longest increasing subsequence. Finding the index of a number in $A$ is performed about $2n$ times, which costs $O(n^2)$ in total. It takes $O(n^2)$ to perform all $n$ moves. So the algorithm runs in $O(n^2)$ time.

The implementation of finding the index of a number can be sped up so that the algorithm can be implemented to run in $O(n\log n)$ time.

Exercises

Exercise 1. (One minute or two) Array $A$ is a permutation of $0, 1, \cdots, n-1$. State an algorithm that find a list of operations of the form move(fromIndex, toIndex) such that will sort $A$ in minimum steps.

Exercise 2. The same input is given. Find an algorithm that computes the minimum number of moves needed to change $A$ so that it ends up the same as $B$ up to a cyclic shift. For example, when $B=[2, 1, 4, 5, 0, 3]$, $A$ should be changed to one of $[2, 1, 4, 5, 0, 3]$, $[1, 4, 5, 0, 3, 2]$, $[4, 5, 0, 3, 2, 1]$, $[5, 0, 3, 2, 1, 4]$, $[0, 3, 2, 1, 4, 5]$ and $[3, 2, 1, 4, 5, 0].$