Maison > Article > développement back-end > 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.
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
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!