php ?-?@amazeUI ?-?2016-11-28 11:45:31
??? 二分查找和快速排序思想上有很大的相似度，就是做一個起始點，開始往左右做動作，也同樣是由遞歸實現(xiàn)，當然也可以不用遞歸實現(xiàn)。但是我覺得也不能用php內(nèi)置特有的函數(shù)- -，我找了很多php的快速排序，幾乎都用到了array_merge函數(shù)。當然使用的array_merge函數(shù)里的那個快速排序也是快排思想- -。
public function quickSort($left,$right,&$arr)
{
$l= $left;
$r= $right;
$pivot= $arr[($left + $right)/ 2];
$temp= 0;
while ($l< $r) {
while ($arr[$l]< $pivot) {
$l++;
}
while ($arr[$r]> $pivot) {
$r--;
}
if ($l>= $r) {
break;
}
$temp= $arr[$l];
$arr[$l]= $arr[$r];
$arr[$r]= $temp;
if ($arr[$l]== $pivot) {
--$r;
}
if ($arr[$r]== $pivot) {
++$l;
}
}
if ($l== $r) {
$l++;
$r--;
}
if ($left < $r) {
self::quickSort($left, $r,$arr);
}
if ($right > $l) {
self::quickSort($l,$right,$arr);
}
}
下面是二分查找:
摸索二分查找法，對于php數(shù)組而言，要找一個值太容易了，array_search一下就好了。二分查找又叫做折半查找。假設(shè)我在紙上寫了一個整數(shù)，在零到一百之間，需要你來猜我紙上寫的到底是幾，這個怎么猜？最快速的辦法就是做二分查找，假設(shè)紙上的數(shù)字為10，已知范圍為0到100，先將范圍值折半，猜50，再詢問50是比紙上的數(shù)字大還是小，答案是小了，再將范圍值縮小至0-50，再次折半，猜25。。。這樣才是最快的方式。用代碼實現(xiàn)二分查找法，基本有兩個方式，一個是遞歸，一個是while循環(huán)。我選擇用遞歸，遞歸的方式更直白和簡單，更符合以上所說邏輯，好理解。
//$search 函數(shù) $array為數(shù)組，$K為要找的值，$low為查找范圍的最小鍵值，$high為查找范圍的最大鍵值
public function binarySearch($array, $k, $low = 0, $high = 0)
{
//判斷數(shù)組元素的數(shù)量
echo 1;
if (count($array) != 0 and $high == 0) {????? //判斷是否為第一次調(diào)用
//數(shù)組的元素個數(shù)
$high = count($array);
}
if ($low <= $high) {????? //如果還存在剩余的數(shù)組元素
$mid = intval(($low + $high) / 2);????? //取$low 與$high的中間值3
//return $array[$mid];
if ($array[$mid] == $k) {
return $mid;??? //如果找到則返回
} elseif ($array[$mid] > $k) {//如果要找的值小于中間值
//如果上面沒有找到，則繼續(xù)查找
return self::binarySearch($array, $k, $low, $mid - 1);
} else {
return self::binarySearch($array, $k, $mid + 1, $high);//5-11,8-11,9-11,10-11,10+11/2再取整還是10，開始死循環(huán)---
}
}
return "沒有要查找的值";
}
