冒泡排序
<?php
/**
* 排序算法-冒泡排序
*/
/**
* 冒泡排序
*
* @param array $value 待排序数组
* @return array
*/
function bubble($value = [])
{
$length = count($value) - 1;
// 外循环
for ($j = 0; $j < $length; ++$j) {
// 内循环
for ($i = 0; $i < $length; ++$i) {
// 如果后一个值小于前一个值，则互换位置
if ($value[$i + 1] < $value[$i]) {
$tmp = $value[$i + 1];
$value[$i + 1] = $value[$i];
$value[$i] = $tmp;
}
}
}
return $value;
}
/**
* 优化冒泡排序
*
* @param array $value 待排序数组
* @return array
*/
function bubble_better($value = [])
{
$flag = true; // 标示 排序未完成
$length = count($value)-1; // 数组长度
$index = $length; // 最后一次交换的索引位置 初始值为最后一位
while ($flag) {
$flag = false; // 假设排序已完成
for ($i=0; $i < $index; $i++) {
if ($value[$i] > $value[$i+1]) {
$flag = true; // 如果还有交换发生 则排序未完成
$last = $i; // 记录最后一次发生交换的索引位置
$tmp = $value[$i];
$value[$i] = $value[$i+1];
$value[$i+1] = $tmp;
}
}
$index = $last;
}
return $value;
}
快速排序
<?php
/**
* php算法实战.
*
* 排序算法-快速排序
*
* @author TIGERB <https://github.com/TIGERB>
*/
/**
* 快速排序.
*
* @param array $value 待排序数组
* @param array $left 左边界
* @param array $right 右边界
*
* @return array
*/
function quick(&$value, $left, $right)
{
// 左右界重合 跳出
if ($left >= $right) {
return;
}
$base = $left;
do {
// 从最右边开始找到第一个比基准小的值，互换位置
// 找到基准索引为止
for ($i=$right; $i > $base; --$i) {
if ($value[$i] < $value[$base]) {
$tmp = $value[$i];
$value[$i] = $value[$base];
$value[$base] = $tmp;
$base = $i; // 更新基准值索引
break;
}
}
// 从最左边开始找到第一个比基准大的值，互换位置
// 找到基准索引为止
for ($j=$left; $j < $base; ++$j) {
if ($value[$j] > $value[$base]) {
$tmp = $value[$j];
$value[$j] = $value[$base];
$value[$base] = $tmp;
$base = $j; // 更新基准值索引
break;
}
}
} while ($i > $j);// 直到左右索引重合为止
// 开始递归
// 以当前索引为分界
// 开始排序左部分
quick($value, $left, $i-1);
// 开始排序右边部分
quick($value, $i+1, $right);
return $value;
}
/**
* 快速排序.while版本
*
* @param array $value 待排序数组
* @param array $left 左边界
* @param array $right 右边界
*
* @return array
*/
function quick_while(&$value, $left, $right)
{
// 左右界重合 跳出
if ($left >= $right) {
return;
}
$point = $left;
$i = $right;
$j = $left;
while ($i > $j) {
//查右边值
while ($i > $point) {
if ($value[$i] < $value[$point]) {
$tmp = $value[$i];
$value[$i] = $value[$point];
$value[$point] = $tmp;
$point = $i;
break;
}
--$i;
}
//查左边值
while ($j < $point) {
if ($value[$j] > $value[$point]) {
$tmp = $value[$j];
$value[$j] = $value[$point];
$value[$point] = $tmp;
$point = $j;
break;
}
++$j;
}
}
// 开始递归
// 以当前索引为分界
// 开始排序左部分
quick_while($value, $left, $i-1);
// 开始排序右边部分
quick_while($value, $i+1, $right);
return $value;
}
二分查找
/**
* 二分查找，要求数组已经排好顺序
* @param array $array 数组
* @param int $low 数组起始元素下标
* @param int $high 数组末尾元素下标
* @param $k 要查找的元素
* @return mixed 成功时返回数组下标，失败返回-1
*/
function bin_sch($array,$low,$high,$k){
if ($low <= $high) {
$mid = intval(($low + $high) / 2);
if ($array[$mid] == $k) {
return $mid;
} elseif ($k < $array[$mid]) {
return bin_sch($array,$low,$mid - 1,$k);
} else{
return bin_sch($array,$mid + 1,$high,$k);
}
}
return -1;
}
// 测试：二分查找
$arr2 = array(5,9,15,25,34,47,55,76);
echo bin_sch($arr2,0,7,47);//结果为5
