algorithm - 证明 10 次交换存在 O(n) 算法

Question

一个著名的问题是找到对数组进行排序的最小交换量。我的问题是我们有大小为 n 的数组，我们知道我们可以用 10 次交换对它进行排序(我们不知道移动，只知道移动的次数)。我想证明存在一个对这个数组进行排序的 O(n) 算法(对于时间)。

首先，为了证明这个陈述，我应该提供一些代码吗？我不知道如何证明 其次，这与排序数组的最小交换量有关吗？

谢谢你的帮助

Answer 1

您的解决方案在 Adaptive sorts algorithms 中.

A classic example of an adaptive sorting algorithm is Straight Insertion Sort. In this sorting algorithm, we scan the input from left to right, repeatedly finding the position of the current item, and insert it into an array of previously sorted items.

我们知道:

The performance of this algorithm can be described in terms of the number of inversions in the input, and then T(n) will be roughly equal to I(A)+(n-1), where I(A) is the number of Inversions.

因此，在您的情况下，反转的次数是常数，该算法的复杂度将为 Theta(n)。