Implementierung des Sortieralgorithmus PHP Hill (Shell) (detaillierte Codeerklärung)

Hill (Shell)-Sortierung oder Shell-Methode ist eine direkte Vergleichssortierung. Es kann als eine Verallgemeinerung von Bubble Sort oder Insertion Sort angesehen werden. Diese Methode sortiert zunächst weit voneinander entfernte Elementpaare und schließt dann nach und nach die Lücke zwischen den zu vergleichenden Elementen. Wenn Sie mit Elementen beginnen, die weit voneinander entfernt sind, können Sie einige fehl am Platz liegende Elemente schneller verschieben als durch den Austausch von Nachbarn.

Beispiel für die Shell-Sortierung lautet wie folgt:

Der erste Durchlauf ist „5-Sortierung“. " , Führe eine Einfügungssortierung für verschiedene Subarrays durch (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Beispielsweise wird das Subarray (a1, a6, a11) von (62,17,25) in (17,25,62) geändert.

Dann „3 sortieren“, Einfügesortierung für die Subarrays (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12) durchführen.

Das letzte Mal ist „1 Sortierung“, also das gesamte Array (a1,...,a12). Wie im Beispiel gezeigt, sind die Subarrays von Shell-Sortieroperationen zunächst sehr kurz, später werden sie länger, sind aber grundsätzlich geordnet. In beiden Fällen funktioniert die Einfügungssortierung. Shell-Sortierung ist instabil: Sie kann die relative Reihenfolge von Elementen mit gleichen Werten ändern. Es handelt sich um einen adaptiven Sortieralgorithmus, der schneller arbeitet, wenn die Eingabe teilweise sortiert ist.

Die Hill (Shell)-Sortierungsgrafik sieht wie folgt aus:

Codebeispiel für PHP, das den Shell (Shell)-Sortieralgorithmus implementiert:

<?php
function shell_Sort($my_array)
{
    $x = round(count($my_array)/2);
    while($x > 0)
    {
        for($i = $x; $i < count($my_array);$i++){
            $temp = $my_array[$i];
            $j = $i;
            while($j >= $x && $my_array[$j-$x] > $temp)
            {
                $my_array[$j] = $my_array[$j - $x];
                $j -= $x;
            }
            $my_array[$j] = $temp;
        }
        $x = round($x/2.2);
    }
    return $my_array;
}

$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,shell_Sort($test_array)). PHP_EOL;

Ausgabe:

原始数组 : 3, 0, 2, 5, -1, 4, 1 
排序后数组 :-1, 0, 1, 2, 3, 4, 5

Dieser Artikel ist eine Einführung in den Sortieralgorithmus von PHP Hill (Shell). Ich hoffe, dass er für Freunde in Not hilfreich ist !

Das obige ist der detaillierte Inhalt vonImplementierung des Sortieralgorithmus PHP Hill (Shell) (detaillierte Codeerklärung). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!