Wie kann der Fisher-Yates-Shuffle ein zufälliges Shuffling in linearer Zeit erreichen?

Fisher-Yates-Shuffling-Algorithmus: ein linearer Zeit-Shuffling-Algorithmus

Effizienz ist entscheidend beim zufälligen Sortieren einer Liste von Ganzzahlen. Obwohl die ursprüngliche Methode in der Frage versucht, Zufälligkeit zu erreichen, kann es während der Verarbeitung zu Effizienzproblemen kommen, insbesondere gegen Ende.

Eine effizientere Lösung ist der Fisher-Yates-Shuffling-Algorithmus, ein linearer Zeitalgorithmus, der eine wirklich zufällige Neuordnung der Eingabeliste gewährleistet. Im Gegensatz zum ursprünglichen Ansatz, der auf einem booleschen Array beruhte, um die vertauschten Elemente zu verfolgen, verfolgt der Fisher-Yates-Shuffling-Algorithmus einen einfacheren Ansatz.

<code class="language-c#">for (int i = iItemCount - 1; i >= 1; i--)
{
    int j = random.Next(i + 1);
    int temp = values[j];
    values[j] = values[i];
    values[i] = temp;
}</code>

Der Algorithmus funktioniert, indem er das aktuelle Element wiederholt mit einem zuvor zufällig ausgewählten Element in der Liste austauscht. Während der Algorithmus fortschreitet, schränkt er den Bereich der unsortierten Elemente ein, wodurch die gesamte Liste in O(n)-Zeit effektiv gemischt wird.

Mit dem Fisher-Yates-Shuffling-Algorithmus können Sie eine Liste von Ganzzahlen effizient und zufällig neu anordnen und so die potenziellen Fallstricke des ursprünglichen Algorithmus vermeiden.

Das obige ist der detaillierte Inhalt vonWie kann der Fisher-Yates-Shuffle ein zufälliges Shuffling in linearer Zeit erreichen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!