统计一个排列中逆序对 的个数

根据分治法的设计思想和算法步骤,要求学生设计一个分治算法,用于解决一个排列中逆序对的个数的统计问题。归并排序的算法是一个分治算法。在分解的过程中,将一个序列分解成2个区间,每个区间长度是二分之一。在合并的过程中,依次判断待合并的两个小区间中元素的大小次序。符合正序的次序,不做任何处理。符合逆序的次序(即大元素排在了小元素之前),将两个元素调换次序。此时,既知道了一个具体的逆序对,也可以统计它的总数。所以,采用此方法可以完成任务