No Comments

PHP 常用算法

/**
 * 二分查找(数组里查找某个元素)
 * @param  array $array
 * @param  int   $low    最小索引
 * @param  int   $high   最大索引
 * @param  mixed $search 待查找元素
 * @return mixed
 */
function binSch($array, $low, $high, $search)
{
    if ($low <= $high) {
        $mid = intval(($low + $high) / 2);
        if ($array[$mid] == $search) {
            return $mid;
        } elseif ($search < $array[$mid]) {
            return binSch($array, $low, $mid - 1, $search);
        } else {
            return binSch($array, $mid + 1, $high, $search);
        }
    }
    return -1;
}
// $arr = [1,3,4,5,6,7];
// $res = binSch($arr,0,5,3);
// var_export($res);

/**
 * 顺序查找(数组里查找某个元素)
 * @param  array  $array
 * @param  int    $n     数组长度
 * @param  mixed  $k     待查元素
 * @return mixed
 */
function seqSch(array $array, int $n, $k)
{
    $array[$n] = $k;
    for ($i = 0; $i < $n; $i++) {
        if ($array[$i] == $k) {
            break;
        }
    }
    if ($i < $n) {
        return $i;
    } else {
        return -1;
    }
}
// $arr = [1, 3, 4, 5, 6, 7];
// $res = seqSch($arr, 6, 7);
// var_export($res);

/**
 * 线性表的删除(数组删除)
 * @param  array $array
 * @param  int   $i     待删除索引
 * @return mixed
 */
function delete_array_element(array $array, $i)
{
    // var_export($array);
    $len = count($array);
    for ($j = $i; $j < $len - 1; $j++) {
        $array[$j] = $array[$j + 1];
    }
    array_pop($array);
    return $array;
}
// $arr = [1, 3, 4, 5, 6, 7];
// $res = delete_array_element($arr, 5);
// var_export($res);

/**
 * 冒泡排序(找出最小,向左)
 * @param  array $array
 * @return array
 */
function bubble_sort1($array)
{
    $count = count($array);
    if ($count <= 0) {
        return [];
    }
    for ($i = 0; $i < $count; $i++) {
        for ($j = $count - 1; $j > $i; $j--) {
            if ($array[$j] < $array[$j - 1]) {
                $tmp           = $array[$j];
                $array[$j]     = $array[$j - 1];
                $array[$j - 1] = $tmp;
            }
        }
    }
    return $array;
}
// $arr = [1, 3, 4, 5, 6, 7];
// shuffle($arr);
// $res = bubble_sort1($arr);
// var_export($res);

/**
 * 冒泡排序(找出最大,向右)
 * @param  array $array
 * @return array
 */
function bubble_sort($arr)
{
    $count = count($arr);
    if ($count <= 0) {
        return [];
    }
    for ($i = 0; $i < $count - 1; $i++) {
        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp         = $arr[$j];
                $arr[$j]     = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
        }
    }
    return $arr;
}
// $arr = [1, 3, 4, 5, 6, 7];
// shuffle($arr);
// $res = bubble_sort($arr);
// var_export($res);

/**
 * 快速排序(数组排序)
 * @param  array $array 待排数组
 * @return array
 */
function quick_sort($array)
{
    if (count($array) <= 1) {
        return $array;
    }
    $key       = $array[0];
    $left_arr  = array();
    $right_arr = array();
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] <= $key) {
            $left_arr[] = $array[$i];
        } else {
            $right_arr[] = $array[$i];
        }

    }
    $left_arr  = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, [$key], $right_arr);
}
// $arr = [5, 7, 6, 4, 3, 1, 8];
// $res = quick_sort($arr);
// var_export($res);

选择排序

  • 每次在未排序中找到最小,和当前最靠前的元素交换
  • 从0开始循环,从1开始,一直到末尾

  • 由于每次把余下数组中最小元素提到前面,自然就有序了

    function selection_sort($arr)
{
  $len = count($arr);
  for ($i = 0; $i < $len; $i++) {
      $minIndex = $i;
      for ($j = $i; $j < $len; $j++) {
          if ($arr[$j] < $arr[$minIndex]) {
              $minIndex = $j;
          }
      }
      $tmp = $arr[$i];
      $arr[$i] = $arr[$minIndex];
      $arr[$minIndex] = $tmp;
  }
  return $arr;
}
$arr = [1, 2, 1, 4, 5, 6, 8, 90, 90, 111];
var_dump(selection_sort($arr));

最后更新于 2021-06-25 03:24:44 并被添加「PHP 常用算法」标签，已有 516 位童鞋阅读过。

相关文章

此处评论已关闭