-1

这是一个非常简单直接的问题，但是，当然，我已经设法做错了。首先，我生成了 5 个包含 10 个随机数的不同数组——从 1 到 10、1 到 100、最多 1 到 100,000。然后我对每个数组执行 5 种不同类型的排序（总共 25 种），计算执行排序所需的时间。无论 n 的大小如何，我都无法弄清楚为什么每个结果都是 0ms。我究竟做错了什么？

public class Lab16Sorting {

public static void main(String[] args) 
{
    final int TOTAL_NUMBERS = 10;
    int count;
    int[] num = new int[TOTAL_NUMBERS];
    Random rand = new Random();

    // Generate 10 numbers from 1 - 10  
    System.out.println("SORT 10");
    System.out.println("----------------");

    for (count = 0; count < TOTAL_NUMBERS; count++)
        num[count] = rand.nextInt(10);

    System.out.println("Array: " + num);
    runSort(num);

    // Generate 10 numbers from 1 - 100     
    System.out.println("\nSORT 100");
    System.out.println("----------------");

    for (count = 0; count < TOTAL_NUMBERS; count++)
        num[count] = rand.nextInt(100);

    System.out.println("Array: " + num);
    runSort(num);

    // Generate 10 numbers from 1 - 1,000       
    System.out.println("\nSORT 1,000");
    System.out.println("----------------");

    for (count = 0; count < TOTAL_NUMBERS; count++)
        num[count] = rand.nextInt(1000);

    System.out.println("Array: " + num);
    runSort(num);

    // Generate 10 numbers from 1 - 10,000  
    System.out.println("\nSORT 10,000");
    System.out.println("----------------");

    for (count = 0; count < TOTAL_NUMBERS; count++)
        num[count] = rand.nextInt(10000);

    System.out.println("Array: " + num);
    runSort(num);

    // Generate 10 numbers from 1 - 100,000     
    System.out.println("\nSORT 100,000");
    System.out.println("----------------");

    for (count = 0; count < TOTAL_NUMBERS; count++)
        num[count] = rand.nextInt(100000);

    System.out.println("Array: " + num);
    runSort(num);
}

/**
 * Run sort algorithms
 */

private static void runSort(int[] num)
{
    long before;
    long after;

    // Run and display selection sort
    before = System.currentTimeMillis();
    selectionSort(num);     
    after = System.currentTimeMillis();
    System.out.println("Selection sort took "+ (after-before) +" milliseconds");

    // Run and display bubble sort
    before = System.currentTimeMillis();
    bubbleSort(num);
    after = System.currentTimeMillis();
    System.out.println("Bubble sort took "+ (after-before) +" milliseconds");

    // Run and display insertion sort
    before = System.currentTimeMillis();
    insertionSort(num);     
    after = System.currentTimeMillis();
    System.out.println("Insertion sort took "+ (after-before) +" milliseconds");

    // Run and display merge sort
    before = System.currentTimeMillis();
    mergeSort(num);
    after = System.currentTimeMillis();
    System.out.println("Merge sort took "+ (after-before) +" milliseconds");

    // Run and display quick sort
    before = System.currentTimeMillis();
    quickSort(num);
    after = System.currentTimeMillis();
    System.out.println("Quick sort took "+ (after-before) +" milliseconds");        
}

我打印出各种数组地址，我发现它们都是一样的（这是有道理的，因为我使用的是同一个数组对象）。我认为这是问题所在，因此我尝试使用不同的数组（int[] num，int[] num2...），并尝试在每次runSort()使用num = new int[TOTAL_NUMBERS].

4

3 回答 3

2

那是因为尺寸10太小，无法真正找出各种类型之间的时间差异。尝试将您的尺寸增加到 附近的某个地方50,000，1,00,000以便真正能够看到差异（即使那样它会在几秒钟内）。

如果您的机器可以承受足够的负载，那么请对范围内的元素进行排序10,00,000（非常不建议仅用于测试时差）。

于 2013-03-14T03:13:52.773 回答
0

RJ 是正确的，您的数组太小以至于排序算法无关紧要。

另请参阅此线程 插入排序、合并排序和快速排序的测试用例

于 2013-03-14T03:22:16.960 回答
0

排序算法是一种调整过的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“Engineering a Sort Function”，Software-Practice and Experience，Vol。23(11) P. 1249-1265（1993 年 11 月）。该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降低到二次性能。以上是java doc。

于 2013-03-14T03:29:54.627 回答