当前位置：文江博客话题详情

快速排序与选择排序（Java 与 C++）

发布于 2024-11-05 23:06:01 字数 609 浏览 3 评论 0原文

我创建了两个项目。一种是 C++ 的，另一种是 Java 的。我对两者进行了快速排序和选择排序的计时试验。奇怪的是我发现了一些非常奇怪的行为。

以下是大小为 10,000 的数组的结果：

SelectionSort Java：80 毫秒

SelectionSort C++：2914 毫秒

QuickSort Java：1 毫秒

QuickSort C++：约 45 秒

现在你可以说我疯了，但我一直被告知 QuickSort 是最快的。这在 Java 中被证明是正确的，但在 C++ 中它完全被关闭了。

所以我的问题是，C++ 处理 QuickSort 的方式是否不同？

我试图保持不同语言之间的函数相同，除了在 C++ 中使用向量与 int 数组之外，它们完全相同。无论如何，我更喜欢使用向量，因为我想在 C++ 中使用排序的实际项目需要向量。

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

编辑：

我相信我明白问题所在。感谢大家的快速回复。我将修改我的代码以按预期工作。我知道这是一个简单的错误。另外，虽然问的问题很尴尬，但回答很有教育意义。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

忘你却要生生世世 2024-11-12 23:06:01

您的快速排序函数在每次递归调用时按值返回整个向量，即使该函数会就地修改它。可能返回所有这些临时文件然后扔掉它们会损害性能。

只需将函数更改为 void 并删除结尾的 return 并看看它的行为如何。

编辑：如果您更习惯 Java，其中几乎所有内容都是垃圾收集引用，请注意，在 C++ 中，按值返回（正如您在返回类型上所做的那样）通常会复制所返回的内容。正如@Johannes Schaub - litb 指出的那样，编译器甚至无法优化返回，因为它没有返回自动（本地）变量。

EDIT2：如果您不这样做作为练习，但您应该使用 std::sort 或 std::stable_sort （后者如果您知道您的数据已经几乎已排序，或者您需要保留重复项的顺序）。例如 std::sort(A.begin(), A.end());

回复收藏 0 原文

救赎№ 2024-11-12 23:06:01

您将在每次递归调用时返回一个完整的向量。这需要花费大量的时间（99.99%的时间都花在了复制上）。

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

编辑：

显然 std::sort 不保证是快速排序，但保证是 O(n*log(n))。来源

回复收藏 0 原文

深白境迁sunset 2024-11-12 23:06:01

您的 C++ 代码还有另一个问题，似乎尚未有人指出。如果我们去掉计时代码，它就会变得非常明显：

quicksort(A,0,length - 1);

SelectionSort(A,length);

您正在对已经排序的数据进行选择排序。在这种情况下，它可能不会产生很大的影响，但仍然有一些帮助。如果您使用插入排序，它几乎会显示为瞬时的。

There's yet another issue with your C++ code that nobody seems to have pointed out yet. If we get rid of the timing code, it becomes pretty obvious though:

quicksort(A,0,length - 1);

SelectionSort(A,length);

You're doing the selection sort on data that's already sorted. Under the circumstances, it probably doesn't make a huge difference, but still helps some. If you used an insertion sort, it would show up as practically instantaneous.

回复收藏 0 原文

最美的太阳 2024-11-12 23:06:01

该问题很可能与您的快速排序的实现有关。如果包含标头并使用 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 尽可能地优化）。

The issue is most probably related to your implementation of quicksort. If you include the header and use std::sort --which is not quicksort, but introsort, a variant that is meant to improve the worse case performance the results are quite different:

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

While running with your implementation of quicksort I am getting outputs similar to:

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

The hardware is a Core2-Duo 2GHz, and I compiled with g++ -O3 -o CompareSorts CompareSorts.cpp (note that the -O3 is important: it tells gcc to optimize as much as it can).

回复收藏 0 原文

找个人就嫁了吧 2024-11-12 23:06:01

你的C++代码失败了。首先，该标准已经提供了快速排序 - std::sort。其次，您为静态大小的数组选择了 std::vector 吗？第三，ftime 和其余的不是有效的分析计时器。第三，即使该函数需要引用，您也会不断从快速排序返回值 - 如果您没有正确设置优化标志，这可能会破坏性能。

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毫秒。

Your C++ code is fail. Firstly, the Standard already provides a quicksort- std::sort. Secondly, you picked a std::vector- for a statically sized array? Thirdly, ftime and the rest are not valid profiling timers. Thirdly, you keep returning values from quicksort, even though the function takes a reference- if you didn't set the optimization flags correctly this could destroy performance.

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.7ms.

回复收藏 0 原文