一个著名的问题是找到用于排序数组的最小交换量。我的问题是，我们有大小为n的数组，我们知道可以用10个交换对它进行排序（我们不知道移动数，仅知道移动数）。我想证明存在一个O（n）算法（用于时间）对该数组进行排序。
首先，为了证明这一说法，我应该提出一些代码吗？我不知道如何证明它。第二，这与排序数组的最小交换量有关吗？
谢谢你的帮助
您的解决方案是采用自适应排序算法。
自适应排序算法的经典示例是“直接插入排序”。在这种排序算法中，我们从左到右扫描输入，重复查找当前项目的位置，并将其插入到先前已排序项目的数组中。
我们知道：
该算法的性能可以用输入中的反转次数来描述，然后
T(n)大致等于I(A)+(n-1)，其中I(A)反转次数是。
因此，正如您的情况一样，求反的次数是恒定的，该算法的复杂度将为Theta(n)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句