为什么我的heapsort比Javas和C++的排序功能更快？

Question

我最近学会了如何使用堆和heapsort的美丽.我决定将heapsort与C++中的std :: sort和Java中的Arrays.sort()进行比较.我整理了一个整数数组,每个整数随机生成在<0; 20亿)

我在Java中用数组生成100,000,000个整数,并运行Arrays.sort(),然后生成新的随机序列并运行我的heapSort().这是我的Java程序的输出:

Arrays.sort time: 10.923 seconds.

Heap sort time: 1.402 seconds.

所以heapsort大约快8倍.

然后我在C++中运行类似的代码,这次使用std :: vector作为我的容器(由于std :: sort需要两个迭代器).

C++结果:

Heapsort: 3.213

std::sort: 37.264

所以在我的程序中,std :: sort大约慢了12倍.

在Java中,我使用System.currentTimeMilis()测量时间,在C++中我使用了clock().

这是在Windows 7,四核英特尔i5 2500k上进行测试,超频至4.8GHz.C++是用-Wall -pedantic标志编译的.

谁能告诉我发生了什么事？heapsort真的那么快吗？或者我在代码中犯了错误？我不希望用大量代码充斥这篇文章,所以我将在本文末尾链接它.

顺便说一句:是的,我知道Arrays.sort()是稳定的,而heapsort则不是.Java没有不稳定的排序(至少,我还没有找到).这就是我在C++中使用std :: sort的原因,看看它是否与稳定性有关.

源代码,包括C++和Java:https://gist.github.com/anonymous/7475399

Answer 1

您的Java代码看起来对我有误

int tmp = heap[0];
heap[i] = heap[0];
heap[i] = tmp;

这不是交换两个元素的代码.

这会对执行时间产生影响吗？我不知道堆的排序是否足以确定.