1

我正在尝试获取不同数组大小的各种排序方法的总经过时间。我能够获得 size = 100、1000、10000 和 100000 的经过时间，但是当我尝试 1000000 时，它只是继续运行而没有给出结果（我假设 1000000 太大了？）。有没有办法使用 nanoTime 来获取经过的时间，它会在合理的时间内编译？任何帮助都会很棒！

我的程序：

import java.util.Random;

public class Sorting {

public static void printArray(int[] array) {
    System.out.print("The Array: ");
    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
    System.out.println();
}

public static void exchange(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void selectionSort(int[] array) {
    for (int fill = 0; fill < array.length - 2; fill++) {
        int minPos = fill;
        for (int j = fill + 1; j < array.length; j++) {
            if (array[j] < array[minPos]) {
                minPos = j;
            }
        }
        exchange(array, fill, minPos);
    }
}

public static void bubbleSort(int[] array) {
    for(int last = array.length - 1; last > 0; last--){
        for(int i = 0; i < last; i ++){
            if(array[i + 1] < array[i]){
                exchange(array, i, i + 1);
            }
        }
    }
}


public static void main(String[] args) {
    int size = 1000000;
    Random rand = new Random();
    int[] arrayToSort = new int[size];
    for (int i = 0; i < size; i++) {
        arrayToSort[i] = rand.nextInt(size);
    }

    //printArray(arrayToSort);
    long startSelect = System.nanoTime();        
    selectionSort(arrayToSort);
    long estSelectTime = System.nanoTime() - startSelect;
    System.out.println("elapsed time after Selection sort for n = " + size + " : " + estSelectTime);
    //printArray(arrayToSort);
//        long startBubble = System.nanoTime();                
//        bubbleSort(arrayToSort);
//        long estBubTime = (System.nanoTime() - startBubble)/size;
//        System.out.println("elapsed time after Bubble sort for n = " + size + " : " + estBubTime);
    //printArray(arrayToSort);

}

}
4

2 回答 2

7

冒泡排序以二次时间运行，因此对于您添加的每个零，排序将花费 100 倍的时间。我猜你可以在一眨眼的时间内对 10,000 个数字进行排序，但 100,000 可能需要几秒钟，因此 1,000,000 至少需要几分钟。

于 2014-03-30T18:27:16.027 回答
0

如果我竞选

 100K =>   4.7 secs
 200K =>  18.5 secs
 500K => 116.7 secos
1000K => 4 mins (estimated)

注意：如果我像这样更改选择排序

public static void selectionSort(int[] array) {
    for (int fill = 0; fill < array.length - 2; fill++) {
        int minPos = fill;
        int minValue = array[minPos];
        for (int j = fill + 1; j < array.length; j++) {
            if (array[j] < minValue) {
                minPos = j;
                minValue = array[j];
            }
        }
        exchange(array, fill, minPos);
    }
}

200K 需要 14.6 秒而不是 18.5 秒。

于 2014-03-30T18:48:47.980 回答