Quels sont les algorithmes de base de PHP ?

Beaucoup de gens disent que les algorithmes sont au cœur des programmes. La clé pour savoir si un programme est bon ou mauvais est la qualité de son algorithme. En tant que PHPer junior, même si je suis peu exposé aux choses algorithmiques. Mais je pense que nous devons encore maîtriser les quatre algorithmes de base que sont le tri à bulles, le tri par insertion, le tri par sélection et le tri rapide.

Recommandations associées : "Tutoriel PHP"

Exigences : Utilisez respectivement le tri par bulles, le tri rapide et le tri par sélection. La méthode de tri par insertion trie les valeurs du tableau ci-dessous par ordre croissant.

$arr=array(11,3,56,62,21,66,32,78,36,76,39,88,34);

1. Le tri à bulles

Introduction :

Le tri à bulles (Bubble Sort, traduction taïwanaise : tri à bulles ou tri à bulles) est un tri simple. algorithme. Il parcourt à plusieurs reprises la séquence à trier, en comparant les deux éléments tour à tour et en les échangeant s'ils sont dans le mauvais ordre. Le travail de visite du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié. Le nom de cet algorithme vient du fait que les éléments plus petits « flotteront » lentement vers le haut du tableau grâce à l’échange.

Étapes :

1. Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-les tous les deux.

2. Faites le même travail pour chaque paire d'éléments adjacents, de la première paire au début à la dernière paire à la fin. À ce stade, le dernier élément doit être le plus grand nombre.

3. Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.

4. Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paires de nombres à comparer.

Code spécifique :

$arr=array(1,43,54,62,21,66,32,78,36,76,39);
function bubbleSort ($arr)
{
$len = count($arr);
//该层循环控制 需要冒泡的轮数
for ($i=1; $i<$len; $i++) {
//该层循环用来控制每轮 冒出一个数 需要比较的次数
for ($k=0; $k<$len-$i; $k++) {
if($arr[$k] > $arr[$k+1]) {
$tmp = $arr[$k+1]; // 声明一个临时变量
$arr[$k+1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}

Effet de tri :

2. Sélectionnez le tri

Introduction :

Le tri par sélection est un algorithme de tri simple et intuitif. Voici comment cela fonctionne. Tout d'abord, recherchez le plus petit élément de la séquence non triée et stockez-le au début de la séquence triée. Ensuite, continuez à rechercher le plus petit élément parmi les éléments non triés restants, puis placez-le à la fin de la séquence triée. Et ainsi de suite jusqu'à ce que tous les éléments soient triés.

Code spécifique :

//实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数
function select_sort($arr) {
//$i 当前最小值的位置， 需要参与比较的元素
for($i=0, $len=count($arr); $i<$len-1; $i++) {
//先假设最小的值的位置
$p = $i;
//$j 当前都需要和哪些元素比较，$i 后边的。
for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是 当前已知的最小值
if($arr[$p] > $arr[$j]) {
//比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。
$p = $j;
}
}
//已经确定了当前的最小值的位置，保存到$p中。
//如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//返回最终结果
return $arr;
}

Effet de tri :

Tri par insertion

Introduction :

La description de l'algorithme de tri par insertion est un algorithme de tri simple et intuitif. Il fonctionne en construisant une séquence ordonnée. Pour les données non triées, il analyse d'arrière en avant dans la séquence triée pour trouver la position correspondante et l'insérer. Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui n'utilise que l'espace supplémentaire O(1). Par conséquent, pendant le processus de numérisation d'arrière en avant, il est nécessaire de décaler de manière répétée et progressive le tri par insertion. éléments triés vers l'arrière, fournissant un espace d'insertion pour le dernier élément.

Étapes :

1. En partant du premier élément, l'élément peut être considéré comme ayant été trié

2. Sortir l'élément suivant, après le trié Scannez d'arrière en avant dans la séquence d'éléments

3. Si l'élément (trié) est plus grand que le nouvel élément, déplacez l'élément à la position suivante

4. étape 3, jusqu'à ce que vous trouviez une position où l'élément trié est inférieur ou égal au nouvel élément

5 Insérez le nouvel élément dans la position

6.

Code spécifique :

function insert_sort($arr)
{
$len=count($arr);
for($i=1; $i<$len; $i++) {
//获得当前需要比较的元素值。
$tmp = $arr[$i];
//内层循环控制 比较 并 插入
for($j=$i-1; $j>=0; $j--) {
//$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
if($tmp < $arr[$j]) {
//发现插入的元素要小，交换位置
//将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
//将前面的数设置为 当前需要交换的数
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素
//由于是已经排序好是数组，则前面的就不需要再次比较了。
break;
}
}
}
//将这个元素 插入到已经排序好的序列内。
//返回
return $arr;
}

Effet de tri :

Tri rapide

Introduction :

Tri rapide Il s'agit d'un algorithme de tri développé par Tony Hall. En moyenne, le tri de n éléments nécessite des comparaisons O(n log n). Dans le pire des cas, des comparaisons O(n2) sont nécessaires, mais cette situation est rare. En fait, le tri rapide est souvent beaucoup plus rapide que les autres algorithmes Ο(n log n), car sa boucle interne peut être implémentée efficacement sur la plupart des architectures et fonctionne bien sur la plupart des applications du monde réel. Les données peuvent déterminer les choix de conception, réduisant ainsi la possibilité de termes quadratiques. dans le temps requis.

Étapes :

1. Choisissez un élément de la séquence, appelé le "pivot",

2. Réorganisez la séquence, tous les éléments étant plus petits que le. la valeur de base est placée devant la base, et tous les éléments plus grands que la valeur de base sont placés derrière la base (le même nombre peut aller de chaque côté). Une fois cette partition terminée, la base se trouve au milieu de la séquence. C'est ce qu'on appelle une opération de partition.

3. Triez de manière récursive le sous-tableau d'éléments plus petits que la valeur de base et le sous-tableau d'éléments supérieurs à la valeur de base.

Code spécifique :

function quick_sort($arr)
{
//判断参数是否是一个数组
if(!is_array($arr)) return false;
//递归出口:数组长度为1，直接返回数组
$length = count($arr);
if($length<=1) return $arr;
//数组元素有多个,则定义两个空数组
$left = $right = array();
//使用for循环进行遍历，把第一个元素当做比较的对象
for($i=1; $i<$length; $i++)
{
//判断当前元素的大小
if($arr[$i]<$arr[0]){
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//递归调用
$left=quick_sort($left);
$right=quick_sort($right);
//将所有的结果合并
return array_merge($left,array($arr[0]),$right);
}

Effet de tri :

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!