arrays - 如何确定整数数组已经排序的程度/级别

Question

考虑任何给定的唯一整数的数组，例如[1,3,2,4,6,5] 如何确定“排序度”的级别，范围从 0.0 到 1.0 ?

Answer 1

一种方法是评估必须移动以使其排序的项目数量，然后将其除以项目总数。

作为第一种方法，我会将前者检测为从较高值到较低值发生转换的次数。在您的列表中，这将是:

3 -> 2
6 -> 5

一共两个 Action 。将其除以六个元素得到 33%。

在某种程度上，这是有道理的，因为您可以简单地将 2 移动到 1 和 3 之间，而 5 到 4 和 6 之间。

现在可能存在一些边缘情况，在这种情况下，以不同的方式移动会更有效，但您可能不得不编写非常复杂的搜索算法来找到最佳解决方案。

就个人而言，我会从最简单的选项开始，它能满足您的需求，只有在结果证明不合适时才会费心扩展。