排序
1.冒泡排序
遍历数组依次比较对换。
function bubble_sort($arr) {
$count = count($arr);
// 外层从0依次遍历
for ($i = 0; $i < $count; $i++) {
// 依次比对之后的每一个值
for ($j = $i+1; $j < $count; $j++) {
// 如果大于则替换位置
if ($arr[$i] > $arr[$j]) {
$tmp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $tmp;
}
}
}
return $arr;
}
2.选择排序
选择排序与冒泡排序类似，区别在于冒泡是每次都对换位置；选择排序则是先找出最小值下标，如果有改变再对换位置。
function select_sort($arr) {
$count = count($arr);
// 外层从0依次遍历
for ($i = 0; $i < $count; $i++) {
// 设置默认最小值下标
$p = $i;
// 依次比对之后的每一个值
for ($j = $i+1; $j < $count; $j++) {
// 如果大于则更正最小值下标
if ($arr[$p] > $arr[$j]) {
$p = $j;
}
}
// 最小值下标有变化，交换数组位置
if ($p != $i) {
$tmp = $arr[$i];
$arr[$i] = $arr[$p];
$arr[$p] = $tmp;
}
}
return $arr;
}
3.插入排序
假设第一位是已排序队列，从第二位开始依次执行：向前比较，如果小于则交换前后位置。
function insert_sort($arr) {
$count = count($arr);
// 假设第一位已排序，从第二位i=1开始向前比较
for ($i = 1; $i < $count; $i++) {
$tmp = $arr[$i];
// 依次与前面的排序元素执行比较对换
for ($j = $i-1; $j >= 0; $j--) {
// 小于前面对比则将后边的元素与前面的元素互换
if ($tmp < $arr[$j]) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
} else {
// 因为前面是已排序队列，因此没必要再比较
break;
}
}
}
return $arr;
}
4.快速排序
通过递归分组实现排序。
function quick_sort($arr) {
// 递归结束条件
$count = count($arr);
if ($count <= 1) {
return $arr;
}
// 取第一个作为参考值
$key = $arr[0];
// 开始分组
$left_arr = array();
$right_arr = array();
for ($i = 1; $i < $count; $i++) {
if ($arr[$i] <= $key) {
$left_arr[] = $arr[$i];
} else {
$right_arr[] = $arr[$i];
}
}
// 递归分组
$left_arr = quick_sort($left_arr);
$right_arr = quick_sort($right_arr);
// 合并数组
$total_arr = array_merge($left_arr, array($key), $right_arr);
return $total_arr;
}
查找
1.顺序查找
遍历数组依次查找
function seq_sch($arr,$k){
foreach($arr as $key=>$val){
if($val == $k){
return $key;
}
}
return -1;
}
2.二分法查找
利用递归思想，查找顺序数组中指定元素下标。
function bin_sch($arr, $low, $high, $k) {
if ($low > $high) {
return -1;
}
$mid = intval(($low+$high)/2);
if ($arr[$mid] == $k) {
return $mid;
} else if ($k < $arr[$mid]) {
return bin_sch($arr, $low, $mid-1, $k);
} else {
return bin_sch($arr, $mid+1, $high, $k);
}
}
原文地址：http://www.fidding.me/article/31
happy coding!
