<?php
//二分查找法
function binSearch($arr, $search)
{
$height = count($arr) - 1;
$low = 0;
while ($low <= $height) {
$mid = floor(($low + $height) / 2);
//获取中间数
if ($arr[$mid] == $search) {
return $mid; //返回
} elseif ($arr[$mid] < $search) {
//当中间值小于所查值时，则$mid左边的值都小于$search，此时要将$mid赋值给$low
$low = $mid + 1;
} elseif ($arr[$mid] > $search) {
//中间值大于所查值,则$mid右边的所有值都大于$search,此时要将$mid赋值给$height
$height = $mid - 1;
}
}
return '查找失败';
}
//二分查找递归实现
function binSearch2($arr, $low, $height, $k)
{
if ($low <= $height) {
$mid = floor(($low + $height) / 2); //获取中间数
if ($arr[$mid] == $k) {
return $mid;
} elseif ($arr[$mid] < $k) {
return binSearch2($arr, $mid + 1, $height, $k);
} elseif ($arr[$mid] > $k) {
return binSearch2($arr, $low, $mid - 1, $k);
}
}
return '查找失败';
}
//顺序查找
function seqSearch($arr, $k)
{
foreach ($arr as $key => $val) {
if ($val == $k) {
return $key;
}
}
return -1;
}
$arr = array(1, 2, 3, 4);
echo binSearch($arr, 4).'<br/>';
echo binSearch2($arr, 0, 4, 4).'<br/>';
echo seqSearch($arr, 4).'<br/>';
echo in_array(4, $arr).'<br/>';
echo array_search(4, $arr);
<?php
/**
* 冒泡排序
* 思想：将数组中前后两个相邻的数值进行比较条件成立则交换.
* 缺点：替换次数多，效率低.
*/
function bubbleSort($arr)
{
// 第一层for循环可以理解为从数组中键为0开始循环到最后一个
for ($i = 0; $i < count($arr); ++$i) {
// 第二层将从键为$i的地方循环到数组最后
for ($j = $i + 1; $j < count($arr); ++$j) {
// 比较数组中相邻两个值的大小
if ($arr[$i] > $arr[$j]) {
$tmp = $arr[$i]; // 这里的tmp是临时变量
$arr[$i] = $arr[$j]; // 第一次更换位置
$arr[$j] = $tmp; // 完成位置互换
}
}
}
return $arr;
}
/**
* 选择排序
* 思想：假设第一个是最小的 ，循环与数组中第一个比较 ，如果比其还小 ， 则记录下标 进行数值交换
* 缺点：效率相比冒泡高.
*/
function selectionSort($array)
{
for ($i = 0; $i < count($array) - 1; ++$i) {
/*findtheminest*/
$min = $i;
for ($j = $i + 1; $j < count($array); ++$j) {
//由小到大排列
if ($array[$min] > $array[$j]) {
//表明当前最小的还比当前的元素大
$min = $j;
//赋值新的最小的
}
}
/*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
if ($min != $i) {
$temp = $array[$min];
$array[$min] = $array[$i];
$array[$i] = $temp;
}
}
return $array;
}
/**
* 插入排序
* 思想：将插入的数据保存在变量中，与数组中的每个数比较 找到合适的位置 进行插入
* 缺点： 效率相对来说比较高.
*/
function insertSort($arr)
{
for ($i = 0; $i < count($arr); ++$i) {
//当前要插入的值与下标
$insertVal = $arr[$i];
$insertIndex = $i - 1;
//判断当前的值是否大于0并且大于它要插入的数
while ($insertIndex >= 0 && $insertVal < $arr[$insertIndex]) {
$arr[$insertIndex + 1] = $arr[$insertIndex];
--$insertIndex;
}
$arr[$insertIndex + 1] = $insertVal;
}
return $arr;
}
/**
* 快速排序
* 思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列.
* 效率很高.
*/
function quickSort($arr)
{
if (count($arr) <= 1) {
return $arr;
}
$key = $arr[0]; // 第一个元素
$left_arr = array(); // 左边数组
$right_arr = array(); // 右边数组
for ($i = 1; $i < count($arr); ++$i) {//从第2个元素开始遍历
if ($arr[$i] <= $key) {//小于第一个元素的，放在左边数组
$left_arr[] = $arr[$i];
} else {
$right_arr[] = $arr[$i];
} //大于第一个元素的，放在右边
}
$left_arr = quickSort($left_arr); //对左边的数组排序
$right_arr = quickSort($right_arr); //对右边的数组排序
return array_merge($left_arr, array($key), $right_arr); //合并数组
}
$arr = array(13, 89, 23, 9, 19, 88, 56, 78, 34, 69, 10, 14);
var_dump(insertSort($arr));
