有没有一种方法来衡量一个列表如何sorting？
有没有办法测量一个列表的sorting方式？
我的意思是，这不是要知道一个列表是否被sorting（布尔），而是像“sorting”的比率，就像统计中的相关系数一样。
例如，
-
如果列表中的项目按升序排列，那么它的比率就是1.0
-
如果列表按降序排列，则其速率将为-1.0
-
如果列表几乎按升序sorting，则其比率将为0.9或接近1的某个值。
-
如果列表根本没有sorting（随机），它的速率将接近于0
我正在斯卡拉的一个小型图书馆练习。 我认为sorting率是有用的，但我没有find任何关于这样的信息。 也许我不了解这个概念的充分条件。
你可以简单地计算列表中的反转次数。
逆温
Ttypes的元素序列中的反转是一对序列元素，它们按照T的集合上的一些sorting<顺序出现。
维基百科 ：
正式地，令
A(1), A(2), ..., A(n)是n数字的序列。
如果i < j且A(i) > A(j)，则(i,j)对称为A的反演 。序列的倒数是其sorting的一个常用度量。
倒数定义为倒数的数量，也就是说，
为了使这些定义更清楚，请考虑示例序列9, 5, 7, 6 。 这个序列有倒数 (0,1), (0,2), (0,3), (2,3)和倒数 4 。
如果你想要一个介于0和1之间的值，你可以用N choose 2来除反转号码。
要实际创build一个algorithm来计算列表的sorting方式，您有两种方法：
方法1（确定性）
修改您最喜爱的sortingalgorithm，以跟踪它在运行时正在纠正的倒数。 尽pipe这是非常平凡的，并且根据您select的sortingalgorithm而有不同的实现，但您最终将得到的algorithm不会比开始使用的sortingalgorithm更昂贵（就复杂性而言）。
如果你采取这种方式，请注意，这不像计算“掉期”那么简单。 例如，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） - 计算这些比较的平均值，然后用
N choose 2进行标准化，N choose 2
我个人会采用随机方法，除非你有正确的要求 – 如果只是因为它很容易实现。
如果你真正想要的是-1 （sorting降序）到1 （sorting升序）之间的值（ z' ），则可以简单地映射上面的值（ z ），该值在0 （sorting升序）和1 （sorting降序），使用这个公式：
z' = -2 * z + 1
如何sorting列表（或其他顺序结构）的传统测量方法是反演次数。
倒数的数目是a <b AND b << a的对（a，b）st索引的数目。 为了这些目的， <<代表您为特定类别select的任何顺序关系。
一个完全sorting的列表没有倒序，完全颠倒的列表具有最大的倒序数目。
你可以使用实际的相关性。
假设对于sorting列表中的每个项目，您分配一个从零开始的整数sorting。 请注意，元素位置索引对等级的graphics看起来像一条直线上的点（位置和等级之间的相关性为1.0）。
您可以计算此数据的相关性。 对于反向sorting，您将得到-1等等。
有很好的答案，我想补充一个完整性的math方面：
-
您可以通过测量与sorting列表相关的程度来衡量列表的sorting方式。 要做到这一点，你可以使用等级相关性（最着名的是Spearman's ），它与通常的相关性完全相同，但它使用列表中的元素排名而不是其项目的模拟值。
-
存在许多扩展，如相关系数 （精确sorting+1，精确反转-1）
-
这允许你有这个度量的统计特性，比如置换中心极限定理，它可以让你知道随机列表的这个度量的分布。
除了倒数计数之外，对于数字列表，可以想象从sorting状态到均值的平方距离：
#! 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
我不确定“最好”的方法，但一个简单的方法是比较每个元素和后面的元素，如果元素2>元素1（或任何你想testing的）增加一个计数器，然后除以总数的元素。 它应该给你一个百分比。
我会计数比较，并将其分为比较的总数。 这是一个简单的Python示例。
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
这样的事情呢？
#!/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()
如果你拿你的清单，计算列表中的值的等级，并调用等级列表Y和另一个列表X ，包含从1到length(Y)的整数，你可以精确地获得你所sorting的度量通过计算两个列表之间的相关系数 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}}
对于完全sorting的列表， r = 1.0 ，对于逆sorting列表， r=-1.0 ，并且对于不同程度的sorting， r=-1.0在这些限制之间变化。
这种方法的一个可能的问题，根据应用程序的不同，计算列表中每个项目的排名等同于对它进行sorting，因此它是O（n log n）操作。