排序
冒泡排序
依次比較相鄰的兩個數(shù)，將比較小的數(shù)放在前面，比較大的數(shù)放在后面。
$arr = [8,1,10,9,5,7];
function bubbleSort($arr){
// 外層 for 循環(huán)控制循環(huán)次數(shù)
for ($i=0; $i<count($arr) ; $i++) {
//內(nèi)層 for 循環(huán)進行兩數(shù)交換，找每次的最大數(shù)，排到最后
for ($j=0; $j < count($arr)-1; $j++) {
//數(shù)組里第一個和第二個對比，如果1>2，執(zhí)行數(shù)值互換
if($arr[$j] >$arr[$j+1]){
$x = $arr[$j]; //第一賦給一個變量
$arr[$j] = $arr[$j+1]; //第二賦給第一
$arr[$j+1] = $x; //把變量給第二，結(jié)果就是1，2的數(shù)值互換
// $a=10;
// $b=20;
// $x=$a; $x=10
// $a=$b; $a=20
// $b=$X; $b=10
}
}
}
return $arr;
}
print_r(bubbleSort($arr));
快速排序
快速排序是對冒泡排序的一種改進。
設(shè)置一個基準元素，通過排序?qū)⑿枰判虻臄?shù)據(jù)分割成兩個部分，其中一部分的所有數(shù)據(jù)比基準元素小，另一部分的所有數(shù)據(jù)比基準元素大，然后對這兩部分數(shù)據(jù)分別進行遞歸快速排序，最后將得到的數(shù)據(jù)和基準元素進行合并，就得到了所需數(shù)據(jù)。
$arr = [8,1,10,9,5,7];
function quickSort($arr){
$lenth = count($arr);//獲取數(shù)組個數(shù)
if($lenth <= 1){//小于等于一個不用往下走了
return $arr;
}
//選擇基準元素。一般選第一個或最后一個
$first = $arr[0];
$left = array();//接收小于基準元素的值
$right = array();//接收大于基準元素的值
//循環(huán)從1開始，因為基準元素是0
for($i=1;$i<$lenth;$i++){
if($arr[$i]<$first){//小于基準元素的值
$left[] = $arr[$i];
}else{//大于基準元素的值
$right[] = $arr[$i];
}
}
//遞歸排序
$left = quickSort($left);
$right = quickSort($right);
//合并返回數(shù)組
return array_merge($left,array($first),$right);
}
print_r(quickSort($arr));
選擇排序
1.找到數(shù)組中最小的元素，拎出來，將它和數(shù)組的第一個元素交換位置；
2.在剩下的元素中繼續(xù)尋找最小的元素，拎出來，和數(shù)組的第二個元素交換位置;
3.如此循環(huán)，直到整個數(shù)組排序完成。
$arr = [8,1,10,9,5,7];
function selectSort($arr){
//實現(xiàn)思路 雙重循環(huán)完成，外層控制輪數(shù)，當前的最小值。內(nèi)層 控制的比較次數(shù)，$i 當前最小值的位置， 需要參與比較的元素
for($i=0, $len=count($arr); $i<$len-1; $i++){
//先假設(shè)最小的值的位置
$p = $i;
//$j 當前都需要和哪些元素比較，$i 后邊的。
for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是 當前已知的最小值
if($arr[$p] > $arr[$j]){
//比較，發(fā)現(xiàn)更小的,記錄下最小值的位置；并且在下次比較時，應(yīng)該采用已知的最小值進行比較。
$p = $j;
}
}
//已經(jīng)確定了當前的最小值的位置，保存到$p中。如果發(fā)現(xiàn) 最小值的位置與當前假設(shè)的位置$i不同，則位置互換即可。
if($p != $i){
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}
print_r(selectSort($arr));
插入排序
每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。
$arr = [8,1,10,9,5,7];
function insertSort($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
$j = $i - 1;
while(isset($arr[$j]) && $arr[$j] > $tmp){
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
$j--;
}
}
return $arr;
}
print_r(insertSort($arr));
希爾排序
希爾排序(Shell Sort)是插入排序的一種，它是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。
希爾排序?qū)嵸|(zhì)上是一種分組插入方法。它的基本思想是：對于n個待排序的數(shù)列，取一個小于n的整數(shù)gap(gap被稱為步長)將待排序元素分成若干個組子序列，所有距離為gap的倍數(shù)的記錄放在同一個組中；然后，對各組內(nèi)的元素進行直接插入排序。 這一趟排序完成之后，每一個組的元素都是有序的。然后減小gap的值，并重復(fù)執(zhí)行上述的分組和排序。重復(fù)這樣的操作，當gap=1時，整個數(shù)列就是有序的。
$arr = [8,1,10,9,5,7];
function shellSort(&$arr){
if(!is_array($arr))return;$n=count($arr);
for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){
for($i=$gap;$i<$n;++$i){
for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){
$temp=$arr[$j];
$arr[$j]=$arr[$j+$gap];
$arr[$j+$gap]=$temp;
}
}
}
return $arr;
}
print_r(shellSort($arr));
查找
二分查找
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。
首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。文章來源：http://www.zghlxwxcb.cn/news/detail-706821.html
/**
* 二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常簡單，有點類似分治的思想。
* 二分查找針對的是一個有序的數(shù)據(jù)集合，每次都通過跟區(qū)間的中間元素對比，
* 將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間被縮小為 0。
*
* 循環(huán)寫法
* @param array $array 待查找的數(shù)組
* @param int $findVal 要查找的值
* @return int 返回找到的數(shù)組鍵
*/
function binarySearch($array, $findVal)
{
// 非數(shù)組或者數(shù)組為空，直接返回-1
if (!is_array($array) || empty($array)) {
return -1;
}
// 查找區(qū)間，起點和終點
$start = 0;
$end = count($array) - 1;
while ($start <= $end) {
// 以中間點作為參照點比較，取整數(shù)
$middle = intval(($start + $end) / 2);
if ($array[$middle] > $findVal) {
// 查找數(shù)比參照點小，則要查找的數(shù)在左半邊
// 因為 $middle 已經(jīng)比較過了，這里需要減1
$end = $middle - 1;
} elseif ($array[$middle] < $findVal) {
// 查找數(shù)比參照點大，則要查找的數(shù)在右半邊
// 因為 $middle 已經(jīng)比較過了，這里需要加1
$start = $middle + 1;
} else {
// 查找數(shù)與參照點相等，則找到返回
return $middle;
}
}
// 未找到，返回-1
return -1;
}
// 調(diào)用
$array = [10,12,16,19,20,34,56,78,84,95,100];
echo binarySearch($array, 84);
/**
* 遞歸寫法
* @param array $array 待查找的數(shù)組
* @param int $findVal 要查找的值
* @param int $start 查找區(qū)間，起點
* @param int $end 查找區(qū)間，終點
* @return int 返回找到的數(shù)組鍵
*/
function binSearch($array, $findVal, $start, $end)
{
// 以中間點作為參照點比較，取整數(shù)
$middle = intval(($start + $end) / 2);
if ($start > $end) {
return -1;
}
if ($findVal > $array[$middle]) {
// 查找數(shù)比參照點大，則要查找的數(shù)在右半邊
return binSearch($array, $findVal, $middle + 1, $end);
} elseif ($findVal < $array[$middle]) {
// 查找數(shù)比參照點小，則要查找的數(shù)在左半邊
return binSearch($array, $findVal, $start, $middle - 1);
} else {
return $middle;
}
}
// 調(diào)用
$arr = [10,12,16,19,20,34,56,78,84,95,100];
var_dump(binSearch($arr, 95, 0, count($arr)-1));
ps：未完待續(xù)文章來源地址http://www.zghlxwxcb.cn/news/detail-706821.html
到了這里，關(guān)于PHP常見算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
