Clojure中内置"排序"的时间复杂性

Question

我想知道的复杂性(大O表示法),Clojure的编程语言提供,我做我的搜索关于它的上内置的"排序"功能clojuredocs页面,但我没有找到任何关于它.

提前致谢.

Answer 1

该sort内置实际上是调用java.util.Arrays.sort:

(defn sort
  "Returns a sorted sequence of the items in coll. If no comparator is
  supplied, uses compare.  comparator must implement
  java.util.Comparator.  Guaranteed to be stable: equal elements will
  not be reordered.  If coll is a Java array, it will be modified.  To
  avoid this, sort a copy of the array."
  {:added "1.0"
   :static true}
  ([coll]
   (sort compare coll))
  ([^java.util.Comparator comp coll]
   (if (seq coll)
     (let [a (to-array coll)]
       (. java.util.Arrays (sort a comp))
       (seq a))
     ())))

对通用Object值的Java排序有以下注释(强调添加):

实现注意事项:此实现是一个稳定的,自适应的迭代合并输出,当输入数组被部分排序时,它需要远低于n lg(n)的比较,同时在输入数组随机排序时提供传统mergesort的性能.如果输入数组几乎已排序,则实现需要大约n次比较.临时存储要求从几乎排序的输入数组的小常量到随机排序的输入数组的n/2个对象引用不等.

该实现在其输入数组中具有升序和降序的相同优点,并且可以利用相同输入数组的不同部分中的升序和降序.它非常适合合并两个或多个排序数组:只需连接数组并对结果数组进行排序.

该实现改编自Tim Peters的Python排序(TimSort).它使用了Peter McIlroy的"乐观分类和信息理论复杂性"中的技术,参见"第四届年度ACM-SIAM离散算法研讨会论文集",第467-474页,1993年1月.

但是,还有其他重载方法,对于原始类型,int[]如下所示:

排序算法是Vladimir Yaroslavskiy,Jon Bentley和Joshua Bloch 的Dual-Pivot Quicksort.该算法在许多数据集上提供O(n log(n))性能,导致其他快速降序降级为二次性能,并且通常比传统(单枢轴)Quicksort实现更快.

复杂性还取决于自定义比较算法的复杂性.

Answer 2

查看源代码,您可以看到它只是委托给java.util.Arrays.sort:

(defn sort
  ([coll]
   (sort compare coll))
  ([^java.util.Comparator comp coll]
   (if (seq coll)
     (let [a (to-array coll)]
       (. java.util.Arrays (sort a comp)) ; Here
       (seq a))
     ())))

显然java.util.Arrays.sort使用Timsort,根据维基百科,它的最坏情况运行时为O(n log n).

为了验证,在IntelliJ 的ctrl+ B兔子洞之后,我最终sort得到了签名:

public static <T> void sort(T[] a, Comparator<? super T> c)

在这个功能的主体是这一点:

...
if (LegacyMergeSort.userRequested)
    legacyMergeSort(a, c);
else
    TimSort.sort(a, 0, a.length, c, null, 0, 0);
...

所以它看起来确实使用Timsort,除非用户请求它使用传统的Merge Sort实现.