链表排序:随机排序还是近似排序？

Question

我有一个链表，我想检查它是近似排序的还是随机的？有没有人能建议一下怎么做？

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

Answer 1

例如，如果你有100个项目，那么比例就会超过100。(列表排序量的分数。)如果你把所有的列表都排序好了，那么你的分数是100。如果列表是向后排序的，那么你的分数是0。您将检查每个相邻的元素，并决定是否对其进行排序(第0和1、1和2、2和3等等)。因此，您将有一个介于0和100之间的比例(或您的情况下的链表大小)。有很多关于“排序尺度”的启发式方法，但这可能是其中之一。

Answer 2

如果您希望涉及数据的振幅，您可以这样做(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