为什么我的heapsort比Javas和C++s排序函数更快？

Question

我最近学会了如何使用堆和堆的美丽。我决定将HePo排序与STD:：排序在C++和数组中进行比较。Java中的sort（）。我对一个整数数组进行排序，每个整数在<；0; 20亿）

我用Java将100000000个整数生成一个数组，然后运行数组。sort（），然后生成新的随机序列并运行my heapSort（）。这是我的Java程序的输出：

Arrays.sort time: 10.923 seconds.

Heap sort time: 1.402 seconds.

所以希普索尔的速度大约是它的8倍

我在C++中运行了类似的代码，这次使用STD::vector作为容器（由于STD：：排序需要两个迭代器）。p>

C++结果：

Heapsort: 3.213

std::sort: 37.264

所以在我的程序中，std:：sort大约慢12倍

在Java中，我使用系统测量时间。CurrnTimeMILSE（）和C++中，我使用了CordOnter（）。p>

这是在Windows 7上测试的，四核Intel i5 2500k，超频至4.8GHz。用^ {< CD1> }标志编译C++。

有人能告诉我发生了什么事吗？希普索尔真的那么快吗？还是我的代码出错了？我不想让这篇文章充斥着大量的代码，所以我会在这篇文章的末尾链接它

顺便说一句：是的，我知道。sort（）是稳定的，heapsort不是。Java没有不稳定的排序（至少，我还没有找到）。这就是为什么我使用STD：：C++中的排序，看看它是否与稳定性有关。p>

源代码，既有C++又有java：https://gist.github.com/anonymous/7475399

Answer 1

我觉得你的Java代码有问题

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

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

这对执行时间有影响吗？我不太清楚，不能确定

Answer 2

<>你没有正确地在java中（约翰指出），也不在C++代码中：

void heapSort(vector<int> & heap, int length)
{
    int heapsize = length;
    buildHeap(heap, heapsize);
    for(int i = heapsize-1; i >= 1; i )
    {
        int tmp = heap[0];
        heap[i] = heap[0];
        heap[i] = tmp; // overwrote the item you just tried to swap!
        heapsize ;
        heapify(heap, 0, heapsize);
    }
}

简而言之，您的代码“更高效”，因为它根本不做任何排序