algorithm - 通过倒数/Pearson's r 找到最优排序算法

Question

是否有可能在预排序序列中给定数量的元素和该序列的倒置数或 Pearson r 找到最佳排序算法？

例如，我有一个预排序的 262143 元素序列。

最大反转数由 (n(n-1))/2 提供，其中 n 是序列中元素的数量(参见 here page 2对于这个假设)。对于此示例，最大值为 34359345153。

现在我的预排序序列的反转次数是 1299203725，这是最大值的 3.78%。我的 Pearson 的 r 是 0.9941。根据我的理解，这应该是一个具有高“排序”的预排序序列(如果我错了请更正我)。

我发现很多关于反转次数和 Person 的 r 的引用作为定义序列“排序性”的一种方式，但我无法对元素和反转的数量/Pearson 的 r 进行某种排序算法的比较是首选之一。

感谢您的帮助。

Answer 1

如果您假设您的排序算法是基于比较的，那么传统排序算法(如合并排序)的最坏情况 O(n log n) 时间可能很难超过。我相信，为了做得一样好或更好，您可能不得不假设反转次数为 O(n log n)，远小于最坏情况下的 O(n^2)。然后，如果您有 O(n) 次反转，并且只要一个元素与其左邻元素形成反转，您就一直向后交换，那么类似冒泡排序的运行速度可能与 O(n) 时间一样快。