堆排序与插入排序JMH基准：为什么我的插入实现了。花费更少的时间？

Question

我已经实现了插入排序和堆排序。从理论上讲，堆排序具有 nlogn 时间复杂度，插入具有 n^2。为什么，那么对 100，000 个长数组进行排序需要大约 x6 倍的插入实现？

我使用JMH对每个排序算法的平均时间进行基准测试。以下是我的基准代码：

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

public class MyBenchmark {

// setup the benchmark - create a new array for each iteration
    @State(Scope.Thread)
    public static class MyState {
        int[] array = null;

        @Setup(Level.Iteration)
        public void doSetup() {
            array = createArray(100000, 0, 100);
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.SECONDS)
    public void insertionSort(MyState state) {
        int[] array = state.array;

        for (int i = 1; i < array.length; i++) {
            int element = array[i];
            for (int j = i - 1; j >= 0; j--) {
                if (element < array[j]) {
                    int temp = array[j];
                    array[j] = element;
                    array[j + 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.SECONDS)
    public void heapSort(MyState state) {
        int[] array = state.array;
        sort(array, array.length);
    }

    public static void sort(int[] arr, int size) {

        for (int i = 0; i < size;) {
            maxHeapify(size, arr);
            int temp = arr[0];
            arr[0] = arr[size - 1];
            arr[size - 1] = temp;
            size--;
        }
    }

    private static void maxHeapify(int size, int[] arr) {
        int nonLeafs = size / 2;
        for (int i = nonLeafs; i > 0; i--) {
            int arrayPos = heapToArrayPos(i), leftChild = heapToArrayPos(leftChild(i)),
                    rightChild = heapToArrayPos(rightChild(i));
            if (rightChild < size) {
                if (arr[rightChild] < arr[leftChild]) {
                    if (arr[arrayPos] < arr[leftChild]) {
                        switchWithLeftChild(arrayPos, arr);
                    }
                } else if (arr[arrayPos] < arr[rightChild]) {
                    switchWithRightChild(arrayPos, arr);
                }
            } else if (arr[arrayPos] < arr[leftChild]) {
                switchWithLeftChild(arrayPos, arr);
            }
        }
    }

    private static int heapToArrayPos(int heap) {
        return heap - 1;
    }

    private static int rightChild(int pos) {
        return pos * 2 + 1;
    }

    private static int leftChild(int pos) {
        return pos * 2;
    }

    private static void switchWithRightChild(int pos, int[] arr) {
        int father = arr[pos];
        int childPos = heapToArrayPos(rightChild(pos + 1)), child = arr[childPos];
        arr[childPos] = father;
        arr[pos] = child;
    }

    private static void switchWithLeftChild(int pos, int[] arr) {
        int father = arr[pos];
        int childPos = heapToArrayPos(leftChild(pos + 1)), child = arr[childPos];
        arr[childPos] = father;
        arr[pos] = child;
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder().include(MyBenchmark.class.getSimpleName()).forks(1).build();

        new Runner(opt).run();
    }

    public static int[] createArray(int length, int minValue, int maxValue) {
        return IntStream.generate(() -> ThreadLocalRandom.current().nextInt(minValue, maxValue)).limit(length)
                .toArray();
    }

    public static int[] createArray(int length) {
        return createArray(length, 0, 10);
    }

    public static int[] createArray(int minValue, int maxValue) {
        return createArray(10, minValue, maxValue);

    }
}

这是基准测试的结果:

JMH 1.12（51天前发布）VM版本：JDK 1.8.0_65，VM 25.65-b01 VM调用程序：C：\Program Files\Java\jdk1.8.0_65\jre\bin\0_65VM选项：-0_65=UTF-8-Xbootclasspath：C：\Program Files\Java\jdk1.8.java.exe\jre\lib\0_65；C：\Program Files\Java\jdk1.8.Dfile.encoding\jre\lib\0_65；C：\Program Files\Java\jdk1.8.resources.jar\jre\lib\0_65；C：\Program Files\Java\jdk1.8.rt.jar\jre\lib\0_65；C：\Program Files\Java\jdk1.8.jsse.jar\jre\lib\0_65；C：\Program Files\Java\jdk1.8.jce.jar\jre\lib\jfr.jar；C：\Program Files\Java\jdk1.8charsets.jar\lib\tools.jar 基准：org.sample.MyBenchmark.heapSort

运行进度：完成 0.00%，ETA 00：01：20
分叉：1/1
预热迭代 1：17.651 秒/操作
预热迭代 2：16.004 秒/操作
预热迭代 3：14.640 秒/操作
预热迭代 4：14.699 秒/操作
预热迭代 5：14.836 秒
/操作预热迭代 6：14.900 秒/操作
预热迭代 7：14.758 秒/操作
预热迭代 8：15.084 秒/操作
预热迭代 9： 15.652 秒/操作
预热迭代 10：15.121 秒/操作
预热迭代 11：15.315 秒/操作
预热迭代 12：15.299 秒/操作
预热迭代 13：15.234 秒/操作
预热迭代 14：14.822 秒/操作
预热迭代 15：15.078 s/
op 预热迭代 16：15.565 s/op
预热迭代 17：15.509 s/op
预热迭代 18：15.189 s/op
预热迭代 19： 14.748 s/op
热迭代 20：14.902 s/op
迭代 1：14.888 s/op
迭代 2：15.381 s/op
迭代 3：16.099 s/op
迭代 4：15.536 s/op
迭代 5：15.635 s/op
迭代 6：16.446 s/
op 迭代 7：16.034 s/op
迭代 8：15.828 s/op
迭代 9：15.666 s/op
迭代 10： 16.071 s/op
迭代 11：15.962 s/op
迭代 12：15.777 s/op
迭代 13：15.757 s/op
迭代 14：15.424 s/op
迭代 15：15.449 s/op
迭代 16：15.920 s/op
迭代 17：14.609 s/op
迭代 18：14.651 s/op
迭代 19：14.661 s/
op 迭代 20：14.607 s/op

结果 “堆排序”： 15.520 ±（99.9%） 0.486 s/op [平均值] （最小值、平均值、最大值） = （14.607， 15.520， 16.446）， stdev = 0.560 CI （99.9%）： [15.034， 16.006] （假设正态分布）

JMH 1.12（51天前发布）VM版本：JDK 1.8.0_65，VM 25.65-b01 VM调用程序：C:\Program Files\Java\jdk1.8.0_65\jre\bin\Java。exe VM选项：-Dfile。encoding=UTF-8-Xbootclasspath:C:\Program Files\Java\jdk1.8.0_65\jre\lib\resources。罐子C： \Program Files\Java\jdk1.8.0_65\jre\lib\rt。罐子C： \Program Files\Java\jdk1.8.0_65\jre\lib\jsse。罐子C： \Program Files\Java\jdk1.8.0_65\jre\lib\jce。罐子C： \Program Files\Java\jdk1.8.0_65\jre\lib\charsets。罐子C： \Program Files\Java\jdk1.8.0_65\jre\lib\jfr。罐子C： \Program Files\Java\jdk1.8.0_65\lib\tools。jar预热：20次迭代，每次1s测量：20次循环，每次1秒超时：每次迭代10分钟线程：1个线程，将同步迭代基准模式：平均时间，时间/op基准：org.sample.MyBenchmark.insertionSort

运行进度：完成 50.00%，ETA 00：10：15 分叉：1/1 预热迭代 1：1.726 秒/操作预热迭代 2：1.636 秒/操作预热迭代 3：1.968 秒/操作预热迭代 4：1.970 秒/操作预热迭代 5：1.961 秒/操作预热迭代 6：1.966 秒/操作预热迭代 7：1.962 秒/操作预热迭代 8：1.961 秒/操作预热迭代 9： 1.959 秒/操作 预热迭代 10：1.965 秒/操作 预热迭代 11：1.966 秒/操作预热迭代 12：1.970 秒/操作预热迭代 13：1.964 秒/操作 预热迭代 14：1.952 秒/操作 预热迭代 15：1.955 秒/操作 预热迭代 16：1.956 秒/操作预热迭代 17：1.972 秒/操作预热迭代 18：1.966 秒/操作预热迭代 19： 1.954 秒/操作热迭代 20：1.956 秒/操作
迭代 1：1.969 秒/操作
迭代 2：1.963 秒/操作
迭代 3：2.050 秒/操作
迭代 4：2.019 秒/操作迭代 5：1.934 秒/操作
迭代 6：1.953 秒/操作
迭代 7：1.961 秒/
操作迭代 8：1.972 秒/操作
迭代 9：1.957 秒/操作
迭代 10： 1.956 s/op
迭代 11：1.975 s/op
迭代 12：1.950 s/op
迭代 13：1.965 s/op
迭代 14：1.961 s/op
迭代 15：1.950 s/op
迭代 16：1.956 s/op
迭代 17：1.975 s/op
迭代 18：1.966 s/op
迭代 19：1.959 s/op
迭代 20：1.965 s/op

结果" insertion sort ":< br > 1.968(99.9%)0.022s/op[平均值] (min，avg，max) = (1.934，1.968，2.050)，stdev = 0.025 CI (99.9%): [1.946，1.990](假设正态分布)

基准模式计数分数误差单位< br > my benchmark . heap sort avgt 20 12.692 0.282s/op < br > my benchmark . insertion sort avgt 20 2.024 0.020s/op

编辑：因为我已经发布了这个问题，所以我在基准测试之前添加了@setup来设置数组，所以数组创建操作不会成为一个因素。我再次运行基准测试，插入排序的结果几乎相同。堆排序基准测试平均速度提高了3秒。我只发布了更新的结果摘要。

Answer 1

您的堆排序实现不正确。您发布的代码似乎正在进行选择排序。也就是说，对于它调用maxHeapify的每个项目，获取堆中的第一个项目，将其放在末尾，并减少计数。因此maxHeapify被称为size次，每次大小都在减小。maxHeapify中的内部循环的迭代次数最终类似于（n^2）/4。

你已经用复杂性O(n^2).实现了一个美化的选择排序

执行就地堆排序的诀窍是首先构建堆（一次），然后重新排列它以进行排序。你叫过一次最大堆：

maxHeapify(size, arr);

完成后，您就有了一个有效的max堆，其中最大的项位于arr[0]等处，这需要O（n）时间。

您需要的是一个升序数组。为此，您需要构建一个循环，从堆中复制最大的项目（即arr[0]）并暂时保存它。然后，获取堆中的最后一项，将计数减少 1，然后在顶部重新插入该项，并根据需要对其进行筛选。最后，将上一个最大项放在上一个项先前占用的位置。当 count 达到 0 时，您有一个排序的数组：

int count = size;
while (count > 0)
{
    int save = arr[0];      // save the largest item
    arr[0] = arr[count-1];  // move last item to top
    arr[count-1] = save;    // and place the largest item
    count = count - 1;      // reduce the count
    SiftDown(0);            // sift item into place
}

您所要做的就是在堆上连续调用removeMax，并将结果存储回空出的位置的数组中。

< code>SiftDown是在堆中插入项时使用的相同方法。

关于使用O(n) heapify方法构建堆的完整示例，请参见我的博客文章简单的整数堆。它是用C#写的，但我认为足够简单，如果你懂Java，你就能理解它。我没有展示如何进行排序，但是有了上面的代码和几行代码，您应该可以做得很好。