时间戳

首页 > 解决方案 > 插入排序 - 计算反转次数

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

问题描述

我正在尝试计算给定数据集的反转次数。它适用于小型数据集，但是一旦我选择了几千个中的一个，反转值就会变成负数。我看不出这是怎么可能的，有谁知道为什么会发生这种情况/可能的修复？

例如，给定一个 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);

    }

}

标签： javaarraysinsertion-sort

解决方案

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

如果您想了解更多信息，请在 Wikipedia 上搜索 Integer overflow。

推荐阅读