排序链接列表：随机或近似排序？

我有一个链表，我想检查它的近似排序或随机？任何人都可以建议如何做到这一点？排序链接列表：随机或近似排序？

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

2012-05-03 piyush0945

您使用哪种语言？ – Arion

您尚未定义“接近排序”的含义。几乎排序的 –

意味着有很多要排序的元素。几乎所有的元素都处于正确的位置。 – piyush0945

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

来源

2012-05-03 11:15:15 phantasmagoria

如果您想参与数据的幅度，你可以做（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

来源

2012-05-03 11:37:58

排序链接列表：随机或近似排序？

回答

相关问题