为什么3种算法的平均时间为负值？

Question

我必须使用大小范围从10000到50000，步长为10000的数组，给所有三种算法提供相同的输入，并且对于每个输入重复执行100次，以纳秒为单位测量执行 （使用System.nanoTime（ ）），并以毫秒为单位报告平均时间。 这就是我在下面做的，但一些平均值是负值我不知道为什么？

import java.util.Arrays; 

public class Sort{ 

    public static void main(String[]args){ 

     double[] arr5 = new double[50000]; 

     for(int i=0;i<arr5.length;i++) 
     arr5[i] = Math.random(); 

     selectionSort(arr5,10000); 
     bubbleSort(arr5,10000); 
     quickSort(arr5,10000); 

     selectionSort(arr5,20000); 
     bubbleSort(arr5,20000); 
     quickSort(arr5,20000); 

     selectionSort(arr5,30000); 
     bubbleSort(arr5,30000); 
     quickSort(arr5,30000); 

     selectionSort(arr5,40000); 
     bubbleSort(arr5,40000); 
     quickSort(arr5,40000); 

     selectionSort(arr5,50000); 
     bubbleSort(arr5,50000); 
     quickSort(arr5,50000); 
    } 

    public static void selectionSort(double [] A,int n){ 
     int sum = 0; 
     System.out.println("Algorithm 1"); 
     for(int s=0;s<100;s++){ 
     long arr[] = new long[100]; 

     long startTime = System.nanoTime(); 

     for(int i=0;i<n-1;i++){ 
      int min = i; 
      for(int j=i+1;j<n;j++){ 
       if(A[j] < A[min]) 
        min=j;} 
      double tmp = A[i]; 
      A[i] = A[min]; 
      A[min]=tmp;} 

     long endTime = System.nanoTime(); 

     arr[s] = endTime - startTime; 
     //System.out.println(arr[s]); 
     sum+=arr[s]; 
     } 
     System.out.println("Average:" + ((sum/100)*Math.pow(10,-6))); 

    } 

    public static void bubbleSort(double A [],int n){ 
     int sum = 0; 
     System.out.println("\nAlgorithm 2"); 
     for(int s=0;s<100;s++){ 
     long[] arr = new long[100]; 

     long startTime = System.nanoTime(); 

     for(int i=0;i<n-1;i++){ 
      for(int j=0;j<n-1-i;j++){ 
       if(A[j]<A[j+1]){ 
        double tmp = A[j]; 
        A[j] = A[j+1]; 
        A[j+1] = tmp;}}} 

     long endTime = System.nanoTime(); 

     arr[s] = endTime - startTime; 
     //System.out.println(arr[s]); 
     sum+=arr[s]; 
     } 
     System.out.println("Average:" + ((sum/100)*Math.pow(10,-6))); 

    } 

//algorithm 3 
    public static void quickSort(double A [],int n){ 
     int sum = 0; 
     System.out.println("\nAlgorithm 3"); 
     long[] arr = new long[100]; 

     for(int i=0;i<100;i++){ 
     long startTime = System.nanoTime(); 

     Arrays.sort(A,0,n-1); 

     long endTime = System.nanoTime(); 

     arr[i] = endTime - startTime; 
     //System.out.println(arr[i]); 
     sum+=arr[i]; 
     } 
     System.out.println("Average:" + ((sum/100)*Math.pow(10,-6))); 

    } 

} 

Answer 1

用于您的计算变量sum是int类型。当您增加sum时，由于endTime - startTime的结果相当大，所以它会溢出。当出现sum的溢出时，它的值会回到最小值（负值）并继续再次增加。

修复：将sum的类型更改为long。因为他们没有在计算中使用，并与各回路被重置

另一个意见

你的阵列称为arr似乎是多余的。

例如，在您的bubbleSort()方法中。您在for循环内声明并初始化数组long[] arr = new long[100];：for(int s=0;s<100;s++)。

现在这个阵列arr的目前唯一目的是的endTime - startTime结果存储在索引s，然后将其用于增加sum（sum+=arr[s];）。

如果这是它的唯一目的，为什么不只是做sum += endTime - startTime并完全删除阵列？

如果你没有INFACT打算让这个阵列中的所有结果的轨迹，那么你应该将long[] arr = new long[100];外for环for(int s=0;s<100;s++)的，因为目前它重新声明，并在每次迭代初始化。

为了证明考虑这个小例子复制您在bubbleSort()在做什么，其他的方法：

for (int i = 0; i < 5; i++) { 
    int[] arr = new int[5]; 
    arr[i] = (i + 1); 
    System.out.println(Arrays.toString(arr)); 
} 

输出是：

[1, 0, 0, 0, 0] 
[0, 2, 0, 0, 0] 
[0, 0, 3, 0, 0] 
[0, 0, 0, 4, 0] 
[0, 0, 0, 0, 5] 

如果阵列之前，循环声明，那么行为会更有意义：

int[] arr = new int[5]; 
for (int i = 0; i < 5; i++) { 
    arr[i] = (i + 1); 
    System.out.println(Arrays.toString(arr)); 
} 

在这种情况下，输出是：

[1, 0, 0, 0, 0] 
[1, 2, 0, 0, 0] 
[1, 2, 3, 0, 0] 
[1, 2, 3, 4, 0] 
[1, 2, 3, 4, 5] 

打印您阵列arr到控制台中for循环的内容，你就会明白我的意思。