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

Question

我最近学会了如何使用堆和堆排序的优点。我决定将堆排序与C++中的std::sort和Java语言中的Arrays.sort()进行比较。我对整数数组进行了排序，每个整数都是在<0；2000000000范围内随机生成的。)

我用Java语言将100,000,000个整数生成到一个数组中，并运行Arrays.sort()，然后生成新的随机序列并运行我的heapSort()。这是我用Java编写的程序的输出：

Arrays.sort time: 10.923 seconds.

Heap sort time: 1.402 seconds.

所以堆排序的速度大约快8倍。

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

C++结果：

Heapsort: 3.213

std::sort: 37.264

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

在Java中，我使用System.currentTimeMilis()来测量时间，在C++中，我使用来自的时钟()。

这是在Windows7上测试的，四核英特尔i5 2500k，超频到4.8 was。使用-Wall -pedantic标志编译C++。

谁能告诉我这是怎么回事？堆排序真的那么快吗？或者我在代码中犯了一个错误？我不想用大量的代码来淹没这篇文章，所以我将在这篇文章的末尾链接它。

顺便说一下，我知道Arrays.sort()是稳定的，而堆排序是不稳定的。这就是我在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;

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

这对执行时间有影响吗？我不知道堆排序是否足够确定。

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);
    }
}

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

Answer 3

在您的C++代码中还有一个与如何生成随机分布相关的问题：

int randomval()
{
  double d;
  int result;
  d = rand() / RAND_MAX;
  result = (int) (d * N);
  return result;
}

d将始终为0，因为您将执行int除法，然后隐式地将其转换为double。

if (largest != i)
{
    int tmp = heap[i];
    heap[i] = heap[largest];
    heap[largest] = tmp;

    heapify(heap, largest, heapsize);
}

这就是为什么你的实现看起来更快。

用实际的分布修复随机测试数据我想你会发现你的实现会更慢：

#include <random>
// snip...
int main()
{
  int length = 10000000;
  std::vector<int> vint1;

  std::default_random_engine gen;
  std::uniform_int_distribution<int> randomval(1, N);
  for (int i = 0; i < length; i++)
  {
        vint1.push_back(randomval(gen));
  }
  std::vector<int> vint2 = vint1; /* so we're sorting same testdata for both */
  // ...

再次运行基准测试显示：

g++ -std=c++0x -Wall -pedantic -O2 heapsorttest.cpp -o heapsorttest.exe
heapsorttest.exe

Heapsort: 5.822s
true

std::sort: 0.936s
true