小开

我不确定“最好”的方法是什么，但是一个简单的方法是比较每个元素和它后面的元素，如果 element2 > element 1(或者你想测试的任何东西) ，则增加一个计数器，然后除以元素的总数。应该会给你一个百分比。

小开

衡量列表(或其他顺序结构)排序情况的传统指标是倒排次数。

反转的次数是 a < b AND b abC0的对(a，b) st 索引的次数 a。为了达到这个目的，<<表示你为你的特定排序选择的任何序理论。

完全排序的列表不存在反转，而完全反转的列表存在最大的反转次数。

小开

最佳答案

您可以简单地计算列表中的倒数次数。

倒置

T型元素序列中的倒序是一对序列元素，它们根据 T序列集上的某个排序 <出现无序。

来自维基百科:

形式上，让 A(1), A(2), ..., A(n)是一个 n数字序列。如果 i < j和 A(i) > A(j)，那么这对 (i,j)被称为 A的反转。

序列的倒数是衡量其排序性的一个常见指标。形式上，反转数被定义为反转的次数，也就是说,

为了使这些定义更清楚，考虑示例序列 9, 5, 7, 6。

如果你想要一个 0和 1之间的值，你可以用 N choose 2除以倒数。

要实际创建一个算法来计算列表排序的得分，有两种方法:

方法1(确定性)

修改你最喜欢的排序算法，记录它在运行时改正了多少个反转。尽管这并不简单，而且根据您选择的排序算法有不同的实现，但是您最终得到的算法(就复杂性而言)并不比您开始使用的排序算法更昂贵。

如果你选择这条路线，要知道它不像计算“掉期”那么简单例如，Mergesort 是最坏的情况 O(N log N)，但是如果它在按降序排序的列表上运行，它将纠正所有的 N choose 2倒排。这是在 O(N log N)操作中纠正的 O(N^2)倒置。因此，一些操作必然一次纠正多个反转。您在实现时必须非常小心。注意: 您可以使用 O(N log N)复杂性来完成这项工作，这只是一个技巧。

相关阅读: 计算排列中的“倒置”次数

方法2(随机)

随机样本对 (i,j)，其中 i != j
对于每一对，确定 list[min(i,j)] > list[max(i,j)](0或1)
计算这些比较的平均值

我个人会选择随机方法，除非你有一个精确性的要求-如果只是因为它是如此容易实现。

如果你真正想要的是一个介于 -1(排序降序)和 1(排序升序)之间的值(z') ，你可以简单地将上面的值(z) ，也就是介于 0(排序升序)和 1(排序降序)之间的值映射到这个范围，使用下面的公式:

z' = -2 * z + 1

小开

如果你拿着你的列表，计算该列表中值的排序，然后调用排序 Y的列表和另一个包含从 1到 length(Y)的整数的列表 X，你可以通过计算两个列表之间的相关系数相关系数，r来获得你正在寻找的排序度量。

r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}}

对于完全排序的列表，r = 1.0，对于反向排序的列表，r=-1.0和 r在不同排序程度的这些极限之间变化。

这种方法的一个可能的问题是，根据应用程序的不同，计算列表中每个项的排名等效于对它进行排序，因此它是一个 O (n log n)操作。

小开

可以使用实际相关性。

假设对于排序列表中的每个项，都从零开始赋予一个整数秩。请注意，元素位置指数与排名的关系图看起来像直线上的点(位置与排名之间的相关性为1.0)。

你可以计算这个数据的相关性。对于反向排序，你会得到 -1，以此类推。

小开

除了倒数计数，对于数字列表，可以想象到与排序状态之间的均方距离:

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }


a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case

小开

这个怎么样？

#!/usr/bin/python3


def sign(x, y):
if x < y:
return 1
elif x > y:
return -1
else:
return 0


def mean(list_):
return float(sum(list_)) / float(len(list_))


def main():
list_ = [ 1, 2, 3, 4, 6, 5, 7, 8 ]
signs = []
# this zip is pairing up element 0, 1, then 1, 2, then 2, 3, etc...
for elem1, elem2 in zip(list_[:-1], list_[1:]):
signs.append(sign(elem1, elem2))


# This should print 1 for a sorted list, -1 for a list that is in reverse order
# and 0 for a run of the same numbers, like all 4's
print(mean(signs))


main()

小开

已经有了很好的答案，我想补充一个数学方面的完整性:

可以通过测量列表与排序列表的相关程度来测量列表的排序程度。为此，您可以使用秩相关性(最广为人知的是斯皮尔曼的) ，它与通常的相关性完全相同，但它使用列表中元素的秩，而不是其项目的模拟值。
存在许多扩展，比如相关性系数(对于精确排序为 + 1，对于精确反转为 -1)
这允许你有这个度量的统计特性，比如排列中心极限定理，它允许你知道这个度量对随机列表的分布。

小开

我会计算比较次数，然后除以比较次数的总和。

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]


right_comparison_count = 0


for i in range(len(my_list)-1):
if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
right_comparison_count += 1


if right_comparison_count == 0:
result = -1
else:
result = float(right_comparison_count) / float((len(my_list) - 1))


print result

有没有一种方法可以测量列表的排序情况？

倒置

方法1(确定性)

方法2(随机)