Was sind die Optimierungsstrategien und Implementierungsmethoden des Schnellsortierungsalgorithmus in PHP?-PHP-Tutorial-php.cn

Was sind die Optimierungsstrategien und Implementierungsmethoden des Schnellsortierungsalgorithmus in PHP?

王林

Freigeben： 2023-09-19 11:16:01

Original

934 Leute haben es durchsucht

Was sind die Optimierungsstrategien und Implementierungsmethoden des Schnellsortierungsalgorithmus in PHP?

Schnellsortierung ist ein gängiger Sortieralgorithmus. Seine Grundidee besteht darin, ein Element als Benchmark-Wert auszuwählen und das Array in zwei Teile zu teilen, wobei ein Teil kleiner als der Benchmark-Wert und der andere Teil größer als der Benchmark-Wert ist. Sortieren Sie dann die beiden Teile schnell getrennt, bis das gesamte Array sortiert ist. Bei der Implementierung einer schnellen Sortierung kann die Leistung des Algorithmus durch Optimierungsstrategien verbessert werden.

Im Folgenden werden verschiedene Optimierungsstrategien und Implementierungsmethoden vorgestellt und spezifische PHP-Codebeispiele bereitgestellt.

Benchmark-Wert zufällig auswählen
Bei der Schnellsortierung hat die Auswahl des Benchmark-Werts einen großen Einfluss auf die Leistung des Algorithmus. Wenn jedes Mal das erste oder letzte Element als Referenzwert ausgewählt wird und das Array selbst geordnet oder ungefähr geordnet ist, erreicht die zeitliche Komplexität des Algorithmus O (n ^ 2). Um diese Situation zu vermeiden, können wir ein Element zufällig als Basiswert auswählen und so die Wahrscheinlichkeit des Worst-Case-Szenarios verringern.

Beispielcode:

function partition($arr, $low, $high) {
    $pivot_index = rand($low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

Nach dem Login kopieren

Methode zum Ermitteln der Mitte von drei Zahlen
Bei der Auswahl eines Benchmark-Werts kann das Vermeiden der Auswahl des minimalen oder maximalen Werts des Arrays die Leistung des Algorithmus verbessern. Eine übliche Methode zum Ermitteln des Basiswerts besteht darin, die „Drei-Zahlen-Methode“ zu verwenden, dh drei Elemente am Anfang, in der Mitte und am Ende des Arrays auszuwählen und dann den Mittelwert als Basiswert zu verwenden.

Beispielcode:

function getPivotIndex($arr, $low, $high) {
    $mid = intval(($low + $high) / 2);
    
    if ($arr[$low] < $arr[$mid]) {
        if ($arr[$mid] < $arr[$high]) {
            return $mid;
        } else if ($arr[$high] < $arr[$low]) {
            return $low;
        } else {
            return $high;
        }
    } else {
        if ($arr[$low] < $arr[$high]) {
            return $low;
        } else if ($arr[$mid] < $arr[$high]) {
            return $high;
        } else {
            return $mid;
        }
    }
}

function partition($arr, $low, $high) {
    $pivot_index = getPivotIndex($arr, $low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

Nach dem Login kopieren

Durch die Anwendung von Optimierungsstrategien wie der zufälligen Auswahl des Benchmark-Werts und der Verwendung der mittleren von drei Zahlen kann die Leistung des Schnellsortierungsalgorithmus verbessert und die Wahrscheinlichkeit des Worst-Case-Szenarios verringert werden. Diese Optimierungsstrategien sind besonders wichtig, um die Effizienz des Algorithmus zu verbessern, wenn sie auf die Sortierung großer Datensätze angewendet werden.

Das obige ist der detaillierte Inhalt vonWas sind die Optimierungsstrategien und Implementierungsmethoden des Schnellsortierungsalgorithmus in PHP?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!