三途河畔

PHP四种排序基础算法

默认分类

快速排序

快速排序是十分常用的高效率的算法,其思想是:先选一个标尺,用它把整个队列过一遍筛选,以保证其左边的元素都不大于它,其右边的元素都不小与它

function bubbleSort($arr){

    // 获取数组长度
    $length = count($arr);

    // 第一层循环控制冒泡轮次

    for ($i= 0; $i < $length - 1; $i++) {

        // 内层循环控制从第0个键值和后一个键值比较,每次冒出一个最大的数
        for ($k= 0; $k < $length-$i; $k++) {

            if ($arr[$k] > $arr[$k + 1]){
                $tmp = $arr[$k + 1];
                $arr[$k + 1] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }

    return $arr;
}

冒泡排序

思路:法如其名,就像冒泡一样,每次从数组中冒出一个最大的数。

比如:2,4,1

第一次冒出4:2,1,4

第二次冒出2:1,2,4

function quickSort($arr){

    // 获取数组长度
    $length = count($arr);

    // 判断长度是否需要继续二分比较
    if ($length <= 1){
        return $arr;
    }

    // 定义基准元素
    $base = $arr[0];

    // 定义两个空数组,用于存放和基准元素的比较后的结果
    $left = [];
    $right = [];

    // 遍历数组
    for ($i = 1; $i < $length; $i++) {

        // 和基准元素作比较
        if ($arr[$i] > $base) {
            $right[] = $arr[$i];
        }else{
            $left[] = $arr[$i];
        }
    }

    // 然后递归分别处理left和right
    $left = quickSort($left);
    $right = quickSort($right);

    // 合并
    return array_merge($left,[$base],$right);
}

选择排序

思路:每次选择一个相应的元素,然后将其放到指定的位置

function selectSort($arr)
{
    // 双重循环完成,外层控制轮数,当前的最小值,内层控制比较次数
    // 获取长度
    $length = count($arr);

    for ($i = 0; $i < $length - 1; $i++) {

        // 假设最小值的位置
        $p = $i;

        // 使用假设的最小值和其他值比较,找到当前的最小值

        for ($j = $i + 1; $j < $length; $j++) {

            // $arr[$p] 是已知的当前最小值

            // 判断当前循环值和已知最小值的比较,当发下更小的值时记录下键,并进行下一次比较
            if ($arr[$p] > $arr[$j]) {
                // 比假设的值更小
                $p = $j;
            }
        }

        // 通过内部for循环找到了当前最小值的key,并保存在$p中
        // 判断 日光当前$p 中的键和假设的最小值的键不一致增将其互换
        if ($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }

    // 返回最终结果
    return $arr;
}

插入排序

插入排序法思路:将要排序的元素插入到已经 假定排序号的数组的指定位置。

function insertSort($arr) {
    //区分 哪部分是已经排序好的
    //哪部分是没有排序的
    //找到其中一个需要排序的元素
    //这个元素 就是从第二个元素开始,到最后一个元素都是这个需要排序的元素
    //利用循环就可以标志出来
    //i循环控制 每次需要插入的元素,一旦需要插入的元素控制好了,
    //间接已经将数组分成了2部分,下标小于当前的(左边的),是排序好的序列
    for($i=1, $len=count($arr); $i<$len; $i++) {
        //获得当前需要比较的元素值。
        $tmp = $arr[$i];
        //内层循环控制 比较 并 插入
        for($j=$i-1;$j>=0;$j--) {
   //$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
            if($tmp < $arr[$j]) {
                //发现插入的元素要小,交换位置
                //将后边的元素与前面的元素互换
                $arr[$j+1] = $arr[$j];
                //将前面的数设置为 当前需要交换的数
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
           //由于是已经排序好是数组,则前面的就不需要再次比较了。
                break;
            }
        }
    }
    //将这个元素 插入到已经排序好的序列内。
    //返回
    return $arr;
}
点我评论
打赏本文
二维码


18

文章

1

标签

 文章分类

 友情链接