PHP数组，数组排序算法，数组查找算法介绍

PHP数组，数组排序算法，数组查找算法介绍

数组基础：

    php中，数组的下标可以整数，也可以是字符串

    php中，数组的元素顺序不是由下标决定，而是由其“加入”的顺序决定

定义：

    $arr1 = array(元素1，元素2，。。。。。。);

    array(1,1.1,5,'abc',true,false); //可以存储任何数据，此时为默认下标

    array(2=>1,4=>1.1,3=>5,7=>'abc',0=>true); //下标可任意设定（无需顺序，无需连续）

    array(2=>1,1.1,1=>5,'abc',0=>true); //可以加下标，也可以不加，不加下标则为默认下标

                                        //默认下标规则：前面已经用过的最大数字下标+1

                                        //这个数字的下标分别是：2，3，1，4，0

    array(2=>1,'dd'=>5,1=>1.1,'abc',0=>true); //混合下标，同样遵循默认下标规则

    array(-2=>1,'dd'=>5,1.1,'abc',true); //负数下标不算在整数下标中，而只当作字符下标

                                         //则这个数组最后三项的下标为：0,1,2

    array(2.7=>1,'dd'=>5,1=>1.1,'abc',true); //浮点数下标会自动转换为整数，且直接去掉小数部分

    array("2.7"=>1,'dd'=>5,"11"=>1.1,'abc',true); //纯数字字符串下标，当作数字看待

    array(2=>1,'dd'=>5,true=>1.1,'abc',false=>true); //布尔值当作下标，则true为1，false为0

    array(2=>1,'dd'=>5,2=>1.1,'abc',true); //如果下标跟前面的重复，则单纯覆盖前面同名下标的值

    其他形式：

        $arr1[] = 1;

        $arr1[] = 5;

        $arr1[] = 1.1;

        ......  //直接在变量后面使用[]，就成为数组，并依次赋值

        $arr2['aa'] = 1;

        $arr2['bb'] = 5;

        $arr2[5] = 1.1;

        ......  //这种形式写的下标，其实跟使用array语法结构几乎一样

数组的分类：

    从键值关系分为：

        关联数组：通常是指下标为字符串，并且该字符串大体可以表达出数据的含义的数组

            例：$person = array("name" => "poe", "age" => 18, "edu" => "大学毕业");

        索引数组：通常是指一个数组的下标严格的从0开始的连续的数字下标 -- 跟js数组类似

    从数组层次为分：

        一维数组：就是一个数组中的每一个元素值，都是一个普通值（非数组值）

             例：$person = array("name" => "poe", "age" => 18, "edu" => "大学毕业");

        二维数组：一个数组中的每一项，又是一个一维数组。

            $person = array(

                            "name" => array("xiaohua","xiaofang), 

                            "age" => array(18,22), 

                            "edu" => array("大学毕业","小学",)

                            );

        多维数组：依次类推。。。

                多维数组的一般语法形式：

                  $v1 = 数组名[下标][下标][......]

数组的遍历：

    遍历基本语法：

        foreach($arr as [$key =>] $value) {

            //这里就可以对$key and $value进行所有可能的操作 -- 因为他们就是一个变量

            //$key代表每次取得元素的下标，可能是数字，也可以是字符串

            //$value代表每次取得元素的值，可能是各种类型

            //此循环结构会从数组的第一项一直遍历到最后一项，然后结束

        }

数组指针和遍历原理：

    每个数组，其内部都有一个“指针”，该指针决定了该数组当前取值的时候取到的元素

    foreach遍历过程中，都是依赖于该指针而进行的。

    举例：$arr1 = array(2=>1,'dd'=>5,1=>1.1,'abc',0=>true);

指针除了负责foreach循环的位置设定之外，还有其他一些函数也依赖于指针：

1：$v1 = current($arr1);    //取得$arr1中当前指针指向的元素的值，如果没有指向元素，则为false

2：$v1 = key($arr1);        //取得$arr1中当前指针指向的元素的下标，。。。。。。。。。。。。。

3：$v1 = next($arr1);       //将指针移向“下一个元素”，然后取得该下一个元素的值

4：$v1 = prev($arr1);       //将指针移向“上一个元素”，然后取得该上一个元素的值

5：$v1 = reset($arr1);      //将指针移向“第一个元素”，并取得该元素的值

6：$v1 = end($arr1);        //将指针移向“最后一个元素”，并取得该元素的值

7：$v1 = each($arr1);       //取得当前元素的下标和值，然后移动指针到下一个位置

数组遍历的流程图：

for+next+reset 遍历数组：

  reset($arr1); //数组指针初始化。这里，返回的数据被“丢弃”了。

  $len = count($arr1);

  for($i = 0;$i < $len;$i++) {

    $key = key($arr1);

    $value = current($arr1);

    next($arr1);

  }

while + each() +list()遍历数组：

     each()函数解释：可以取得一个数组中的一个元素的下标和值，然后再放入一个新的数组中。

                     该新数组，有4个元素，但存储的是下标和值的“双份”，类似下述形式：

        array(

                1=>取出来的值,

                'value'=>取出来的值,

                0=>取出来的下标（键名),

                'key'=>>取出来的下标（键名),

             );  

