c++ - 在 C++ 中对包含 double 类型数字的数组进行排序的最快方法是什么？

Question

在 C++ 中对包含 double 类型数字的数组进行排序的最快方法是什么？我有两种类型的数组，第一种长度为 20，第二种长度为 5000，数组长度对哪种算法最快有影响吗？长度为 5000 的数组平均包含 28 个不同的值。

http://www.codeproject.com/Articles/38381/STL-Sort-Comparison-Function

Answer 1

对于第一个问题：如果您的数组只有一小组唯一值（如您所说的 28），您可能需要考虑某种计数排序（口味：基数、鸽笼、桶）。如果您知道数组内容的硬性限制和范围，您可能会做一些好事。

但如前所述，对于这么小的数组，你可能对 std::sort 很好，除非你有很多 5000 元素的数组要排序。

对于第二个问题：长度问题（见天空的答案）。O(n log n) 是任何正常排序所能做的最好的。O(n^2) 通常是最坏的情况。O(n^2) 意味着在最坏的情况下，您的 20 元素数组将需要对应于 20^2 (=400) 次操作的时间，而您的 5000 数组时间对应于 5000^2 (=2500 万) 次操作。如您所见，在这种情况下，更大的数组意味着更多的时间。对于您的情况和 O(n log n) 算法，5000 数组将需要对应于 5000 log 5000 (=18500) 操作的时间。

一个操作是什么以及它需要多长时间取决于特定的实现，并且通常与比较无关（因此被 Ordo 表示法忽略）。当数组大小足够大时，O(n log n) 算法的慢速实现仍然比 O(n^2) 算法的快速实现快。但是对于像 20 个元素这样的小数组，一个好的低开销实现最重要。400 个快速操作将比 26 个慢操作快。对 5000 个阵列进行相同的比较表明，2500 万次快速操作仍然不会比 18500 次慢速操作快。

另一个因素是数组的内容。一些算法，如插入排序，在几乎正确顺序的数组上特别快（接近 O(n)），而在随机输入上却很差 O(n^2)。

通过利用数组内容的预定义（已知）限制/范围（因此不归类为正常排序），计数排序可以接近 O(n)，也就是说，时间与元素的数量成正比。参见维基百科。

快乐的研究！

Answer 2

我有所作为，但你最好的选择是使用 std::sort 。它根据输入大小在内部切换认为最佳的排序算法。

参见维基百科参考：

• https://en.wikipedia.org/wiki/Sort_%28C++%29
• https://en.wikipedia.org/wiki/Introsort

Answer 3

您可能想要搜索快速排序、归并排序、插入排序或冒泡排序等排序算法。

排序很大程度上取决于要排序的项目的数量，这可以从排序算法的符号“大 O 符号”中看出。不同值和数据类型的平均数量通常不会在运行时产生足够的影响。（冒泡排序）算法的O(n^2)复杂性是您拥有的元素数量的平方，它告诉您它的时间与要排序的项目数量大致成二次增长。快速排序具有O(n log n)复杂性，使其成为最快的排序方法之一。

冒泡排序是最容易实现且运行时最慢的。

编辑：正如评论所说，无论你使用什么算法，只有 5000 个值的短数组并没有太大的区别，只要它不像 Bogosort。