排序

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);
        }
    }

happy coding!