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

}

輸出：