PHP常見排序算法學習

2020-03-22 18:33:58

字體：大中小

來源：轉載

供稿：網友

常見的排序算法有：冒泡排序法，快速排序法，選擇排序法，插入排序法，本文做了一個PHP常見排序小結筆記，同時也希望能幫到你。

需求：將一個有多個數字的數組進行從小到大的排序.

排序算法

【一】.冒泡排序

思路分析：
想象一個大水池里有N多還未排好的序列的氫氣球，較大的先冒出來，然后依次是較小的往上冒。即，每次比較相鄰的兩個數，小的在前大的在后，否則進行位置互換。

代碼實現：（舉例幾種寫法，注意循環體的判斷條件）建議使用第一、二種。

   /**     * 交換方法     * @param array $arr 目標數組     * @param $a 索引a     * @param $b 索引b     * @param bool $flag 交換標志     * @return bool     */    function swap(array &$arr,$a,$b,$flag = false){        // 遍歷i后面的元素，只要該元素小于當前元素，就把較小的往前冒泡        if($arr[$a] > $arr[$b]){            $temp = $arr[$a];            $arr[$a] = $arr[$b];            $arr[$b] = $temp;            $flag = true;        }        return $flag;    }    /**     * 第一種寫法     * @param $arr 所要排序的數組     * @return mixed 返回的數組     */    function bubbleSort($arr) {        $len = count($arr);        if ($len <= 1) {return $arr;}        //該層循環控制 需要冒泡的輪數        for ($i = 0; $i < $len-1; $i++) {            //該層循環用來控制每輪 冒出一個數 需要比較的次數            for ($j = $i + 1; $j < $len; $j++) {                // 或者 $this->swap($arr,$j,$j+1);                $this->swap($arr,$i,$j);            }        }        return $arr;    }    //第二種寫法    html' target='_blank'>public function BubbleSort2($arr){        $len = count($arr);        if ($len <= 1) {return $arr;}        for ($i = 0;$i < $len-1;$i++){            //TODO 本趟排序開始前，交換標志應為假            $flag = false;            for ($j = 0;$j <= $len-2;$j++){                $flag = $this->swap($arr,$j,$j+1,$flag);            }            if(!$flag) return $arr;        }        return $arr;    }    //第三種寫法    function BubbleSort3(array &$arr){        $len = count($arr);        if ($len <= 1) {return $arr;}        for($i = 0;$i < $len-1;$i++){            //從后往前逐層上浮小的元素 $j >= 0            for($j = $len - 2;$j >= $i ;$j --){                $this->swap($arr,$j,$j+1);            }        }        return $arr;    }    //第四種寫法    function bubbleSort4($arr)    {        $len = count($arr);        if ($len <= 1) {return $arr;}        for($i = 0;$i < $len-1;$i++) {            for($j = 0;$j < $len-$i-1;$j++) {                $this->swap($arr,$j,$j+1);            }        }        return $arr;    }

小結：

時間復雜度：O(n^2)

補充：可使用PHP內置函數 sort()或rsort().

上述函數對索引數組按照鍵值進行排序，為 array 中的單元賦予新的鍵名，這將刪除原有的鍵名而不僅是重新排序。如果成功則返回 TRUE，否則返回 FALSE

【二】.選擇排序

思路分析：
每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完

代碼實現

   /*    * @param 選擇排序法    * 每一次從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數據元素排完    * */    function selectSort($arr){        //雙重循環完成，外層控制輪數，內層控制比較次數        $len = count($arr);        if ($len <= 1) {return $arr;}        for ($i = 0; $i < $len-1; $i++) {            $minIndex = $i;            // 找出i后面最小的元素與當前元素交換            for ($j = $i + 1; $j < $len; $j++) {                if ($arr[$minIndex] > $arr[$j]){                    $minIndex = $j;                }            }            if ($minIndex != $i) {                $temp = $arr[$i];                $arr[$i] = $arr[$minIndex];                $arr[$minIndex] = $temp;            }        }        return $arr;    }

小結：

時間復雜度：O(n^2)

不穩定的排序方法（比如序列[5， 5， 3]第一次就將第一個[5]與[3]交換，導致第一個5挪動到第二個5后面）。

在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了

最好情況是，已經有序，交換0次；最壞情況交換n-1次，逆序交換n/2次。交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快

【三】.插入排序

思路分析：

每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。(從而得到一個新的、個數加一的有序數據)

描述：

⒈ 從第一個元素開始，該元素可以認為已經被排序

⒉ 取出下一個元素，在已經排序的元素序列中從后向前掃描

⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置

⒋ 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置

⒌ 將新元素插入到下一位置中

⒍ 重復步驟 2~5

代碼實現

此處提供兩種寫法，主要是循環的寫法稍有不同，可作參考.

   /*    * 插入排序法    * 每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。    * */    function insertSort($arr){        $len = count($arr);        if ($len <= 1) {return $arr;}        //先默認$array[0]，已經有序，是有序表        for($i = 1;$i < $len;$i++){            if ($arr[$i] < $arr[$i-1]){                $insertVal = $arr[$i]; //$insertVal是準備插入的數                $insertIndex = $i - 1; //有序表中準備比較的數的下標                while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){                    $arr[$insertIndex + 1] = $arr[$insertIndex]; //將數組往后挪                    $insertIndex--; //將下標往前挪，準備與前一個進行比較                }                if($insertIndex + 1 !== $i){                    $arr[$insertIndex + 1] = $insertVal;                }            }        }        return $arr;    }    function insertSort2($arr){        $len = count($arr);        if ($len <= 1) {return $arr;}        //先默認$array[0]，已經有序，是有序表        for($i = 1;$i < $len;$i++){            if ($arr[$i] < $arr[$i-1]){                $insertVal = $arr[$i]; //$insertVal是準備插入的數                //$j 有序表中準備比較的數的下標                //$j-- 將下標往前挪，準備與前一個進行比較                for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){                    $arr[$j+1]= $arr[$j];//將數組往后挪                }                $arr[$j + 1] = $insertVal;            }        }        return $arr;    }

小結：

時間復雜度：O(n^2)

空間復雜度：O(1) (用于記錄需要插入的數據)

穩定的排序方法

算法適用于少量數據的排序

如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。

【四】.快速排序

思路分析：

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，

然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列

代碼實現

注：網上多數為quick_sort2（）這類的寫法，感覺并非原算法的描述，建議可做參考.

或許代碼quick_sort()有所欠缺，并未發現能有較快的排序效果，尷尬了.

   /**     * @param $arr 目標數組     * @param int $l 左起坐標     * @param $r 右起坐標 初始化傳入數組時，$r = count($arr)-1     * @return mixed     */    public  function quick_sort(&$arr, $l=0, $r)    {        $length = count($arr);        //先判斷是否需要繼續進行 遞歸出口:數組長度為1，直接返回數組        if(!is_array($arr)||$length <= 1) {return $arr;}        if ($l < $r)        {            $i = $l;            $j = $r;            $baseVal = $arr[$l];            while ($i < $j)            {                // 從右向左找第一個小于$baseVal的數                while($i < $j && $arr[$j] >= $baseVal)                    $j--;                if($i < $j)                    $arr[$i++] = $arr[$j];                // 從左向右找第一個大于等于$baseVal的數                while($i < $j && $arr[$i] < $baseVal)                    $i++;                if($i < $j)                    $arr[$j--] = $arr[$i];            }            $arr[$i] = $baseVal;            $this->quick_sort($arr, $l, $i - 1); // 遞歸調用            $this->quick_sort($arr, $i + 1, $r);            return $arr;        }    }    /*    * 快速排序法    * */    public function quick_sort2($arr) {        $length = count($arr);        //先判斷是否需要繼續進行 遞歸出口:數組長度為1，直接返回數組        if(!is_array($arr)||$length <= 1) {return $arr;}        //選擇第一個元素作為基準        $baseValue = $arr[0];        //遍歷除了標尺外的所有元素，按照大小關系放入兩個數組內        //初始化兩個數組        $leftArr = array();  //小于基準的        $rightArr = array();  //大于基準的        //使用for循環進行遍歷，把選定的基準當做比較的對象        for($i = 1; $i<$length; $i++) {            if( $arr[$i] < $baseValue) {                //放入左邊數組                $leftArr[] = $arr[$i];            } else {                //放入右邊數組                $rightArr[] = $arr[$i];            }        }        //再分別對左邊和右邊的數組進行相同的排序處理方式遞歸調用這個函數        $leftArr = $this->quick_sort2($leftArr);        $rightArr = $this->quick_sort2($rightArr);        //合并 左邊 標尺 右邊， 注意：array($baseValue),關聯著重復數據        return array_merge($leftArr, array($baseValue), $rightArr);    }

小結：

既不浪費空間又可以快一點的排序算法

最差時間復雜度O(N^2)，平均時間復雜度為O(NlogN)

【五】.計數排序

思路分析

計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等于i的元素的個數。然后根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序

算法描述：

找出待排序的數組中最大和最小的元素；

統計數組中每個值為i的元素出現的次數，存入數組C的第i項；

對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；

反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

代碼實現

   /**     * 計數排序     * @param $arr     * @return array     */    function countingSort($arr)    {        $len = count( $arr );        if( $len <= 1 ) return $arr;        // 找出待排序的數組中最大值和最小值        $min = min($arr);        $max = max($arr);        // 計算待排序的數組中每個元素的個數        $countArr = array();        for($i = $min; $i <= $max; $i++)        {            $countArr[$i] = 0;        }        foreach($arr as $v)        {            $countArr[$v] +=  1;        }        $resArr = array();        foreach ($countArr as $k=>$c) {            for($i = 0; $i < $c; $i++)            {                $resArr[] = $k;            }        }        return $resArr;    }

小結：

計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。
作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

計數排序不是比較排序，排序的速度快于任何比較排序算法

最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n+k)
平均情況：T(n) = O(n+k)

限制條件很多注意

【六】.桶排序

思路分析

假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排)

算法描述

設置一個定量的數組當作空桶；

遍歷輸入數據，并且把數據一個一個放到對應的桶里去；

對每個不是空的桶進行排序；

從不是空的桶里把排好序的數據拼接起來。

代碼實現

   /**     * 木桶排序設計     * @param $arr 目標數組     * @param int $bucketCount 分配的木桶數目（整數）     * @return array     */    public function bucketSort($arr,$bucketCount = 10)    {        $len = count($arr);        $max = max($arr)+1;        if ($len <= 1) {return $arr;}        //填充木桶        $arrFill = array_fill(0, $bucketCount, []);        //開始標示木桶        for($i = 0; $i < $len ; $i++)        {            $key = intval($arr[$i]/($max/$bucketCount));            array_push($arrFill[$key] , $arr[$i]);            //TODO 測試發現：如果此處調用，耗時翻倍            /*if(count($arrFill[$key])){                $arrFill[$key] = $this->insertSort($arrFill[$key]);            }*/        }        //對每個不是空的桶進行排序        foreach ($arrFill as $key=>$f){            if (count($f)){                $arrFill[$key] = $this->insertSort($f);            }        }        //開始從木桶中拿出數據        for($i = 0; $i < count($arrFill); $i ++)        {            if($arrFill[$i]){                for($j = 0; $j <= count($arrFill[$i]); $j++)                {   //這一行主要用來控制輸出多個數字                    if ($arrFill[$i][$j]){                        $arrBucket[] = $arrFill[$i][$j];                    }                }            };        }        return $arrBucket;    }

注：

上述代碼是我根據對木桶排序的定義進行的設計，因為網上多數的PHP代碼感覺不合規范，其中的insertSort()為借用的文中所寫的插入排序

通過測試發現，此方法耗時比countingSort()要長好多，此處僅做參考不做推薦。

總結：

當輸入的元素是n 個0到k之間的整數時，它的運行時間是 O(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。由于用來計數的數組C的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于數據范圍很大的數組，需要大量時間和內存。

穩定的排序方法

桶排序是計數排序的升級版

最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n^2)
平均情況：T(n) = O(n+k)

附錄

【1】排序算法總結

【2】自行分析

此處提供一個網上多數作為“桶排序”的類似代碼段,個人認為并非描述中的排序算法，倒是與文中涉及到的“計數排序”更為契合.

  /**     * @param $arr 目標數組     * @return array 返回的已排序數組     */    public function bOrCSort($arr)    {        $len = count($arr);        $max = max($arr);        if ($len <= 1) {return $arr;}        //填充木桶        $arrFill = array_fill(0, $max, 0);        for($i = 0; $i < $len ; $i++)        {            $arrFill[$arr[$i]] ++;        }        //開始從木桶中拿出數據        for($i = 0; $i <= $max; $i ++)        {            for($j = 1; $j <= $arrFill[$i]; $j++)            { //這一行主要用來控制輸出多個數字                $arrRes[] = $i;            }        }        return $arrRes;    }

【3】用時測試

為了簡單比較幾種算法的用時大小，本人隨機生成了數量為10000，數值在300以內的測試數組，文中介紹的算法用時如下：

bucketsort 用時：1013.6640071869 ms
countingSort 用時：5.6858062744141 ms
quick_sort 用時：66540.108919144 ms
selectSort 用時：15234.955072403 ms
bubbleSort 用時：162055.89604378 ms
insertSort 用時：12029.093980789 ms
內置sort 用時：3.0169486999512 ms

所以，簡單需求的數組排序處理還是建議使用內置的sort()函數.