首页 文章

从结果中确定排序算法

提问于
浏览
1

我现在正在修改排序算法 . 这是一个问题:

给出该排序算法用C语言编写,并将'a'和'A'视为相等,运行此排序算法后,结果如下:

10000随机数据 - > 0.016秒
100000随机数据 - > 0.304秒

10000个有序数据 - > 0.006秒
100000个有序数据 - > 0.108秒

10000反转数据 - > 0.010秒
100000反向数据 - > 0.138秒

问题:简要说明您可以从上述测试结果中得出的结论 .

What I have done
我知道这种排序算法是 non-stable (如问题中所述),我猜它是一种快速排序 . 我知道快速排序有最坏情况 O(n^2) ,平均和最佳情况 O(n log n) ,但我不知道如何从结果中解释,我可以快速排序 .

我可以从结果中找出具体的信息吗?如果有数学计算或结果中的其他重要观察,那将是很好的 .

1 回答

  • 2

    我们可以看出,这不是一个 O(n*log(n)) 平均情况算法,比如mergesort或一个好的快速排序 .

    我们可以看出该算法不是自适应的,或者至少不是非常自适应的 . 自适应算法在分类输入上的表现要好得多,也可能在反向输入上表现得更好 . 特别是,将排序输入的大小提高10倍会使运行时间增加大约10倍 . 虽然算法在排序或反向排序的输入上比随机输入做得更好,但这看起来更像是一个结果例如,在这些情况下更有效的分支预测 .

    我们没有任何信息表明排序是否稳定 .

    我没有看到任何可以区分这是一个快速排序,合并,合作,还是其他 O(n*log(n)) 算法的东西 . 我们可以为快速排序排除某些类型的枢轴选择 - 例如,总是选择第一个元素的快速排序,因为枢轴将在排序输入的二次时间内运行 - 但除此之外,我无法分辨 .

相关问题