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

beebe_3

　　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 search2($arr,$v1) {
                        foreach($arr as $key => $value) {
                            if($v1 == $value) {
                                return $key;

                            }

                        }

                        return false;

                    }
                //特别注意以下写法：

                if($m = search2($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 "";
　　print_r($arr2);
　　echo "";
　　echo '';
　　

　　$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";
　　}
　　输出：