快速排序与选择排序的比较（Java vs C++）

Question

我创建了两个项目，一个是C++，一个是Java。我对快速排序和选择排序在两个项目中做了时间测试。奇怪的是，我发现了一些非常奇怪的行为。

以下是一个大小为10000的数组的结果：

Java选择排序：80毫秒

C++选择排序：2914毫秒

Java快速排序：1毫秒

C++快速排序：约45秒

现在可以叫我疯了，但我一直被告知快速排序是最快的。这在Java中被证明是正确的，然而在C++中它却完全失败了。

所以我的问题是，C++是否以不同的方式处理快速排序？

我尝试保持两种语言之间的函数相同，它们完全相同，唯一的区别是在C++中使用向量而不是整数数组。无论如何，我更喜欢使用向量，因为我想在C ++中将其用于实际项目需要一个向量类型的排序。

我确定这是一个愚蠢的错误或者我正在做什么事情，但请提供一些关于发生这种情况的见解。

编辑：

我相信我知道问题出在哪里了。感谢大家极快的回应。我将修改我的代码以按预期工作。我知道这是一个简单的错误。此外，虽然问题很尴尬，但回复是有教育意义的。

- Timlankey

---

使用Java中的“向量”。你正在比较苹果和橙子。 - Brian Roach

你是怎么编译你的C++代码的？你有开启优化吗？ - GWW

我只是在使用Visual Studio进行编译，使用默认设置，我不认为我已经开启了优化。此外，我将用于计时结果的最终编译器将不受我的控制。 - Timlankey

值得注意的是，快速排序并不保证是最快的。在最坏情况下，该算法需要进行O(nn)次比较。如果您想要保证O(nlogn)的时间复杂度，请使用归并排序。 - jakubiszon

@Timlankey：任何关心程序性能的人都不会关闭优化编译。非优化构建的性能是无关紧要的，所有发布构建都已经开启了所有优化。 - Puppy

Answer 1

你的快速排序函数在每次递归调用时都通过值返回整个向量，尽管函数会对其进行就地修改。很可能返回所有这些临时对象然后将它们丢弃会影响性能。

只需要将函数改为void类型并删除结尾的return语句，看看它的表现如何。

编辑：如果你更习惯Java，那么请注意，在C++中按值返回（如你在返回类型中所做的）通常会复制被返回的任何东西。正如@JohannesSchaub-litb指出的那样，编译器甚至无法优化掉返回，因为它没有返回自动（局部）变量。

编辑2：如果你不是在练习，你应该使用std::sort或std::stable_sort（如果你知道你的数据已经几乎有序，或者你需要保留重复项的顺序）。例如：std::sort(A.begin(), A.end());

- Mark B

---

问题在于，我排序的原因是因为我需要在主函数中重复使用已排序的数组（未在我提供的代码中显示）。 - Timlankey

这里不可能使用 NRVO，因为它没有返回自动变量。 - Johannes Schaub - litb

谢谢Mark，我非常感激你的帮助，使用std::sort似乎是最好的选择。 - Timlankey

Answer 2

在每次递归调用时，您返回了完整的向量。这需要很长时间（99.99％的时间用于复制）。

顺便说一下，您可以在C ++中使用STL sort函数，它保证是快速排序（尽管这会破坏您的分析，因为您没有进行真正的比较）。

编辑：

显然，std :: sort不能保证是快速排序，但它保证是O（n * log（n））。 Source

- orlp

---

你说C++中的快速排序有问题？除非我链接了错误的文件，否则它与Java中的相同，只是使用向量而不是整数。如果我完全弄错了快速排序算法，请告诉我。我想能够编写一个平均时间复杂度为O(nlogn)的C++排序程序。 - Timlankey

@Timlankey：使用std::sort，它的时间复杂度为O(nlogn)。 - orlp

std::sort不能保证是快速排序。但它保证时间复杂度为O(n Log n)。 - user2100815

