sorting - 排序链表：随机还是接近排序？

Question

我有一个链表，我想检查它是几乎排序的还是随机的？任何人都可以建议如何做到这一点？

现在我要做的是运行到列表的一半并比较相邻元素以检查给定列表是否接近排序或其他。但困难在于这种方法不能完全证明，我想要一些具体的东西。

Answer 1

如果您想涉及数据的幅度，您可以执行以下操作（Python3）：

import random    
l = [random.random() for x in range(100)]
s = 0
for i,x in enumerate(l[0:50]):
    s += l[i+1] - x
print(s)

如果您只想查看排序了多少个值，请将s+=行替换为

    s += 1 if l[i+1] > x else 0

Answer 2

例如，如果您有 100 个项目，则比例将超出 100。（列表排序的分数。）如果您对所有列表进行排序，则得分为 100。如果列表向后排序，则你的分数是 0。您将检查每个相邻的并决定这对是否已排序（第 0 和第 1、第 1 和第 2、第 2 和第 3 等等）。因此，您将有一个介于 0 和 100 之间的比例（或您的案例的链表大小）。关于“排序规模”有很多启发式方法，但这可能是其中之一。