排序

题目难度：简单

知识点：数学逻辑，数组

解题思路：将数组按照从小到大的顺序排序，新旧数组中数值不相同的的总位置数即为题中需要移动的个元素的个数。

方法一

首先创建一个新的数组，使用不断循环的方式将旧数组中的值赋给新的数组，完成数组的复制。然后对新数组进行排序，最后对比两个数组在同一位置处的数值是否相同，统计数值不同的数量。

import java.util.*;
public class Main{
    public static void main (String args[]){
        Scanner in =new Scanner(System.in);
        while (in.hasNext()){
            int n=in.nextInt();
            int x[]=new int[n];
            for (int i=0;i<n;i++){
                x[i]=in.nextInt();
            }
            //创建新的数组用于复制原数组
            int temp[]=new int[n];
            for (int i=0;i<n;i++ ){
                temp[i]=x[i];
            }
            //对新数组进行排序
            Arrays.sort(temp);
            //统计两个数组中相同位置不同元素的个数
            int count=0;
            for (int i=0;i<n;i++ ){
                if (temp[i]!=x[i]){
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

方法二

首先采用clone函数对数组进行复制。然后与方法一相同，对新数组进行排序，最后对比两个数组在同一位置处的数值是否相同，统计数值不同的数量。

import java.util.*;
public class Main{
    public static void main (String args[]){
        Scanner in =new Scanner(System.in);
        while (in.hasNext()){
            int n=in.nextInt();
            int x[]=new int[n];
            for (int i=0;i<n;i++){
                x[i]=in.nextInt();
            }
            //复制原数组
            int y[] = new int[n];
            y = x.clone();
            //对新数组进行排序
            Arrays.sort(y);
            //统计两个数组中相同位置不同元素的个数
            int sum = 0;
            for (int i=0;i<n;i++){
                if (x[i] != y[i])
                    sum++;
            }
            System.out.println(sum);
        }
    }
}