+1 很好的发现。@Timlankey：只需从quicksort函数中删除返回语句，就可以大大提高操作速度。@nightcracker：std::sort通常是introsort，这是一种围绕快速排序的变体，试图避免可怕的最坏情况性能。 - David Rodríguez - dribeas

@David Rodriguez：对不起，我记错了。但它保证是O(n*log(n))的时间复杂度。 - orlp

Answer 3

你的C++代码还存在一个问题，似乎还没有人指出。如果我们去掉计时代码，这个问题就很明显了：

quicksort(A,0,length - 1);

SelectionSort(A,length);

您正在对已排序的数据执行选择排序。在这种情况下，可能并没有太大的区别，但仍然会有所帮助。如果您使用插入排序，它将几乎瞬间显示出来。

- Jerry Coffin

---

是的，我也注意到了。说实话，我有点忘记C++的工作原理了。我已经好几年没有接触C++了，所以在它上面犯了很多愚蠢的错误。不过还是谢谢你，我发帖后意识到了这一点。 - Timlankey

Answer 4

问题很可能与您的快速排序实现有关。如果您包括 std::sort 头文件并使用——这不是快速排序，而是 introsort，一种旨在改善最坏情况性能的变体，则结果会非常不同：

$ ./CompareSorts 
Quick Sort Took: 1
Selection Sort Took: 101

当我使用您的快速排序实现运行时，我得到类似于以下输出：

$ ./CompareSorts 
Quick Sort Took: 41
Selection Sort Took: 95

硬件是Core2-Duo 2GHz，我使用g++ -O3 -o CompareSorts CompareSorts.cpp编译（请注意-O3很重要：它告诉gcc尽可能进行优化）。

- David Rodríguez - dribeas

Answer 5

你的C++代码失败了。首先，标准库已经提供了快速排序函数- std::sort。其次，你选择了一个std::vector来代替静态大小的数组？第三，ftime和其他计时器不是有效的性能分析工具。另外，你在quicksort函数中不断返回值，即使该函数使用引用作为参数- 如果你没有正确设置优化标志，这可能会破坏性能。

int main()
{
    std::vector<int> A(array_size);

    for(int i = 0; i < array_size; i++)
    {
        A[i] = rand() % array_size;
    }

    __int64 begin, end, frequency;
    QueryPerformanceFrequency((LARGE_INTEGER*)&frequency);
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    std::sort(std::begin(A), std::end(A));
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    std::cout << "Quick Sort Took: " << ((double)(end - begin) / frequency) * 1000 << std::endl;
    std::cin.get();

    return 0;
}

0.7毫秒。

- Puppy

---

它的大小不是静态的。在我真正想要使用它的最终实现中，大小将是未知的。这个程序只是为了测试它的时间而制作的。 - Timlankey

@Timlankey：我刚刚编辑了一个动态大小的向量。这显著减少了我的机器上的运行时间。但这并不改变你的代码违反基本分析原则的事实 - 除了这样一个合成基准毫无意义。 - Puppy

谢谢DeadMG，我学到了很多。我以前真的不知道如何在C++中进行基准测试。提供的代码显著地帮助了我解决了许多之前遇到的问题。 - Timlankey

Answer 6

我同意Mark B的观点

你还应该确保： - 每个测试单独运行 - 每个测试运行多次以获得平均值 - 所有测试使用相同的数据

- VirtualTroll

Answer 7

你的代码存在一些问题导致了这个错误。在Java版本中，你对接收到的数组进行排序，而在C++版本中，你对向量进行排序并返回其副本（每次快速排序递归都会进行不必要的复制）。

别忘了使用优化（-O3）编译C++版本。

- fbafelipe

Answer 8

Mark B在这个问题上说得一针见血。我用更新的代码在我的设备上重复了测试，结果如下：

Java QS: 7毫秒

Java SS: 111毫秒

相比之下

C++ QS: 1毫秒

C++ SS: 72毫秒

- Captain Giraffe