swift4 - Sort方法的时间复杂度

Question

我需要对包含数字元素的数组进行排序。但是，我不确定使用 sort 方法是否有效，因为我不知道这种方法的时间复杂度。苹果文件也没有提到它。所以我想知道这个方法的时间复杂度是多少，使用了什么样的排序算法。

标签： swift4

Answer 1

Swift 使用 Introsort。查看源代码，我们看到选择的枢轴是第一个元素。

维基百科链接：https ://en.wikipedia.org/wiki/Introsort

从维基百科页面：

(...)，关键操作之一是选择枢轴：列表分区所围绕的元素。最简单的枢轴选择算法是将列表的第一个或最后一个元素作为枢轴，这在排序或接近排序输入的情况下会导致不良行为。

查看那个 wikipedia 页面，完全可以预测，考虑到实现选择，Swift 的排序性能对于排序的输入来说是最差的。它的平均性能是 ‎O(n log n)，这恰好也是它最坏的情况。