PHP數(shù)組，數(shù)組排序算法，數(shù)組查找算法介紹

PHP數(shù)組，數(shù)組排序算法，數(shù)組查找算法介紹

數(shù)組基礎(chǔ)：

    php中，數(shù)組的下標(biāo)可以整數(shù)，也可以是字符串

    php中，數(shù)組的元素順序不是由下標(biāo)決定，而是由其“加入”的順序決定

定義：

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

    array(1,1.1,5,'abc',true,false); //可以存儲任何數(shù)據(jù)，此時為默認(rèn)下標(biāo)

    array(2=>1,4=>1.1,3=>5,7=>'abc',0=>true); //下標(biāo)可任意設(shè)定（無需順序，無需連續(xù)）

    array(2=>1,1.1,1=>5,'abc',0=>true); //可以加下標(biāo)，也可以不加，不加下標(biāo)則為默認(rèn)下標(biāo)

                                        //默認(rèn)下標(biāo)規(guī)則：前面已經(jīng)用過的最大數(shù)字下標(biāo)+1

                                        //這個數(shù)字的下標(biāo)分別是：2，3，1，4，0

    array(2=>1,'dd'=>5,1=>1.1,'abc',0=>true); //混合下標(biāo)，同樣遵循默認(rèn)下標(biāo)規(guī)則

    array(-2=>1,'dd'=>5,1.1,'abc',true); //負(fù)數(shù)下標(biāo)不算在整數(shù)下標(biāo)中，而只當(dāng)作字符下標(biāo)

                                         //則這個數(shù)組最后三項(xiàng)的下標(biāo)為：0,1,2

    array(2.7=>1,'dd'=>5,1=>1.1,'abc',true); //浮點(diǎn)數(shù)下標(biāo)會自動轉(zhuǎn)換為整數(shù)，且直接去掉小數(shù)部分

    array("2.7"=>1,'dd'=>5,"11"=>1.1,'abc',true); //純數(shù)字字符串下標(biāo)，當(dāng)作數(shù)字看待

    array(2=>1,'dd'=>5,true=>1.1,'abc',false=>true); //布爾值當(dāng)作下標(biāo)，則true為1，false為0

    array(2=>1,'dd'=>5,2=>1.1,'abc',true); //如果下標(biāo)跟前面的重復(fù)，則單純覆蓋前面同名下標(biāo)的值

    其他形式：

        $arr1[] = 1;

        $arr1[] = 5;

        $arr1[] = 1.1;

        ......  //直接在變量后面使用[]，就成為數(shù)組，并依次賦值

        $arr2['aa'] = 1;

        $arr2['bb'] = 5;

        $arr2[5] = 1.1;

        ......  //這種形式寫的下標(biāo)，其實(shí)跟使用array語法結(jié)構(gòu)幾乎一樣

數(shù)組的分類：

    從鍵值關(guān)系分為：

        關(guān)聯(lián)數(shù)組：通常是指下標(biāo)為字符串，并且該字符串大體可以表達(dá)出數(shù)據(jù)的含義的數(shù)組

            例：$person = array("name" => "poe", "age" => 18, "edu" => "大學(xué)畢業(yè)");

        索引數(shù)組：通常是指一個數(shù)組的下標(biāo)嚴(yán)格的從0開始的連續(xù)的數(shù)字下標(biāo) -- 跟js數(shù)組類似

    從數(shù)組層次為分：

        一維數(shù)組：就是一個數(shù)組中的每一個元素值，都是一個普通值（非數(shù)組值）

             例：$person = array("name" => "poe", "age" => 18, "edu" => "大學(xué)畢業(yè)");

        二維數(shù)組：一個數(shù)組中的每一項(xiàng)，又是一個一維數(shù)組。

            $person = array(

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

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

                            "edu" => array("大學(xué)畢業(yè)","小學(xué)",)

                            );

        多維數(shù)組：依次類推。。。

                多維數(shù)組的一般語法形式：

                  $v1 = 數(shù)組名[下標(biāo)][下標(biāo)][......]

