常用算法PHP版本

常用排序算法

排序算法说明

//排序算法
//几种排序算法的结果都是一样的,都可以进行升序或降序操作
//排序速度: 快速排序(在有序数组时效率是最差的) > 直接插入排序算法 > 选择排序 > 冒泡

冒泡排序(升序)

<?php
$arr = [5, 6, 3, 4, 2, 0, 1, 8, 9, 7];

/**
 * 冒泡排序(升序)
 * 主要思路:
 * 1.遍历数组,遍历次数为数组长度
 * 2.遍历数组,每次将将当前元素和后一个做对比
 * 3.从头开始, 比较相邻的元素。如果第一个比第二个大，就交换他们两个,再比第二个和第三个,以此类推。
 *
 * @param array $data
 */
function bubbleSort(array $data)
{
    //统计数组长度
    $length = count($data);
    //控制要冒泡的总轮数
    for ($i = 1; $i < $length; ++$i) {
        /**
         * 在本轮中遍历所有剩余的元素,$length - $i是因为对比过的就不用对比了, 因为对比过的他肯定比后面的小
         * 比如:
         * 这里说的是升序
         * 第一步骤,下标为0对比下标为1,如果0>1,就把1挪到0,再把0挪到1.
         * 第二步, 在用下标1和下标2的对比,如果1>2,就把2挪到1,再把1挪到2.
         */
        for ($j = 0; $j < $length - $i; ++$j) {
            //如果第一个比第二个大,这里是升序排序
            if ($data[$j] > $data[$j + 1]) {
                //将第二个放到一个临时变量中
                $tmp = $data[$j + 1];
                //将第一个放到第二个位置中
                $data[$j + 1] = $data[$j];
                //将第二个放到第一个的位置中
                $data[$j] = $tmp;
            }
        }
    }

    return $data;
}

选择排序(升序)

<?php
$arr = [5, 6, 3, 4, 2, 0, 1, 8, 9, 7];

/**
 * 选择排序(升序)
 * 主要思路:
 * 1.先在未排序序列中找到最小元素，存放到排序序列的起始位置.
 * 2.然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
 * 3.以此类推，直到所有元素均排序完毕。
 *
 * @param [type] $data
 */
function selectSort($data)
{
    //获取数组长度
    $length = count($data);
    //按照长度,从0开始遍历数组
    for ($i = 0; $i < $length - 1; ++$i) {
        //假设当前元素的下标为最小元素的下标
        $minIndex = $i;
        //逐个遍历当前下标后面的所有元素,这就是为了判断当前元素是不是所有元素里面最小的元素
        for ($j = $i + 1; $j < $length; ++$j) {
            //如果该元素<最小元素
            if ($data[$j] < $data[$minIndex]) {
                //则把该元素的下标放到最小下标里面
                $minIndex = $j;
            }
        }
        //已经确定了当前的最小值的位置，保存到$p中。
        //如果 最小值的下标与当前假设的下标$i不同，则互换位置
        if ($minIndex != $i) {
            $tmp = $data[$minIndex];
            $data[$minIndex] = $data[$i];
            $data[$i] = $tmp;
        }
    }

    return $data;
}

快速排序(升序)

<?php
$arr = [5, 6, 3, 4, 2, 0, 1, 8, 9, 7];

/**
 * 快速排序(升序).
 * 主要思路:
 * 从数列中挑出一个元素，称为 "基准"（pivot）;
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 * 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 *
 * @param [type] $data
 */
function fastSort($data)
{
    $length = count($data);
    //必须满足长度,否则返回原数组
    if ($length <= 1) {
        return $data;
    }
    //定义空数组
    $leftArray = [];
    $rightArray = [];
    //遍历数组,遍历次数为数组的长度
    for ($i = 1; $i < $length; ++$i) {
        //判断当前元素是否小于数组的第一个元素
        if ($data[$i] < $data[0]) {
            //当前元素<数组的第一个元素,把当前元素放入$leftArray中
            $leftArray[] = $data[$i];
        } else {
            //当前元素>=数组的第一个元素,把当前元素放入$rightArray中
            $rightArray[] = $data[$i];
        }
    }

    //递归调用
    $leftArray = fastSort($leftArray);
    //同时把$data[0]也追加进leftArray数组里
    $leftArray[] = $data[0];
    $rightArray = fastSort($rightArray);
    //合并数组
    $mergeArr = array_merge($leftArray, $rightArray);

    return $mergeArr;
}

直接插入排序(升序)

<?php
$arr = [5, 6, 3, 4, 2, 0, 1, 8, 9, 7];

/**
 * 直接插入排序(升序)
 * 主要原理:
 * 工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * 因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
 *
 * @param [type] $data
 */
