根据结果确定排序算法

Question

我现在正在修改排序算法。以下是一个问题：

给出了该排序算法用C编写，并将'a‘和'A’视为相等的排序算法，运行该排序算法后，结果如下：

10000随机数据-> 0.016秒

100000随机数据-> 0.304秒

10000有序数据-> 0.006秒

100000有序数据-> 0.108秒

10000反向数据-> 0.010秒

100000反向数据-> 0.138秒

问题:在点形式中，简要说明你可以从上面的测试结果中得出的结论。

我做了什么，

我知道这个排序算法是非稳定的(如问题中所述)，我可以猜到它是一个快速排序。我知道快速排序有最坏的情况O(n^2)，O(n log n)，但是我不知道如何从结果中解释，我不能只是说哦，因为它的不稳定和快速排序有坏的结果逆序，所以我可以确定它是快速排序。

从结果中我能看出什么具体的东西吗？如果有数学计算或其他一些重要的观察结果，那就太好了。

Answer 1

我们可以看出，这不是像选择排序或插入排序那样的二次时间算法，因为将输入大小提高10倍会使运行时提高13-19倍。这是我们所期望的O(n*log(n))平均案例算法的行为，比如mergesort或一个好的快速排序算法。

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

我们没有任何信息表明这类信息是否稳定。

我看不出有什么能区分这是快速排序、合并、堆排序还是其他O(n*log(n))算法。我们可以排除对快速排序的某些类型的枢轴选择--例如，一个总是选择第一个元素的快速排序，因为支点将在排序输入上在二次时间内运行--但除此之外，我不知道。