常見(jiàn)的排序算法有：冒泡排序法，快速排序法，選擇排序法，插入排序法，本文做了一個(gè)PHP常見(jiàn)排序小結(jié)筆記，同時(shí)也希望能幫到你。

需求：將一個(gè)有多個(gè)數(shù)字的數(shù)組進(jìn)行從小到大的排序.

排序算法

【一】.冒泡排序

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

代碼實(shí)現(xiàn)：（舉例幾種寫(xiě)法，注意循環(huán)體的判斷條件）建議使用第一、二種。

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

小結(jié)：

時(shí)間復(fù)雜度：O(n^2)

補(bǔ)充：可使用PHP內(nèi)置函數(shù) sort()或rsort().

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

【二】.選擇排序

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

代碼實(shí)現(xiàn)

   /*    * @param 選擇排序法    * 每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完    * */    function selectSort($arr){        //雙重循環(huán)完成，外層控制輪數(shù)，內(nèi)層控制比較次數(shù)        $len = count($arr);        if ($len <= 1) {return $arr;}        for ($i = 0; $i < $len-1; $i++) {            $minIndex = $i;            // 找出i后面最小的元素與當(dāng)前元素交換            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;    }

小結(jié)：

時(shí)間復(fù)雜度：O(n^2)

不穩(wěn)定的排序方法（比如序列[5， 5， 3]第一次就將第一個(gè)[5]與[3]交換，導(dǎo)致第一個(gè)5挪動(dòng)到第二個(gè)5后面）。

在一趟選擇，如果一個(gè)元素比當(dāng)前元素小，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了

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

【三】.插入排序

思路分析：

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

描述：

⒈ 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序

⒉ 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

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

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

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

⒍ 重復(fù)步驟 2~5

代碼實(shí)現(xiàn)

此處提供兩種寫(xiě)法，主要是循環(huán)的寫(xiě)法稍有不同，可作參考.

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

小結(jié)：

時(shí)間復(fù)雜度：O(n^2)

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

穩(wěn)定的排序方法

算法適用于少量數(shù)據(jù)的排序

如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來(lái)減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。

【四】.快速排序

思路分析：

通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，

然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列

代碼實(shí)現(xiàn)

注：網(wǎng)上多數(shù)為quick_sort2（）這類的寫(xiě)法，感覺(jué)并非原算法的描述，建議可做參考.

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

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

小結(jié)：

既不浪費(fèi)空間又可以快一點(diǎn)的排序算法

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

【五】.計(jì)數(shù)排序

思路分析

計(jì)數(shù)排序使用一個(gè)額外的數(shù)組C，其中第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組C來(lái)將A中的元素排到正確的位置。它只能對(duì)整數(shù)進(jìn)行排序

算法描述：

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

統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；

對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）；

反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

代碼實(shí)現(xiàn)

   /**     * 計(jì)數(shù)排序     * @param $arr     * @return array     */    function countingSort($arr)    {        $len = count( $arr );        if( $len <= 1 ) return $arr;        // 找出待排序的數(shù)組中最大值和最小值        $min = min($arr);        $max = max($arr);        // 計(jì)算待排序的數(shù)組中每個(gè)元素的個(gè)數(shù)        $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;    }

小結(jié)：

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。
作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法

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

限制條件很多 注意

【六】.桶排序

思路分析

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

算法描述

設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；

遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去；

對(duì)每個(gè)不是空的桶進(jìn)行排序；

從不是空的桶里把排好序的數(shù)據(jù)拼接起來(lái)。

代碼實(shí)現(xiàn)

   /**     * 木桶排序設(shè)計(jì)     * @param $arr 目標(biāo)數(shù)組     * @param int $bucketCount 分配的木桶數(shù)目（整數(shù)）     * @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, []);        //開(kāi)始標(biāo)示木桶        for($i = 0; $i < $len ; $i++)        {            $key = intval($arr[$i]/($max/$bucketCount));            array_push($arrFill[$key] , $arr[$i]);            //TODO 測(cè)試發(fā)現(xiàn)：如果此處調(diào)用，耗時(shí)翻倍            /*if(count($arrFill[$key])){                $arrFill[$key] = $this->insertSort($arrFill[$key]);            }*/        }        //對(duì)每個(gè)不是空的桶進(jìn)行排序        foreach ($arrFill as $key=>$f){            if (count($f)){                $arrFill[$key] = $this->insertSort($f);            }        }        //開(kāi)始從木桶中拿出數(shù)據(jù)        for($i = 0; $i < count($arrFill); $i ++)        {            if($arrFill[$i]){                for($j = 0; $j <= count($arrFill[$i]); $j++)                {   //這一行主要用來(lái)控制輸出多個(gè)數(shù)字                    if ($arrFill[$i][$j]){                        $arrBucket[] = $arrFill[$i][$j];                    }                }            };        }        return $arrBucket;    }

注：

上述代碼是我根據(jù)對(duì)木桶排序的定義進(jìn)行的設(shè)計(jì)，因?yàn)榫W(wǎng)上多數(shù)的PHP代碼感覺(jué)不合規(guī)范，其中的insertSort()為借用的文中所寫(xiě)的插入排序

通過(guò)測(cè)試發(fā)現(xiàn)，此方法耗時(shí)比countingSort()要長(zhǎng)好多，此處僅做參考不做推薦。

總結(jié)：

當(dāng)輸入的元素是n 個(gè)0到k之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 O(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。

穩(wěn)定的排序方法

桶排序是計(jì)數(shù)排序的升級(jí)版

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

附錄

【1】排序算法總結(jié)

【2】自行分析

此處提供一個(gè)網(wǎng)上多數(shù)作為“桶排序”的類似代碼段,個(gè)人認(rèn)為并非描述中的排序算法，倒是與文中涉及到的“計(jì)數(shù)排序”更為契合.

  /**     * @param $arr 目標(biāo)數(shù)組     * @return array 返回的已排序數(shù)組     */    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]] ++;        }        //開(kāi)始從木桶中拿出數(shù)據(jù)        for($i = 0; $i <= $max; $i ++)        {            for($j = 1; $j <= $arrFill[$i]; $j++)            { //這一行主要用來(lái)控制輸出多個(gè)數(shù)字                $arrRes[] = $i;            }        }        return $arrRes;    }

【3】用時(shí)測(cè)試

為了簡(jiǎn)單比較幾種算法的用時(shí)大小，本人隨機(jī)生成了數(shù)量為10000，數(shù)值在300以內(nèi)的測(cè)試數(shù)組，文中介紹的算法用時(shí)如下：

bucketsort 用時(shí)：1013.6640071869 ms
countingSort 用時(shí)：5.6858062744141 ms
quick_sort 用時(shí)：66540.108919144 ms
selectSort 用時(shí)：15234.955072403 ms
bubbleSort 用時(shí)：162055.89604378 ms
insertSort 用時(shí)：12029.093980789 ms
內(nèi)置sort 用時(shí)：3.0169486999512 ms

所以，簡(jiǎn)單需求的數(shù)組排序處理還是建議使用內(nèi)置的sort()函數(shù).

相關(guān)閱讀：

PHP遍歷算法的總結(jié)

PHP如何實(shí)現(xiàn)折半查找算法

十大機(jī)器學(xué)習(xí)需要了解的算法

以上就是PHP常見(jiàn)排序算法學(xué)習(xí)的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注 其它相關(guān)文章！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。