Häufig verwendete Blasensortierungs- und Schnellsortierungsalgorithmen sowie die Implementierung von binären Such- und sequentiellen Suchalgorithmen in PHP

Der Inhalt dieses Artikels befasst sich mit dem häufig verwendeten Blasensortierungs- und Schnellsortierungsalgorithmus sowie der Implementierung des binären Such- und sequentiellen Suchalgorithmus. Ich hoffe, er wird Ihnen helfen .

1. Blasensortierung

Grundidee:

Sortieren Sie das Array von hinten nach vorne (umgekehrte Reihenfolge). Führen Sie mehrere durch Scans, und wenn festgestellt wird, dass die Reihenfolge zweier benachbarter Werte nicht mit den für die Sortierung erforderlichen Regeln übereinstimmt, werden die beiden Werte ausgetauscht. Auf diese Weise bewegen sich die kleineren (größeren) Werte allmählich von hinten nach vorne.

<?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. Schnelle Sortierung

Grundidee:

Ein Element im Array auswählen (meistens das erste) Scannen Sie als Lineal das Array einmal und sortieren Sie die Elemente, die kleiner als das Lineal sind, vor dem Lineal, sortieren Sie alle Elemente, die größer als das Lineal sind, nach dem Lineal und teilen Sie jede Teilsequenz durch Rekursion in kleinere Sequenzen auf, bis alle Sequenzen in derselben Reihenfolge sind . .

<?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. Binäre Suche

Grundidee:

Angenommen, die Daten sind in aufsteigender Reihenfolge sortiert, z Bei gegebenem Wert x ist die Suche ab der mittleren Position der Sequenz erfolgreich. Wenn x kleiner als der aktuelle Positionswert ist, erfolgt die Suche in der ersten Hälfte der Sequenz x ist größer als der aktuelle Positionswert, die Suche erfolgt in der zweiten Hälfte der Sequenz. Suchen Sie weiter, bis Sie es finden. (Wird verwendet, wenn die Datenmenge groß ist)

<?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. Sequentielle Suche

Grundidee:

Von der Das erste Element im Array wird nacheinander nach unten durchsucht. Wenn ein Element vorhanden ist, das mit dem Ziel übereinstimmt, ist die Suche erfolgreich. Wenn bis zum letzten Element noch kein Zielelement vorhanden ist, schlägt die Suche fehl.

<?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. Schreiben Sie eine Funktion, die alle Dateien und Unterordner unter einer Datei durchlaufen kann

<?php  
function my_scandir($dir)
{
$files = array();
if($handle = opendir($dir))
{
while (($file = readdir($handle))!== false) 
{
if($file != &#39;..&#39; && $file != &#39;.&#39;)
{
if(is_dir($dir."/".$file))
{
$files[$file]=my_scandir($dir."/".$file);
}
else
{
$files[] = $file;
}
}
}
closedir($handle);
return $files;
}
}
var_dump(my_scandir(&#39;../&#39;));
?>		

6. Schreiben Sie eine Funktion, die so effizient wie möglich ist Get die Dateierweiterung von einer Standard-URL

<?php
function getExt($url)
{
$arr = parse_url($url);//parse_url解析一个 URL 并返回一个关联数组，包含在 URL 中出现的各种组成部分
//&#39;scheme&#39; => string &#39;http&#39; (length=4)
//&#39;host&#39; => string &#39;www.sina.com.cn&#39; (length=15)
//&#39;path&#39; => string &#39;/abc/de/fg.php&#39; (length=14)
//&#39;query&#39; => string &#39;id=1&#39; (length=4)
$file = basename($arr[&#39;path&#39;]);// basename函数返回路径中的文件名部分
$ext = explode(&#39;.&#39;, $file);
 return $ext[count($ext)-1];
}
print(getExt(&#39;http://www.sina.com.cn/abc/de/fg.html.php?id=1&#39;));
?>

7. Methode zum Abfangen chinesischer Zeichenfolgen ohne verstümmelte Zeichen

Sie können mb_substr verwenden, müssen aber php_mbstring sicherstellen .dll wird in php.ini geladen, das heißt, stellen Sie sicher, dass die Zeile „extension=php_mbstring.dll“ vorhanden und nicht auskommentiert ist, da sonst undefinierte Funktionsprobleme auftreten.

Verwandte Empfehlungen:

PHP-Blasensortierung, PHP-Blasensortierung

Blasensortierung in PHP, Kompromisssortierung, Einfügungssortierung

Das obige ist der detaillierte Inhalt vonHäufig verwendete Blasensortierungs- und Schnellsortierungsalgorithmen sowie die Implementierung von binären Such- und sequentiellen Suchalgorithmen in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!