0

リンクされたリストがあり、ほぼソートされているかランダムかを確認したいですか? 誰かがそれを行う方法を提案できますか??

現在、私がやろうとしているのは、リストの半分まで実行し、隣接する要素を比較して、指定されたリストがほぼソートされているかどうかを確認することです。しかし、難しいのは、この方法は完全な証明ではなく、具体的なものが欲しいということです。

4

2 に答える 2

0

たとえば、項目が 100 の場合、スケールは 100 のうちになります。 (リストが並べ替えられている量のスコア。) すべてのリストが並べ替えられている場合、スコアは 100 です。リストが逆方向に並べ替えられている場合は、あなたのスコアは0です。隣接するそれぞれをチェックし、ペアがソートされているかどうかを判断します (0 番目と 1 番目、1 番目と 2 番目、2 番目と 3 番目など)。したがって、スケールは 0 から 100 (または場合によってはリンクされたリストのサイズ) になります。「ソートスケール」については多くのヒューリスティックがありますが、これはその1つかもしれません。

于 2012-05-03T11:15:15.893 に答える
0

データの振幅を含めたい場合は、次のことができます (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-03T11:37:58.093 に答える