Maison > Article > développement back-end > Algorithmes de tri à bulles et de tri rapide couramment utilisés et implémentation d'algorithmes de recherche binaire et de recherche séquentielle en PHP
Le contenu de cet article concerne l'algorithme de tri à bulles et de tri rapide couramment utilisé et l'implémentation de l'algorithme de recherche binaire et de recherche séquentielle en PHP. Il a une certaine valeur de référence. J'espère que cela vous aidera. .
1. Tri des bulles
Idée de base :
Trier le tableau de l'arrière vers l'avant (ordre inverse) Effectuer plusieurs scans, et lorsqu'il s'avère que l'ordre de deux valeurs adjacentesest incompatible avec les règles requises pour le tri, les deux valeurssont échangées. De cette façon, les valeurs plus petites (plus grandes) se déplaceront progressivement de l'arrière vers l'avant.
<?php function mysort($arr) { for($i = 0; $i < count($arr); $i++) { $isSort = false; for ($j=0; $j< count($arr) - $i - 1; $j++) { if($arr[$j] < $arr[$j+1]) { $isSort = true; $temp = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $temp ; } } if($isSort) { break; } } return $arr; } $arr = array(3,1,2); var_dump(mysort($arr)); ?>
2. Tri rapide
Idée de base :
Sélectionnez un élément dans le tableau (principalement le premier un) en tant que règle, scannez le tableau et triez les éléments plus petits que la règle avant la règle, et triez tous les éléments plus grands que la règle après la règle, et divisez chaque sous-séquence en séquences plus petites par récursion jusqu'à ce que toutes les séquences soient L'ordre est cohérent.
<?php //快速排序 function quick_sort($arr) { //先判断是否需要继续进行 $length = count($arr); if($length <= 1) { return $arr; } $base_num = $arr[0];//选择一个标尺 选择第一个元素 //初始化两个数组 $left_array = array();//小于标尺的 $right_array = array();//大于标尺的 for($i=1; $i<$length; $i++) { //遍历 除了标尺外的所有元素,按照大小关系放入两个数组内 if($base_num > $arr[$i]) { //放入左边数组 $left_array[] = $arr[$i]; } else { //放入右边 $right_array[] = $arr[$i]; } } //再分别对 左边 和 右边的数组进行相同的排序处理方式 //递归调用这个函数,并记录结果 $left_array = quick_sort($left_array); $right_array = quick_sort($right_array); //合并左边 标尺 右边 return array_merge($left_array, array($base_num), $right_array); } $arr = array(3,1,2); var_dump(quick_sort($arr)); ?>
3. Recherche binaire
Idée de base :
En supposant que les données sont triées par ordre croissant, pour le donné Définissez la valeur x, démarrez la comparaison à partir de la position médiane de la séquence, si la valeur de la position actuelle est égale à Continuez à chercher jusqu'à ce que vous la trouviez. (À utiliser lorsque la quantité de données est importante)
<?php //二分查找 function bin_search($arr,$low,$high,$k) { if($low <= $high) { $mid = intval(($low + $high)/2); if($arr[$mid] == $k) { return $mid; } else if($k < $arr[$mid]) { return bin_search($arr,$low,$mid-1,$k); } else { return bin_search($arr,$mid+1,$high,$k); } } return -1; } $arr = array(1,2,3,4,5,6,7,8,9,10); print(bin_search($arr,0,9,3)); ?>
4. Recherche séquentielle
Idée de base :
À partir du tableau Commencez la recherche vers le bas un par un à partir du premier élément. S'il existe un élément cohérent avec la cible, la recherche réussit. S'il n'y a toujours pas d'élément cible jusqu'au dernier élément, la recherche échoue.
<?php //顺序查找 function seq_search($arr,$n,$k) { $array[$n] = $k; for($i = 0;$i < $n; $i++) { if($arr[$i] == $k) { break; } if($i < $n) { return $i; } else { return -1; } } ?>
5. Écrivez une fonction qui peut parcourir tous les fichiers et sous-dossiers d'un fichier
<?php function my_scandir($dir) { $files = array(); if($handle = opendir($dir)) { while (($file = readdir($handle))!== false) { if($file != '..' && $file != '.') { if(is_dir($dir."/".$file)) { $files[$file]=my_scandir($dir."/".$file); } else { $files[] = $file; } } } closedir($handle); return $files; } } var_dump(my_scandir('../')); ?>
6. Écrivez une fonction, obtenez le extension de fichier à partir d'une URL standard aussi efficacement que possible
<?php function getExt($url) { $arr = parse_url($url);//parse_url解析一个 URL 并返回一个关联数组,包含在 URL 中出现的各种组成部分 //'scheme' => string 'http' (length=4) //'host' => string 'www.sina.com.cn' (length=15) //'path' => string '/abc/de/fg.php' (length=14) //'query' => string 'id=1' (length=4) $file = basename($arr['path']);// basename函数返回路径中的文件名部分 $ext = explode('.', $file); return $ext[count($ext)-1]; } print(getExt('http://www.sina.com.cn/abc/de/fg.html.php?id=1')); ?>
7. Méthodes pour intercepter les chaînes chinoises sans caractères tronqués
Oui Utilisez mb_substr, mais vous Vous devez vous assurer que php_mbstring.dll est chargé dans php.ini, c'est-à-dire vous assurer que la ligne "extension=php_mbstring.dll" existe et n'est pas commentée, sinon des problèmes de fonction non définis se produiront.
Recommandations associées :
Tri des bulles PHP, Tri des bulles php
Tri des bulles en php, Tri des compromis, tri par insertion
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!