排序鏈接列表：隨機或近似排序？

我有一個鏈表，我想檢查它的近似排序或隨機？任何人都可以建議如何做到這一點？排序鏈接列表：隨機或近似排序？

現在我想要做的是運行到列表的一半，並比較相鄰的元素，以檢查給定列表是否接近排序或否則。但困難在於，這種方法並不完全可靠，我想要一些具體的東西。

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

排序鏈接列表：隨機或近似排序？

回答

相關問題