题解 | #排序次数#

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] nums = new int[N];
        //利用hashMap存储所有元素原来的位置
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<N; i++){
            nums[i] = scanner.nextInt();
            map.put(nums[i], i);
        }
        //重新排序
        Arrays.sort(nums);
        //计数器
        int res =0;
        //遍历排序好的元素,此时可以这么理解: 
        //我们在不断的抽出第一小的数据,第二小的数据.... 
        //将每次得到的数据与它的后面一个进行比较,比较什么呢?  比较它们原来在数组中的位置,如果发生了颠倒,则说明更大的那个数字发生了一次替换,
        //此时计数器加一,并且更重要的是,i+1的hash值也要变,变为一个比所有value都大的值,示意它现在是新的末尾
        //也就是说,其实这个hashMap是一个动态的过程,我们在不断的维护他
        for(int i=0; i<nums.length-1; i++){
            if(map.get(nums[i]) > map.get(nums[i+1])){
                map.put(nums[i+1], N++);
                res++;
            }
        }
        System.out.println(res);
    }
}