Лучший оптимизированный способ - это решить с помощью сортировки слиянием, где при слиянии мы можем проверить, сколько инверсий требуется, сравнивая левый и правый массив. Когда элемент в левом массиве больше, чем элемент в правом массиве, это будет инверсия.
Подход сортировки слиянием: -
Вот код. Код точно такой же, как сортировка слиянием, за исключением фрагмента кода в методе mergeToParent, где я считаю инверсию при условии (left[leftunPicked] < right[rightunPicked])
public class TestInversionThruMergeSort {
static int count =0;
public static void main(String[] args) {
int[] arr = {6, 9, 1, 14, 8, 12, 3, 2};
partition(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
System.out.println("inversions are "+count);
}
public static void partition(int[] arr) {
if (arr.length > 1) {
int mid = (arr.length) / 2;
int[] left = null;
if (mid > 0) {
left = new int[mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
}
int[] right = new int[arr.length - left.length];
if ((arr.length - left.length) > 0) {
int j = 0;
for (int i = mid; i < arr.length; i++) {
right[j] = arr[i];
++j;
}
}
partition(left);
partition(right);
mergeToParent(left, right, arr);
}
}
public static void mergeToParent(int[] left, int[] right, int[] parent) {
int leftunPicked = 0;
int rightunPicked = 0;
int parentIndex = -1;
while (rightunPicked < right.length && leftunPicked < left.length) {
if (left[leftunPicked] < right[rightunPicked]) {
parent[++parentIndex] = left[leftunPicked];
++leftunPicked;
} else {
count = count + left.length-leftunPicked;
if ((rightunPicked < right.length)) {
parent[++parentIndex] = right[rightunPicked];
++rightunPicked;
}
}
}
while (leftunPicked < left.length) {
parent[++parentIndex] = left[leftunPicked];
++leftunPicked;
}
while (rightunPicked < right.length) {
parent[++parentIndex] = right[rightunPicked];
++rightunPicked;
}
}
}
Другой подход, в котором мы можем сравнить входной массив с отсортированным массивом: -
Это реализация Diablo ответа. Хотя это не должно быть предпочтительным подходом, так как удаление n элементов из массива или списка - это log (n ^ 2).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
public class TestInversion {
public static void main(String[] args) {
Integer [] arr1 = {6, 9, 1, 14, 8, 12, 3, 2};
List<Integer> arr = new ArrayList(Arrays.asList(arr1));
List<Integer> sortArr = new ArrayList<Integer>();
for(int i=0;i<arr.size();i++){
sortArr.add(arr.get(i));
}
Collections.sort(sortArr);
int inversion = 0;
Iterator<Integer> iter = arr.iterator();
while(iter.hasNext()){
Integer el = (Integer)iter.next();
int index = sortArr.indexOf(el);
if(index+1 > 1){
inversion = inversion + ((index+1)-1);
}
//iter.remove();
sortArr.remove(el);
}
System.out.println("Inversions are "+inversion);
}
}