有没有一种方法可以衡量列表的排序方式？
有没有一种方法可以衡量列表的排序方式？
我的意思是，这不是要知道列表是否已排序（布尔值），而是诸如“排序”之比，诸如统计中的相关系数之类的东西。
例如，
如果列表中的项目按升序排列，则其比率为1.0
如果列表降序排列，则其速率将为-1.0
如果list几乎升序排列，则其比率将是0.9或接近1的某个值。
如果列表根本不排序（随机），则其比率将接近0
我正在Scala中写一个小型图书馆进行练习。我认为排序速率会很有用，但是我找不到有关此类信息的任何信息。也许我不知道这个概念的适当术语。
您可以简单地计算列表中的反转次数。
反演
类型的元素序列中的一个反转T是一对序列元素，它们根据<的集合上的某些顺序乱序出现T。
从维基百科：
正式地，让数字
A(1), A(2), ..., A(n)序列n。
如果i < j和A(i) > A(j)，然后在一对(i,j)被称为反转的A。的反转数的序列的是它的有序性的一个公共量度。
形式上，将反转数定义为反转数，即
为了使这些定义更清楚，请考虑示例序列9, 5, 7, 6。该序列具有反演 (0,1), (0,2), (0,3), (2,3)和反演编号 4。
如果您想要介于0和之间的值1，则可以将反转数除以N choose 2。
要实际创建一种算法来计算此分数对列表的排序方式，您有两种方法：
方法1（确定性）
修改您喜欢的排序算法，以跟踪其运行时正在纠正的反转次数。尽管这是不平凡的，并且根据您选择的排序算法有不同的实现方式，但最终您得到的算法（就复杂性而言）不会比开始时使用的排序算法昂贵。
如果您采用这种方法，请注意，这并不像计算“掉期”那么简单。例如，Mergesort是最坏的情况O(N log N)，但是如果它在以降序排列的列表上运行，它将纠正所有N choose 2反转。O(N^2)在O(N log N)操作中纠正了这种反转。因此，某些操作不可避免地必须一次校正多个反转。您必须小心执行。注意：您可以非常O(N log N)复杂地完成此操作，这很棘手。
相关：计算排列中的“反转”数
方法2（随机）
- 随机抽样对
(i,j)，其中i != j - 对于每对，确定是
list[min(i,j)] < list[max(i,j)]（0还是1） - 计算这些比较的平均值，然后通过
N choose 2
除非您对准确性有要求，否则我个人会采用随机方法-仅仅是因为它是如此容易实现。
如果您真正想要的是（降序排列）到（升序排列z'）之间的值（），则可以使用此公式将（升序）和（降序排列）之间的（）以上的值映射到该范围：-11z01
z' = -2 * z + 1
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
有没有一种方法可以衡量iOS中的延迟？
- 2
有没有一种方法可以衡量javascript cpu处理滞后
- 3
有没有一种方法可以使用索引对列表列表进行排序？
- 4
Python：有没有一种方法可以将随机数按排序方式保存在列表中？
- 5
有没有一种方法可以衡量缓存一致性未命中
- 6
有没有一种方法引用的降序排序方式？
- 7
有没有一种方法引用的降序排序方式？
- 8
有没有一种方法可以衡量Google BigQuery中的字符串相似度
- 9
有没有一种方法可以对列表中的颜色元素进行排序（C＃）？
- 10
有没有一种方法可以在Python 3+中对嵌套列表进行排序？
- 11
有没有一种方法可以以异步方式运行Database.SqlQuery？
- 12
有没有一种方法可以以异步方式运行Database.SqlQuery？
- 13
有没有一种方法可以控制缩略图的呈现方式？
- 14
有没有一种方法可以阻止表格在R中排序
- 15
有没有一种方法可以对子数组的张量进行排序？
- 16
有没有一种方法可以阻止表格在R中排序
- 17
有没有一种方法可以对拆分的数组进行排序？
- 18
有没有一种方法可以“遍历列表”？
- 19
有没有一种方法可以将列表理解重写为for循环？
- 20
有没有一种方法可以通过索引合并多个列表索引？
- 21
Erlydtl：有没有一种方法可以渲染模板中的记录列表？
- 22
有没有一种方法可以比较两个列表与流？
- 23
Python：有没有一种方法可以漂亮地打印列表？
- 24
有没有一种方法可以刷新VSCode中的任务列表？
- 25
有没有一种方法可以使Python列表需要某个对象？
- 26
有没有一种方法可以合并R中的回归摘要列表？
- 27
切片时，有没有一种方法可以从列表的末尾开始？
- 28
有没有一种方法可以遍历列表并分配变量
- 29
有没有一种方法可以将列表放入Python集？
我来说两句