本文涉及到 冒泡算法 选择排序 快速排序 归并排序 顺序查找 二分/折半查找
<?php // 数组排序算法 // 冒泡算法 两个数字比较 较大的数字放到右边 $arr = array(9,5,6,1,89,6,6,1,2,3,6); for($j = 0,$len = count($arr);$j < $len;$j++){ for($i =0,$len =count($arr);$i < $len-1-$j;$i++){ if($arr[$i] > $arr[$i+1]){ $temp = $arr[$i]; $arr[$i] = $arr[$i+1]; $arr[$i+1] = $temp; } } } echo '<pre>'; print_r($arr); echo '<hr>'; // 选择排序 $arr1 = array(5,6,2,3,1,0); for($i = 0,$len = count($arr1);$i < $len;$i++){ // 假定一个最小的 $min = $i; // 用假定最小的和剩余其他的比较 for($j = $i+1;$j < $len;$j++){ // 当前比较的元素 < 假定的,把当前的下标赋值给min if($arr1[$j] < $arr1[$min]){ $min = $j; } } // 交换真正的最小值 if($min != $i){ $temp = $arr1[$i]; $arr1[$i] = $arr1[$min]; $arr1[$min] = $temp; } } echo '<pre>'; print_r($arr); echo '<hr>'; // 快速排序 $arr2 = [5,6,1,2,3,0]; function quick_sort($arr2){ // 递归出口 数组长度<=1时候就已经排好了 $len = count($arr2); if($len <=1) return $arr2; // 存放数组 $left = $right = array(); for($i =1;$i < $len;$i++){ // 一般情况下把第一个元素当作比较元素,比它小的放到left里面,大的放到right里面 if($arr2[$i] < $arr2[0]){ $left[] = $arr2[$i]; }else{ $right[] = $arr2[$i]; } } // 递归点 $left = quick_sort($left); $right = quick_sort($right); returnarray_merge($left,array($arr2[0]),$right); } echo '<pre>'; print_r(quick_sort($arr2)); echo '<hr>'; // 归并排序 // 二路归并 必须是两个有序数组 // $arr4 = [1,3,5]; // $arr5 = [2,3]; // // 创建一个空数组用于存放归并空间 // $arr6 = array(); // while (count($arr4) && count($arr5)) { // $arr6[] = $arr4[0] < $arr5[0] ? array_shift($arr4) : array_shift($arr5); // } // print_r(array_merge($arr6,$arr4,$arr5)); $arr3 = [5,1,3,9,0]; function merge_sort($arr){ // 递归出口 数组长度<=1时候就已经排好了 $len = count($arr); if($len <=1) return $arr; // 拆分 $middle = floor($len/2); $left = array_slice($arr,0,$middle); $right = array_slice($arr,$middle); // 递归点,保证left和right为有序数组 $left = merge_sort($left); $right = merge_sort($right); $m = array(); while (count($left) &&count($right)) { // 只要left right里面有元素,就进入循环 // 取出left right里面的第一个元素进行比较 哪个小就把小的放入m中 $m[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right); } return (array_merge($m,$left,$right)); } print_r(merge_sort($arr3)); echo '<hr>'; // 查找算法 // 顺序查找 $arr4 = [8,9,7,12,0]; functioncheck_order($arr,$num){ for($i =0,$len =count($arr);$i < $len;$i++){ if($arr[$i] == $num){ return $i; } } returnfalse; } var_dump(check_order($arr4,102)); // 二分/折半 查找 $arr5 = [1,5,7,15,98,120]; $ress = 5; functioncheck_break($arr,$ress){ // 取得边界 $right = count($arr); $left = 0; while ($left <= $right) { // 得到中间值 $middle = floor(($left + $right)/2); // 匹配数据 if($arr[$middle] == $ress){ return $middle +1; } // 值在右边 if($arr[$middle] < $ress){ $left = $middle + 1; }else{ $right = $middle - 1; } } returnfalse; } var_dump(check_break($arr5,$ress));