list()函数解释：

    使用形式：list($v1,$v2,$v3,......) = $arr1(数组);

    其作用是：依次取得数组$arr1中下标为0，1，2，3，......的元素的值，并一次性放多个变量中（一一对应）

    即相当于如下语句：

    $v1 = arr1[0];

    $v2 = arr1[1];

    $v3 = arr1[2];

    $v4 = arr1[3];

    ......

    但是注意：只能实现这样的“从0开始的连续数字下标元素的取值”（但并非要求数组的元素的顺序为同样的数字顺序）。

然后开始使用这2个函数和while循环结构来实现数组遍历：

    reset($arr1);

    while(list($key,$value)=each($arr1)) //从数组1中一次次出得元素。当each到数组最后，就返回false

    {

        //这里，就可以对$key and $value进行操作

    }

    如：

    $my_array = array("Dog","Cat","Horse");

    list($a,$b,$c) = $my_array;

    echo "I have several animals, a $a , a $b, a $c.";

foreach遍历细节探讨：

    1：foreach也是正常的循环语法结构，可以有break and coutinue等操作

    2：遍历过程中值变量默认的传值方式是值传递

    3：遍历过程中值变量可以人为设定为引用传递！引用传递会改变原数组

        foreach($arr as $key => &$value) {.......} //键变量$key不可以使用引用传递

    4：foreach默认是原数组上进行遍历。但如果在遍历过程中对数组进行了某种修改或某种指针性操作，则会复制数组后在复制的数组上继续遍历循环。

    5：foreach中如果值变量是引用传递，则无论如何都是在原数组上进行。

数组函数：

    指针操作函数：current , key , next , prev , reset , end , each

    单元操作函数：array_pop , array_push , array_shift , array_unshift , array_slice , array_splice

    排序函数：sort , asort , ksort , usort , rsort , arsort , krsort , shuffle

    查找函数：in_array , array_key_exists , array_search

    其他函数：count , array_reverse , array_merge, array_sum, array_keys , array_values , array_map , array_walk , range

数组排序思想介绍：

    冒泡排序（bubble sort）：

       目标：将下列数组进行正序（从小到大）排列出来

        $arr2 = array(5,15,3,4,9,11);

        一般性逻辑描述：

            1：对该数组从第一个元素开始，从左到右，相邻的两个元素比较大小，如果左边的比右边的大，则将他们两个交换位置。结果：

                array(5,15,3,4,9,11);

                array(5,3,15,4,9,11);

                array(5,3,4,15,9,11);

                array(5,3,4,9,15,11);

                array(5,3,4,9,11,15);

                此时，才“走完一轮回”继续下一轮：

                array(5,3,4,9,11,15); //初始数组

                array(3,5,4,9,11,15);

                array(3,4,5,9,11,15);

                array(3,4,5,9,11,15);

                array(3,4,5,9,11,15);

                array(3,4,5,9,11,15);

                ......

            隐含的逻辑描述（假设数组有n项）：

                1：需要进行n-1次的“冒泡”比较过程

                2：每一次的比较都比前一次少比较一次，第一次为n-1次

                3：每次比较，都是从数组的开头（0）开始，跟紧挨的元素比较，并进行交换（需要的时候）

