java - 插入排序 - 计算反转次数

Question

我正在尝试计算给定数据集的反转次数。它对于小数据集效果很好，但是一旦我选择了几千个中的一个，反转值就会变成负值。我不明白这是怎么可能的，有人知道为什么会发生这种情况/可能的修复吗？

例如，给定 5 个数据集(-6、1、15、8、10)，反转值为 2。然而，对于更长的数据集，我得到 -2032112517 个反转。

    public static void main(String[] args) {
        Scanner userInput = new Scanner(System.in);
        System.out.println("Enter length of array: ");
        int input= userInput.nextInt();
        int[] values = new int[input];
        for (int i = 0; i < values.length; i++)
        {
            values[i] = userInput.nextInt();
        }
        insertionSort(values);

    }
    public static void insertionSort(int values[ ]) {
        int arrlen = values.length;
        int invert = 0;
        for (int i = 0; i < arrlen; i++) {
            int currentValue = values[i];
            int compare = i - 1;
            while (compare >= 0 && values[compare] > currentValue) {
                invert++;
                values[compare + 1] = values[compare];
                compare = compare - 1;
            }
            values[compare + 1] = currentValue;

        }
        System.out.println("INVERT IS: " +invert);

    }

}

Answer 1

Java中的最大int值是2147483647，很可能发生了溢出。尝试使用 long 代替。

如果您想了解更多信息，请在 Wikipedia 上搜索“整数溢出”。