java - 对根据输入大小平均不同排序算法的持续时间感到困惑吗？

Question

我正在尝试编写一种方法来比较四种不同排序算法(合并排序、快速排序、堆排序、插入排序)的运行时间。我试图在 for 循环的每次迭代中对每个算法进行计时，这会增加每个循环随机生成的数组的数组大小。我的代码可以工作，但需要太多时间。在循环结束时，我计算每个排序算法接管大小从 1 到 100 的数组的平均时间。

注意:generateArray(num) 只是创建一个填充有大小为 num 的随机整数的数组。

我不是一个出色的编码员，有什么方法可以更好地实现它？

这是代码片段:

static void testArrays() {
    ThreadMXBean bean = ManagementFactory.getThreadMXBean();
    long insertionCount=0, mergeCount=0, 
            quickCount=0, heapCount = 0;

    for (int i=1; i<100; i++) {
        long[] A = generateArray(i);
        long[] copy1 = A.clone();
        long[] copy2 = A.clone();
        long[] copy3 = A.clone();

        long startTime1 = bean.getCurrentThreadCpuTime();
        insertionSort(A);
        long endTime1 = bean.getCurrentThreadCpuTime();
        long duration = endTime1 - startTime1;
        insertionCount = insertionCount + duration;

        long startTime2 = bean.getCurrentThreadCpuTime();
        mergeSort(copy1);
        long endTime2 = bean.getCurrentThreadCpuTime();
        long mergeDuration = endTime2 - startTime2;
        mergeCount = mergeCount + mergeDuration;

        long startTime3 = bean.getCurrentThreadCpuTime();
        heapSort(copy2);
        long endTime3 = bean.getCurrentThreadCpuTime();
        long heapDuration = endTime3 - startTime3;
        heapCount = heapCount + heapDuration;


        long startTime4 = bean.getCurrentThreadCpuTime();
        quickSort(copy3);
        long endTime4 = bean.getCurrentThreadCpuTime();
        long quickDuration = endTime4 - startTime4;
        quickCount = quickCount + quickDuration;

    } 
    long averageIS = insertionCount/10000;
    long averageMS = mergeCount/10000;
    long averageHS = heapCount/10000;
    long averageQS = quickCount/10000;
    System.out.println("Insertion Sort Avg: " + averageIS);
    System.out.println("MergeSort Avg: " + averageMS);
    System.out.println("HeapSort Avg: " + averageHS);
    System.out.println("QuickSort Avg: " + averageQS);
}

Answer 1

有比较排序和分布排序。

比较排序法是通过一次比较两个要比较的键值并交换来进行排序的方法

分布式排序是一种根据键值将数据划分为若干子集，通过对每个子集进行排序来实现整体排序的方法。

众所周知，快速排序是最快的。在最坏的情况下，n² 发生在主元处于最小值和最大值时。为了避免这种情况，请随机使用枢轴或三媒体分区。平均而言，它会产生最佳性能。

对于已排序的数据，插入排序是最快的。如果它们已经排序，则仅与第一个元素进行比较。

上述算法的时间复杂度如下。

O (n²):冒泡排序、选择排序、插入排序、希尔排序、快速排序

O(n log n):堆排序、归并排序

O(kn):基数排序(k有一个限制，即它可以在低位数和低位数的4字节整数上表现良好)。