1

我编写了一个冒泡排序程序，将 10000 个唯一值按顺序排序。

我已经运行了这个程序，它给了我一个时间输出（使用 nanoTime）来表示程序完成所需的时间，但我希望在程序代码中添加另一个输出；程序从开始到结束需要多少次排序。

这是代码：

public class BubbleSort {
public static void main(String[] args) {
    int BubArray[] = new int[]{#here are 10000 integers#};
    System.out.println("Array Before Bubble Sort");
        for(int a = 0; a < BubArray.length; a++){
             System.out.print(BubArray[a] + " ");
        }

         double timeTaken = bubbleSortTimeTaken(BubArray);
            bubbleSort(BubArray);
            System.out.println("");               
            System.out.println("Array After Bubble Sort");
    System.out.println("    Time taken for Sort : " + timeTaken + " milliseconds.");                
            for(int a = 0; a < BubArray.length; a++){
                    System.out.print(BubArray[a] + " ");
        }
}

private static void bubbleSort(int[] BubArray) {

        int z = BubArray.length;
        int temp = 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;

                        }      
                }
        }
}
public static double bubbleSortTimeTaken(int[] BubArray) {
long startTime = System.nanoTime();
    bubbleSort(BubArray);
long timeTaken = System.nanoTime() - startTime;
return timeTaken;
}
}

代码执行并输出我想要的方式：

Array Before Bubble Sort
13981 6793 2662 10986 733 10107 2850 ... 
Array After Bubble Sort
10 11 17 24 35 53 57 60 61 78 83 89 128 131 138 141 ....
Time taken for Sort : 1.6788472E7 milliseconds.

但我希望在代码中添加另一个输出，它告诉我完成多少次移动（基本上是一个移动计数器），即：

Time taken for Sort : 1.6788472E7 milliseconds.
Total number of moves: 3000

这有意义吗？任何帮助将不胜感激，谢谢。

4

2 回答 2

1

试试这个：

// returns the number of switches
private int bubbleSort(int[] BubArray) {

        int z = BubArray.length;
        int temp = 0;
        int timesSwitched = 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;
                                timesSwitched++
                        }      
                }
        }
     return timesSwitched;
}
于 2012-12-06T21:55:59.540 回答
1

我会更改bubbleSort为返回一个 int 并将您的时间复杂度分配给它。

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;

}

然后在main：

int itrs = bubbleSort(BubArray);
            System.out.println("");               
            System.out.println("Array After Bubble Sort");
    System.out.println("    Time taken for Sort : " + timeTaken + " milliseconds.");  
    System.out.println("Time complexity: " + itrs);
于 2012-12-06T22:00:51.117 回答