偶然间在网上看到了一篇文章《程序员必须知道的10大基础实用算法及其讲解》,发现一个不懂算法的程序猿算不上一个合格的猿,所以接下来的目标又多出了一个算法和数据结构。
本文的算法全部使用PHP语言实现。
1.快速排序算法
在我看来快速排序就是先找到一个基准,然后创建两个数组,把大于这个基准的数字放到一个数组里,小于这个基准的数字放到一个数组里,然后在两个数组里分别再进行判断。
具体实现:
- <?php
- function quickSort(&$arr) {
- if(count($arr)>1) {
- $k = $arr[0];
- $x = array();
- $y = array();
- $_size = count($arr);
- for($i=1;$i<$_size;$i++) {
- if($arr[$i]<=$k) {
- $x[] = $arr[$i];
- }elseif($arr[$i]>$k) {
- $y[] = $arr[$i];
- }
- }
- $x = quickSort($x);
- $y = quickSort($y);
- return array_merge($x,array($k),$y);
- }else {
- return $arr;
- }
- }
- ?>
2.二分查找算法
二分查找用于从一个数组中查找一个元素所在位置的算法。原理是,首先对数组进行排序,然后取这个数组的中间值和目标元素进行判断,如果目标元素小于中间值,那么它就在中间值的前半部分,然后再从前半部分应用二分查找。
具体实现:
- <?php
- function binarySearch(Array $arr,$target) {
- $low = 0;
- $high = count($arr)-1;
- while($low<=$high) {
- $mid = floor(($low+$high)/2);
- if($arr[$mid]==$target) {
- //找到了
- return $mid;
- }
- if($arr[$mid] < $target) {
- //中间值小于目标值,搜索后半部分
- $low = $mid+1;
- }
- if($arr[$mid] > $target) {
- //中间值大于目标值,搜索前半部分
- $high = $mid-1;
- }
- }
- //查找失败
- return false;
- }
- ?>
3.值传递和引用传递(插一句)
有时候我们看到的函数是这样的
- function bubbleSort(&$arr) {
- $arr++;
- }
那么传递的$arr到底是怎么回事呢,其实这就是php中的引用传递方法。
例如:
- function bubbleSort($num) {
- $num++;
- }
- function bubbleSort1(&$num) {
- $num++;
- }
- $num = 1;
- echo "num=".$num."<br/>";
- bubbleSort($num);
- echo "bubbleSort-num=".$num."<br/>";
- bubbleSort1($num);
- echo "bubbleSort1-num=".$num."<br/>";
输出结果:
num=1
bubbleSort-num=1
bubbleSort1-num=2
会发现,使用值传递的时候,并不会改变传入参数的值。而使用引用传递的时候,会将传入参数的值改变。
4.冒泡排序
每一次循环,比较相邻两个元素,实现找到最大的元素放在最后,像冒泡一样,每次循环冒上去一个最大的元素,所以叫冒泡排序吧,哈哈哈!
具体实现:
- function bubbleSort($arr = array()) {
- $size = count($arr);
- for($i = 0; $i < $size - 1; $i++) {
- for($j = $i + 1; $j < $size; $j++) {
- if($arr[$i] > $arr[$j]) {
- $tmp = $arr[$i];
- $arr[$i] = $arr[$j];
- $arr[$j] = $tmp;
- }
- }
- }
- return $arr;
- }
- $test = array(3,2,1,5,9,7,4,12,10);
- print_r(bubbleSort($test));
|