编辑：哇，好多很棒的回复。是的，我正在将其用作适应度函数，以评估遗传算法执行的排序质量。因此，评估成本非常重要（即，它必须很快，最好是 O(n)。）

作为我正在研究的 AI 应用程序的一部分，我希望能够根据候选整数数组的单调性（也称为“有序性”）对其进行评分。目前，我使用一种启发式方法，该方法计算最长的已排序序列，然后将其除以数组的长度：

public double monotonicity(int[] array) {    if (array.length == 0) return 1d;    int longestRun = longestSortedRun(array);    return (double) longestRun / (double) array.length;}public int longestSortedRun(int[] array) {    if (array.length == 0) return 0;    int longestRun = 1;    int currentRun = 1;    for (int i = 1; i < array.length; i++) {        if (array[i] >= array[i - 1]) {            currentRun++;        } else {            currentRun = 1;        }        if (currentRun > longestRun) longestRun = currentRun;    }    return longestRun;}

这是一个好的开始，但是它没有考虑到可能存在已排序子序列的“集群”。例如：

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}

这个数组被划分为三个已排序的子序列。我的算法会将其评为仅 40% 有序，但是直观上，它应该获得比这更高的分数。对于此类问题，是否有标准算法？

回答：

我认为要使用什么样的函数很大程度上取决于你的用途。根据你的问题，我猜你正在使用遗传系统来创建一个排序程序，并且这将被用作排名函数。如果是这样的话，那么执行速度至关重要。基于此，我敢打赌你的最长排序子序列算法会很好地工作。听起来它应该能很好地定义适应度。