Quelles sont les stratégies d'optimisation et les méthodes d'implémentation de l'algorithme de tri rapide en PHP ?

Quelles sont les stratégies d'optimisation et les méthodes d'implémentation de l'algorithme de tri rapide en PHP ?

Le tri rapide est un algorithme de tri courant. Son idée de base est de sélectionner un élément comme valeur de référence et de diviser le tableau en deux parties, une partie est plus petite que la valeur de référence et l'autre partie est supérieure à la valeur de référence. Triez ensuite rapidement les deux parties séparément jusqu'à ce que l'ensemble du tableau soit trié. Lors de la mise en œuvre du tri rapide, les performances de l'algorithme peuvent être améliorées grâce à des stratégies d'optimisation.

Plusieurs stratégies d'optimisation et méthodes de mise en œuvre seront présentées ci-dessous, et des exemples de code PHP spécifiques seront fournis.

1. Sélectionnez aléatoirement la valeur de référence
   Dans le tri rapide, la sélection de la valeur de référence a un grand impact sur les performances de l'algorithme. Si le premier ou le dernier élément est sélectionné comme valeur de référence à chaque fois, alors lorsque le tableau lui-même est ordonné ou approximativement ordonné, la complexité temporelle de l'algorithme atteindra O (n ^ 2). Pour éviter cette situation, nous pouvons sélectionner au hasard un élément comme valeur de base, réduisant ainsi la probabilité du pire des cas.

Exemple de code :

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

2. Méthode de recherche du milieu de trois nombres
   Lors de la sélection d'une valeur de référence, éviter de sélectionner la valeur minimale ou maximale du tableau peut améliorer les performances de l'algorithme. Une méthode courante pour prendre la valeur de base consiste à utiliser la « méthode à trois nombres », c'est-à-dire à sélectionner trois éléments au début, au milieu et à la fin du tableau, puis à prendre la valeur du milieu comme valeur de base.

Exemple de code :

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

En adoptant des stratégies d'optimisation telles que la sélection aléatoire de la valeur de référence et la prise au milieu de trois nombres, les performances de l'algorithme de tri rapide peuvent être améliorées et la probabilité du pire des cas peut être réduite. Ces stratégies d’optimisation sont particulièrement importantes pour améliorer l’efficacité des algorithmes si elles sont appliquées au tri d’ensembles de données à grande échelle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!