冒泡排序代码：

得到结果：

Bubble sort : 
原始数组：Array ( [0] => 5 [1] => 15 [2] => 3 [3] => 4 [4] => 9 [5] => 11 ) 
排序之后：Array ( [0] => 3 [1] => 4 [2] => 5 [3] => 9 [4] => 11 [5] => 15 )

选择排序：

    目标：将下列数组进行正序（从小到大）排列出来

   $arr2 = array(5,15,3,4,9,11);

       第一次比较：一般性逻辑描述：取得该数组中的最大值及其下标，然后跟该数组的最后一项“交换”（倒数第一项确定）

       第二次比较：取得该数组中除最后 1 项的最大值及其下标，然后跟倒数第二项交换（倒数第2项确定）

       第三次比较：取得该数组中除最后 2 项的最大值及其下标，然后跟倒数第三项交换（倒数第2项确定）

           ..............

    隐含的逻辑描述（假设数组有n项）：

        1：要进行 n-1 趟才可能得出结论

        2：每一趟要找的数据的个数都比前一趟少一次，第一趟要找 n 个

        3：每次找出的最大值所在的项，和要与之进行交换的项的位置，依次减 1，第一次的位置是 n-1

选择排序代码：  

数组查找算法：  

    就是从一个数组中找一个元素的数据（可能是找下标，也可能是找数据值）

    数组的查找通常有两种需求：判断要找的数据是否存在；找出要找的数据的位置（下标）

    顺序查找：

    从一个数组中按顺序找出一个元素（下标或值）

            需求1：判断要找的数据是否存在

                    $v1 = 10;

                    function search($arr,$v1) {

                        foreach($arr as $value) {

                            if($v1 == $value) {

                                return true;

                            }

                        }

                        return false;

                    }

             需求2：找出要找的数据的位置（下标）

                    $v1 = 10;

                    function search3($arr,$v1) {

                        foreach($arr as $key => $value) {

                            if($v1 == $value) {

                                return $key;

                            }

                        }

                        return false;

                    }

                //特别注意以下写法：

                if($m = search3($arr,10)) === false) {

                    echo "没找到";

                }else{

                    echo "找到了，位置为$m";

                }

二分查找：

    二分查找的前提：

        1：是针对一个已经进行了排序的数组（即里面的数据已经是有序的）

        2：是连续的索引数组，比如下标为：0,1,2,3,4,......

    如：$arr2 = array(3,4,5,15,19,21,25,28,30,33,38,44,51,52,60,77,80,82,83);

二分查找案例代码：

echo " 判断数据31是否在下列数据中存在";

$arr2 = array(3,4,5,15,19,21,25,28,30,30,33,38,44,51,52,60,77,80,82,83);

echo "<pre>";

print_r($arr2);

echo "</pre>";

echo '<hr />';

$v1 = 15;

// $v target data

//$start the target data start position in the array

//$end the target data end position in the array

function binary_search($arr,$v,$start,$end) {

$mid = floor(($start + $end)/2);

if($v == $arr[$mid]) {

return $mid;

}else if($v < $arr[$mid]) {

$start = $start;

$end = $mid -1;

if($start > $end) {

return false;

}

return binary_search($arr,$v,$start,$end);

}else{

$start = $mid +1;

$end = $end;

if($start > $end) {

return false;

}

return binary_search($arr,$v,$start,$end);

}

}

$len = count($arr2);

$result = binary_search($arr2,$v1,0,$len-1);

if($result === false) {

echo "No such data";

}else{

echo "$v1 position is : $result";

}

输出：