php 常用的算数排序

常见的排序:

1.冒泡排序:

  原理:第一个数字和所有数字进行比较,然后遇到大的交换位置,这样第一次就把最大的放在了最后边,然后继续在比较,第二次比较的时候最后一个数字就不用比较了,因为已经确定它是最大的了,以此类推。

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

 *     比如:2,4,1    // 第一次 冒出的泡是4 

 *            2,1,4   // 第二次 冒出的泡是 2 

 *                1,2,4   // 最后就变成这样 

时间复杂度:冒泡排序是一种用时间换空间的排序方法,最坏情况是把顺序的排列变成逆序,或者把逆序的数列变成顺序。

<?php

$arr = array(1,45,21,89,12,5,2,46,23);

 function getPao($arr)
 {
    $len = count($arr);                             //获取数组长度

    for ($i=1; $i < $len; $i++)                     //该循环控制 需要冒泡轮数
    {
        for ($j=0; $j < $len-$i; $j++)              //该循环控制每轮冒出一个数需要比较的次数
        {
            if($arr[$j] > $arr[$j+1])
            {
                $tmp = $arr[$j+1];
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
    return $arr;
 }

?>


2.选择排序:

       

    实现思路 双重循环完成,外层控制轮数,当前的最小值。内层 控制的比较次数


<?php

  function select_sort($arr)
    {
        $len = count($arr);

        for ($i=0,$len; $i < $len-1; $i++) {        //$i 当前最小值的位置, 需要参与比较的元素
            $p = $i;                                //先假设最小的值的位置
            for ($j=$i+1; $j < $len; $j++) {        //$j 当前都需要和哪些元素比较,$i 后边的
                if($arr[$p] > $arr[$j])             //$arr[$p] 是 当前已知的最小值
                {
                    $p = $j;                        //比较,发现更小的,记录下最小值的位置;并且在下次比较时, 应该采用已知的最小值进行比较。
                }
            }
            //已经确定了当前的最小值的位置,保存到$p中。如果发现 最小值的位置与当前假设的位置$i不同,则位置互换即可
            if($p != $i)
            {
                $tmp = $arr[$p];
                $arr[$p] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
        return $arr;
    }

?>


3.快速排序


<?php

     function quick_sort($arr)
    {
        $len = count($arr);
        if($len <= 1)                       //先判断是否需要继续进行
        {
            return $arr;
        }

        $base_num = $arr[0];                //如果没有返回,说明数组内的元素个数 多余1个,需要排序 。选择一个标尺。 选择第一个元素
        //初始化两个数组
        $left_array = array();              //小于标尺的
        $right_array = array();             //大于标尺的
        for ($i=1; $i < $len; $i++)         //遍历 除了标尺外的所有元素,按照大小关系放入两个数组内
        {
            if($base_num > $arr[$i])
            {
                $left_array[] = $arr[$i];
            }
            else
            {
                $right_array[] = $arr[$i];
            }
        }
        //再分别对 左边 和 右边的数组进行相同的排序处理方式。递归调用这个函数,并记录结果
        $left_array = quick_sort($left_array);
        $right_array = quick_sort($right_array);
        return array_merge($left_array,array($base_num),$right_array);
    }

?>


4.插入排序

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


<?php

 

function insert_sort($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;

}


?>


5.二分查找

1,2,3,4,5,6,7

我现在要查找7

我先取出中间数 4

判断下是不是要找的数字,发现小了

就去右边查找

然后取出右边的所有的数

取出她们几个的中间数 6

发现还小了

继续找右边的数组

找到7了 ok了!!!

 

最差的一种情况就是这个数字不存在 ====

 function binary_search(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) $high = $mid - 1;
        if($arr[$mid] < $target) $low = $mid + 1;
    }
    return false;
 }

 $arr = array(1,3,5,9,15,19);
 $inx = binary_search($arr,3);
 var_dump($inx);

?>

相关内容推荐