數(shù)組的遍歷：

    遍歷基本語法：

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

            //這里就可以對$key and $value進(jìn)行所有可能的操作 -- 因?yàn)樗麄兙褪且粋€變量

            //$key代表每次取得元素的下標(biāo)，可能是數(shù)字，也可以是字符串

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

            //此循環(huán)結(jié)構(gòu)會從數(shù)組的第一項(xiàng)一直遍歷到最后一項(xiàng)，然后結(jié)束

        }

數(shù)組指針和遍歷原理：

    每個數(shù)組，其內(nèi)部都有一個“指針”，該指針決定了該數(shù)組當(dāng)前取值的時候取到的元素

    foreach遍歷過程中，都是依賴于該指針而進(jìn)行的。

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

指針除了負(fù)責(zé)foreach循環(huán)的位置設(shè)定之外，還有其他一些函數(shù)也依賴于指針：

1：$v1 = current($arr1);    //取得$arr1中當(dāng)前指針指向的元素的值，如果沒有指向元素，則為false

2：$v1 = key($arr1);        //取得$arr1中當(dāng)前指針指向的元素的下標(biāo)，。。。。。。。。。。。。。

3：$v1 = next($arr1);       //將指針移向“下一個元素”，然后取得該下一個元素的值

4：$v1 = prev($arr1);       //將指針移向“上一個元素”，然后取得該上一個元素的值

5：$v1 = reset($arr1);      //將指針移向“第一個元素”，并取得該元素的值

6：$v1 = end($arr1);        //將指針移向“最后一個元素”，并取得該元素的值

7：$v1 = each($arr1);       //取得當(dāng)前元素的下標(biāo)和值，然后移動指針到下一個位置

數(shù)組遍歷的流程圖：

for+next+reset 遍歷數(shù)組：

  reset($arr1); //數(shù)組指針初始化。這里，返回的數(shù)據(jù)被“丟棄”了。

  $len = count($arr1);

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

    $key = key($arr1);

    $value = current($arr1);

    next($arr1);

  }

while + each() +list()遍歷數(shù)組：

     each()函數(shù)解釋：可以取得一個數(shù)組中的一個元素的下標(biāo)和值，然后再放入一個新的數(shù)組中。

                     該新數(shù)組，有4個元素，但存儲的是下標(biāo)和值的“雙份”，類似下述形式：

        array(

                1=>取出來的值,

                'value'=>取出來的值,

                0=>取出來的下標(biāo)（鍵名),

                'key'=>>取出來的下標(biāo)（鍵名),

             );  

list()函數(shù)解釋：

    使用形式：list($v1,$v2,$v3,......) = $arr1(數(shù)組);

    其作用是：依次取得數(shù)組$arr1中下標(biāo)為0，1，2，3，......的元素的值，并一次性放多個變量中（一一對應(yīng)）

    即相當(dāng)于如下語句：

    $v1 = arr1[0];

    $v2 = arr1[1];

    $v3 = arr1[2];

    $v4 = arr1[3];

    ......

    但是注意：只能實(shí)現(xiàn)這樣的“從0開始的連續(xù)數(shù)字下標(biāo)元素的取值”（但并非要求數(shù)組的元素的順序?yàn)橥瑯拥臄?shù)字順序）。

然后開始使用這2個函數(shù)和while循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)數(shù)組遍歷：

    reset($arr1);

    while(list($key,$value)=each($arr1)) //從數(shù)組1中一次次出得元素。當(dāng)each到數(shù)組最后，就返回false

    {

        //這里，就可以對$key and $value進(jìn)行操作

    }

    如：

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

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

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

foreach遍歷細(xì)節(jié)探討：

    1：foreach也是正常的循環(huán)語法結(jié)構(gòu)，可以有break and coutinue等操作

    2：遍歷過程中值變量默認(rèn)的傳值方式是值傳遞

    3：遍歷過程中值變量可以人為設(shè)定為引用傳遞！引用傳遞會改變原數(shù)組

        foreach($arr as $key => &$value) {.......} //鍵變量$key不可以使用引用傳遞

    4：foreach默認(rèn)是原數(shù)組上進(jìn)行遍歷。但如果在遍歷過程中對數(shù)組進(jìn)行了某種修改或某種指針性操作，則會復(fù)制數(shù)組后在復(fù)制的數(shù)組上繼續(xù)遍歷循環(huán)。

    5：foreach中如果值變量是引用傳遞，則無論如何都是在原數(shù)組上進(jìn)行。

