什么时候简单的排序比复杂的排序快？
我在学校被分配了一个排序算法，我们的任务是回顾几种排序算法。报告的其中一节与“何时简单排序更快”有关。
我所拥有的排序算法是：
- 气泡分类
- 选择排序
- 插入
均为O(n^2)平均
然后，我有以下O(n log )算法：
- 合并排序
- 快速排序
和基类O(kn)
我已经对未排序和排序的数据进行了几次测试，从10到100,000的n个条目不等，而且复杂排序O(n log )总是在更快的时间内执行。
我还尝试使用包含n个元素的排序数据集，其中n= 10到100,000。
但是，O(n log )算法仍然更快。
所以我的问题是，什么时候简单的排序比复杂的快。
谢谢克里斯。
回答 5
Stack Overflow用户
发布于 2014-02-26 17:49:49
在运行时间与输入大小的平方成正比的类型中，内部循环中的分支往往非常简单。
插入排序通常在这方面效果最好。
另一方面，对于N个大小的输入，运行时间与N个log成正比的排序具有更复杂的分支。
分支复杂性显示为运行时的一个常量因素。因此，我们有一个简单而复杂的运行时
S N^2 and C N log N在较旧的计算机上，S往往比C小得多。为了好玩起见，假设你有S=1和C= 4，那么你有一个可以求解的方程：
1 N^2 = 4 N log N兴趣的解是在N= 16 (原木是基2)。这是输入的大小，其中“简单”算法所具有的速度较好的常数因子被较好的渐近速度所克服。小于16的输入将按正弦算法更快地排序！当N> 16时，复算法的幂“踢”。
然而，在现代计算机中--正如您所发现的--硬件级分支的速度更快，编译器更好地使S和C更加接近。在我的经验中，只有微小的嵌入式处理器才是关于N^2类跑得更快、明显可见的古老传说。
Stack Overflow用户
发布于 2014-02-26 17:31:08
这实际上取决于算法的具体实现。通常，对于0到低的几十个元素，插入排序将超过大多数O(n log )排序，但实际的数目取决于插入排序的实现方式、数据的排序方式、比较的开销等等。在这种情况下，您几乎必须运行排序算法的特定实现，以确定何时执行哪个排序更快。
希望这能有所帮助！
Stack Overflow用户
发布于 2014-02-26 17:36:29
首先，基排序不是O(nlogn)。它是O(kn)，其中k是任意数字中的最大数字数。
时，O(n^2)排序可能比O(nlogn)排序快
- 输入的大小很小。如果您的输入包含~100 (甚至~1000)数字，现代处理器可以显示
O(n^2)排序更快(或与O(nlogn)相同)。 - 在某些情况下，当
O(n^2)排序识别要排序的数组时，它可以在排序过程中停止，这在O(nlogn)排序的情况下很难(但仍然有可能)实现。 例如，在插入排序或标记气泡排序中，如果数组已排序，则可以停止该算法。这将导致最佳情况下的O(n)性能。
https://stackoverflow.com/questions/22048619
复制相似问题
腾讯云开发者
