arrays - 具有 O(n) 次反转的数组

试图找出最多包含 n 次反转的数组类型，n 是数组大小。我在想一个几乎排序的数组会属于这种情况，并且一个数组几乎完全排序，最大元素和最小元素切换，例如..

9 2 3 4 5 6 7 8 1

所以我的想法是，当一个数组最多有 n 个反转时，可以说这个数组几乎已经排序了吗？或者还有其他情况，其中数组最多有 n 次反转并且几乎没有排序。

最佳答案

“最少”排序数组(即反向排序)具有 1 + 2 + 3 + ... + n-1 = n(n-1)/2 反转。

数组的反转越少，它的排序就越“多”。

并且，由于 n 比 n(n-1)/2 小很多，因此我们可能会调用一个 n 反转“几乎已排序”的数组。

这个数组有 n-1 反转:

9 1 2 3 4 5 6 7 8

为了回应您的评论， insertion sort 的复杂性是 O(n + d) ，其中 d 是反转次数，因此它将在 O(n) 中运行以进行 O(n) 反转。

关于arrays - 具有 O(n) 次反转的数组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19608737/