function insertSrot($data)
{
    //获取数组长度
    $length = count($data);
    //遍历数组,遍历次数为数组的长度
    for ($i = 1; $i < $length; ++$i) {
        //当前元素
        $current = $data[$i];
        //另一个遍历方式,这种方式其实看起来更加的清晰,更容易理解
        // for ($j = $i - 1; $j >= 0; --$j) {
        //     if ($current < $data[$j]) {
        //         $data[$j + 1] = $data[$j];
        //         $data[$j] = $current;
        //     } else {
        //         break;
        //     }
        // }

        //前一个键
        $prefix = $i - 1;

        //如果下标不为0 并且前一个元素比当前元素大
        //这里这个逻辑,基本上就是不断的用前一个元素和当前元素比大小,如果前一个元素>当前元素,则把当前元素当到前面,然后在用当前元素继续和前一个的前一个做对比
        //直到比到前一个元素不比当前元素小,则将当前元素放在这个元素的后面
        while ($prefix >= 0 && $data[$prefix] > $current) {
            //将前一个元素插入到当前位置
            $data[$prefix + 1] = $data[$prefix];
            --$prefix;
        }
        //否则将当前元素放到,最后一个比当前元素大的位置,再进行下一个循环
        $data[$prefix + 1] = $current;
    }

    return $data;
}

echo '冒泡排序'.PHP_EOL;
print_r(bubbleSort($arr));
echo '选择排序'.PHP_EOL;
print_r(selectSort($arr));
echo '快速排序'.PHP_EOL;
print_r(fastSort($arr));
echo '插入排序'.PHP_EOL;
print_r(insertSrot($arr));

常用查找算法

二分查找(不支持乱序查找,所以要做好排序)

<?php

//二分查找，因为每次可以舍去一半查找区间，所以会将时间复杂度减少到O(logn)，算法更优。

//十个数,索引数组下标到9
$arr = [5, 6, 3, 4, 2, 0, 1, 8, 9, 7];
$arr1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

/**
 * 非递归的二分查找,对乱序数组无效.
 * 主要思路:
 * 先取数组中间的值floor((lower+higher)/2),
 * 然后通过与所需查找的数字进行比较，若比中间值大，则将首值替换为中间位置下一个位置，继续第一步的操作；若比中间值小，则将尾值替换为中间位置上一个位置，继续第一步操作
 * 重复第二步操作直至找出目标数字.
 *
 * @param array  $data   被查找的内容
 * @param [type] $search 要查找的内容
 */
function binarySearch(array $data, $search)
{
    $length = count($data);
    $lower = 0;
    $higher = $length - 1;

    while ($lower <= $higher) {
        //取出数组中间的下标
        $middle = floor(($lower + $higher) / 2);
        //判断属于左右哪个部分
        if ($data[$middle] > $search) {
            //如果当前元素>搜索元素, 向左移动一位即删除右边的数据
            $higher = $middle - 1;
        } elseif ($data[$middle] < $search) {
            //如果当前元素<搜索元素, 向又移动一位即删除左边的数据
            $lower = $middle + 1;
        } else {
            //等于这个数,即为找到, 则返回
            return $middle;
        }
    }

    //没有找到,返回 -1
    return -1;
}
echo '非递归的二分查找'.PHP_EOL;
//不支持乱序
print_r(binarySearch($arr, 7));
echo PHP_EOL;
//支持顺序
print_r(binarySearch($arr1, 7));
echo PHP_EOL;

/**
 * 递归二分查找,对乱序数组无效.
 *
 * @param [type] $data   被查找的数据
 * @param [type] $search 要查找的元素
 * @param [type] $lower  最小的键
 * @param [type] $higher 最大的键
 */
function binarySearchRecursion($data, $search, $lower, $higher)
{
    //上面看懂了这里就不用说什么了
    $middle = floor(($lower + $higher) / 2);
    if ($lower > $higher) {
        return -1;
    }
    if ($search > $data[$middle]) {
        $result = binarySearchRecursion($data, $search, $middle + 1, $higher);
    } elseif ($search < $data[$middle]) {
        $result = binarySearchRecursion($data, $search, $lower, $middle - 1);
    } else {
        $result = $middle;
    }

    return $result;
}

echo '递归二分查找'.PHP_EOL;
//不支持乱序
print_r(binarySearchRecursion($arr, 7, 0, count($arr) - 1));
echo PHP_EOL;
//支持顺序
print_r(binarySearchRecursion($arr1, 7, 0, count($arr1) - 1));

顺序查找

<?php

$arr = [5, 6, 3, 4, 2, 0, 1, 8, 9, 7];

/**
 * 顺序查找, 很显然顺序查找就是从头到尾挨个对比,比二分查找的性能差很多倍
 * 基本上没什么难度,这里在PHP中其实可以直接用foreach更好.
 *
 * @param [type] $data   被查找的数组
 * @param [type] $search 要查找的内容
 */
function sequenceSearch($data, $search)
{
    $length = count($data);
    for ($i = 0; $i < $length; ++$i) {
        if ($data[$i] == $search) {
            return $i + 1;
        }
    }

    return -1;
}
print_r('顺序查找'.PHP_EOL);
print_r(sequenceSearch($arr, 9));