首頁 > 文章 > 後端開發 > php中常用的冒泡排序&快速排序演算法以及二分查找&順序查找的演算法實現

php中常用的冒泡排序&快速排序演算法以及二分查找&順序查找的演算法實現

不言原創: 2018-08-22 16:34:371489瀏覽

這篇文章帶給大家的內容是關於php中常用的冒泡排序&快速排序演算法以及二分查找&順序查找的演算法實現，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

一、冒泡排序

基本思想：

對需要排序的陣列從後往前（逆序）進行多遍的掃描，當發現相鄰的兩個數值的次序與排序要求的規則不一致時，就將這兩個數值進行交換。這樣比較小（大）的數值就將逐漸從後面往前面移動。

<?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));
?>

二、快速排序

基本思想：

在陣列中挑出一個元素（多為第一個）作為標尺，掃描一遍數組將比標尺小的元素排在標尺之前，將所有比標尺大的元素排在標尺之後，通過遞歸將各子序列分別劃分為更小的序列直到所有的序列順序一致。

<?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));
?>

三、二分查找

基本概念：

假設資料是按升序排序的，對於給定值x，從序列的中間位置開始比較，如果當前位置值等於x，則查找成功；若x小於當前位置值，則在數列的前半段中查找；若x大於當前位置值則在數列的後半段中繼續查找，直到找到為止。（資料量大的時候使用）

<?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));
?>

四、順序找出

#基本思想：

從陣列的第一個元素開始一個一個向下查找，如果有和目標一致的元素，查找成功；如果到最後一個元素仍沒有目標元素，則查找失敗。

<?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;
}
}
?>

五、寫一個函數，能夠遍歷一個檔案下的所有檔案和子資料夾

<?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;));
?>

六、寫一個函數，盡可能高效的從一個標準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;));
?>

七、實作中文字串截取無亂碼的方法

可使用mb_substr,但是要確保在php.ini中載入了php_mbstring.dll，即確保「extension=php_mbstring.dll」這一行存在並且沒有被註解掉，否則會出現未定義函數的問題。

php中常用的冒泡排序&快速排序演算法以及二分查找&順序查找的演算法實現

相關文章