2

在我的排序程序的 Java 代码中（它使用我的插入排序算法实现对 100000 个整数进行排序），我试图找出数组中的元素交换了多少次。我将其设置为静态变量，因为 sort() 方法是静态的。

但是，在程序运行期间的某个时候，我认为超出了整数限制，最终计数显示为负数。必须有办法纠正这个问题并得到正确的数字，但我无法弄清楚......你能帮忙吗？

public class InsertionSort {
    private static int exchcount=0;

    public static void exch(Comparable[] a, int i,int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    public static int exchangeCount(){
        return exchcount;
    }

    public static void sort(Comparable[] a){
    int N = a.length;       

    for(int i=0; i< N;i++){
        for(int j=i; j>0 && less(a[j],a[j-1]); j--){
        exch(a,j,j-1);
        exchcount++;

        }
       }
   }
...

    public static void main(String[] args) {
        Integer[] a = RandomNumberArrayGenerator.generate(100000);
        sort(a);
        System.out.println("number of exchanges="+ exchangeCount());
   }

这给

number of exchanges= -1799089211
4

4 回答 4

5

最简单的是将 counter 变成 along而不是int。这将使您最多可以数到 9,223,372,036,854,775,807。

如果每一个都exch()需要一个 CPU 周期，那么在 3GHz 的计算机上，long计数器溢出大约需要 100 年。

于 2013-06-29T12:06:20.817 回答
4

原始类型int是有符号的，32 位值，从 -2,147,483,648 到 2,147,483,647（含）。请参阅java 教程。

如果 end 之后的值是 -1799089211 ，这意味着当你exchanges达到 2,147,483,647 时，它会变为 -2,147,483,648，而不是 -2,147,483,647 等等......所以你(-2,147,483,648 + 1799089211 - 1)超出了原始类型的限制int。当然，这种情况假设你的计数器只溢出了一次，但它应该溢出不止一次。

对计数器使用long数据类型和（只是肯定的）测试溢出。

于 2013-06-29T12:06:52.680 回答
1

每次增加它时，您都可以检查它是否为负数，然后将溢出设置为 1。您还可以使用另一个整数来跟踪它。也许之后将其设置为 0。你有机会吗

exchcount++;

进入

    exchcount++;
    if (exchcount<0) {
      overflowcount++;
      exchcount=0;
   }

您也可以使用 long 代替，这将允许您的程序使用 64 位而不是 32 位。

这将需要你的机会

private static int exchcount=0;

进入

private static long exchcount=0;

这将允许您计入 2^63 而不是 2^31

于 2013-06-29T12:04:33.623 回答
0

使用long而不是int. 这是简单的答案。

于 2013-06-29T12:16:11.990 回答