數(shù)組函數(shù)：

    指針操作函數(shù)：current , key , next , prev , reset , end , each

    單元操作函數(shù)：array_pop , array_push , array_shift , array_unshift , array_slice , array_splice

    排序函數(shù)：sort , asort , ksort , usort , rsort , arsort , krsort , shuffle

    查找函數(shù)：in_array , array_key_exists , array_search

    其他函數(shù)：count , array_reverse , array_merge, array_sum, array_keys , array_values , array_map , array_walk , range

數(shù)組排序思想介紹：

    冒泡排序（bubble sort）：

       目標(biāo)：將下列數(shù)組進(jìn)行正序（從小到大）排列出來

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

        一般性邏輯描述：

            1：對該數(shù)組從第一個元素開始，從左到右，相鄰的兩個元素比較大小，如果左邊的比右邊的大，則將他們兩個交換位置。結(jié)果：

                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);

                此時，才“走完一輪回”繼續(xù)下一輪：

                array(5,3,4,9,11,15); //初始數(shù)組

                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);

                ......

            隱含的邏輯描述（假設(shè)數(shù)組有n項(xiàng)）：

                1：需要進(jìn)行n-1次的“冒泡”比較過程

                2：每一次的比較都比前一次少比較一次，第一次為n-1次

                3：每次比較，都是從數(shù)組的開頭（0）開始，跟緊挨的元素比較，并進(jìn)行交換（需要的時候）

冒泡排序代碼：

得到結(jié)果：

Bubble sort : 
原始數(shù)組：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 )

選擇排序：

    目標(biāo)：將下列數(shù)組進(jìn)行正序（從小到大）排列出來

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

       第一次比較：一般性邏輯描述：取得該數(shù)組中的最大值及其下標(biāo)，然后跟該數(shù)組的最后一項(xiàng)“交換”（倒數(shù)第一項(xiàng)確定）

       第二次比較：取得該數(shù)組中除最后 1 項(xiàng)的最大值及其下標(biāo)，然后跟倒數(shù)第二項(xiàng)交換（倒數(shù)第2項(xiàng)確定）

       第三次比較：取得該數(shù)組中除最后 2 項(xiàng)的最大值及其下標(biāo)，然后跟倒數(shù)第三項(xiàng)交換（倒數(shù)第2項(xiàng)確定）

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

    隱含的邏輯描述（假設(shè)數(shù)組有n項(xiàng)）：

        1：要進(jìn)行 n-1 趟才可能得出結(jié)論

        2：每一趟要找的數(shù)據(jù)的個數(shù)都比前一趟少一次，第一趟要找 n 個

        3：每次找出的最大值所在的項(xiàng)，和要與之進(jìn)行交換的項(xiàng)的位置，依次減 1，第一次的位置是 n-1

選擇排序代碼：  

數(shù)組查找算法：  

    就是從一個數(shù)組中找一個元素的數(shù)據(jù)（可能是找下標(biāo)，也可能是找數(shù)據(jù)值）

    數(shù)組的查找通常有兩種需求：判斷要找的數(shù)據(jù)是否存在；找出要找的數(shù)據(jù)的位置（下標(biāo)）

    順序查找：

    從一個數(shù)組中按順序找出一個元素（下標(biāo)或值）

            需求1：判斷要找的數(shù)據(jù)是否存在

                    $v1 = 10;

                    function search($arr,$v1) {

                        foreach($arr as $value) {

                            if($v1 == $value) {

                                return true;

                            }

                        }

                        return false;

                    }

             需求2：找出要找的數(shù)據(jù)的位置（下標(biāo)）

                    $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：是針對一個已經(jīng)進(jìn)行了排序的數(shù)組（即里面的數(shù)據(jù)已經(jīng)是有序的）

        2：是連續(xù)的索引數(shù)組，比如下標(biāo)為：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 " 判斷數(shù)據(jù)31是否在下列數(shù)據(jù)中存在";

$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";

}

輸出：