1

嗨，我用 JAVA 编写了一个冒泡排序应用程序。该应用程序正在充分工作并提供足够的输出，但它并没有给我平均时间的输出。

这是我的代码：

public class BubbleSort {
static double bestTime = 10000000, worstTime = 0;
public static void main(String[] args) {
    int BubArray[] = new int[]{**#interger values are placed in here#**};
         System.out.println("Unsorted List Before Bubble Sort");
         for(int a = 0; a < BubArray.length; a++){
         System.out.print(BubArray[a] + " ");
            }

        System.out.println("\n Bubble Sort Execution ...");

                    for(int i=0; i<10000;i++) {
                        bubbleSortTimeTaken(BubArray, i);
                        }

         int itrs = bubbleSort(BubArray);
    System.out.println("");               
    System.out.println("Array After Bubble Sort");
    System.out.println("Moves Taken for Sort : " + itrs + " Moves.");
    System.out.println("BestTime: " + bestTime + " WorstTime: " + worstTime);
    System.out.print("Sorted Array: \n");

        for(int a = 0; a < BubArray.length; a++){
                System.out.print(BubArray[a] + " ");
        }
}

private static int bubbleSort(int[] BubArray) {

int z = BubArray.length;
int temp = 0;

int itrs = 0;

for(int a = 0; a < z; a++){
        for(int x=1; x < (z-a); x++){

                if(BubArray[x-1] > BubArray[x]){

                        temp = BubArray[x-1];
                        BubArray[x-1] = BubArray[x];
                        BubArray[x] = temp;


                }    

                itrs++;
        }
}

return itrs;
}

public static void bubbleSortTimeTaken(int[] BubArray, int n) 
{
long startTime = System.nanoTime();
    bubbleSort(BubArray);   
    double timeTaken = (System.nanoTime() - startTime);
    if (timeTaken > 0)
    {
        worstTime = timeTaken;
    }
    else if (timeTaken < bestTime)
    {
        bestTime = timeTaken;
    }

    System.out.println(n + "," + timeTaken);

}
}

但我不确定如何 a) 获得每个的平均时间，以及如何在图表上绘制最佳、平均和最坏情况的结果。

这是一个示例输出：

Unsorted List Before Bubble Sort
#Integers Values of Unsorted List#

Bubble Sort Execution ... **#(execution number, time in nanoseconds)#**
0,6336584.0
1,5063668.0
2,3364580.0
3,3373289.0
4,3755912.0
5,3383866.0
....
9995,3431772.0
9996,3368312.0
9997,3743469.0
9998,4639362.0
9999,3433638.0

Moves Taken for Sort : 499500 Moves.
BestTime: 1.0E7 WorstTime: 3433638.0

此外，我不确定我的bubbleSortTimeTaken()函数是否正常工作，因为每次运行程序都会给出 1.0E7，无论使用的整数数量（100、1000、10000、100000、1000000）已经过测试。我希望找到要绘制的平均、最佳和最坏情况。

任何帮助将不胜感激，谢谢。

4

2 回答 2

1 
   if (timeTaken > 0)   // <- PROBLEM, Shouldn't be zero
    {
        worstTime = timeTaken;
    }
    else if (timeTaken < bestTime) //<- PROBLEM! , the 2 comparisons are unrelated
    {
        bestTime = timeTaken;
    }

在那里。如果timeTaken> 0（大部分情况下），else if则永远不会执行。
因此，bestTime永远不会更新，并保留原始值 (1E7)。

要解决此问题，应将函数修改为如下所示：

public static void bubbleSortTimeTaken(int[] BubArray, int n) 
{
long startTime = System.nanoTime();
    bubbleSort(BubArray);   
    double timeTaken = (System.nanoTime() - startTime);
    if (timeTaken > worstTime)
    {
        worstTime = timeTaken;
    }
    if (timeTaken < bestTime)
    {
        bestTime = timeTaken;
    }

    System.out.println(n + "," + timeTaken);

}
}

请注意，我也添加了一个可能的修复worstTime。

于 2012-12-09T18:22:04.183 回答
1 
 if (timeTaken > 0)
{
    worstTime = timeTaken;
}

这应该是

 if (timeTaken > worstTime)
{
    worstTime = timeTaken;
}

否则你将无法正确设置它。这就解释了为什么你的 bestTime 总是 10e7。

要找到平均值，只需执行一定次数，记录所有时间，然后将它们相加并除以完成的次数。

于 2012-12-09T18:22:07.547 回答