爲什麼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循環的內容，你就會明白我的意思。