PHP實(shí)現(xiàn)常用排序算法的方法

更新時(shí)間：2020年02月05日 14:55:04 作者：歪麥

本文主要介紹了一些常用的排序算法，以及PHP的代碼實(shí)現(xiàn)等，感興趣的朋友跟隨小編一起看看吧

本文主要介紹了一些常用的排序算法，以及PHP的代碼實(shí)現(xiàn)等，希望對您能有所幫助。

本文來自于awaimai.com,由火龍果軟件Luca編輯推薦。

作為phper，一般接觸算法的編程不多。

但基本的排序算法還是應(yīng)該掌握。

畢竟算法作為程序的核心，算法的好壞決定了程序的質(zhì)量。

本文將依次介紹一些常用的排序算法，以及PHP實(shí)現(xiàn)。

1 快速排序

快速排序是由東尼·霍爾發(fā)展的一種排序算法。

在平均狀況下，排序 n 個(gè)項(xiàng)目要Ο(n log n)次比較。

在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。

事實(shí)上，快速排序通常明顯比其他Ο(n log n) 算法更快，因?yàn)樗膬?nèi)部循環(huán)可以在大部分的架構(gòu)上，很有效率地被實(shí)現(xiàn)出來。

快速排序采用分治法實(shí)現(xiàn)排序，具體步驟：

從數(shù)列中挑出一個(gè)數(shù)作為基準(zhǔn)元素。通常選擇第一個(gè)或最后一個(gè)元素。

掃描數(shù)列，以基準(zhǔn)元素為比較對象，把數(shù)列分成兩個(gè)區(qū)。規(guī)則是：小的移動(dòng)到基準(zhǔn)元素前面，大的移到后面，相等的前后都可以。分區(qū)完成之后，基準(zhǔn)元素就處于數(shù)列的中間位置。

然后再用同樣的方法，遞歸地排序劃分的兩部分。

遞歸的結(jié)束條件是數(shù)列的大小是0或1，也就是永遠(yuǎn)都已經(jīng)被排序好了。

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

function quickSort($arr)
 {
 $len = count($arr); 
 // 先設(shè)定結(jié)束條件，判斷是否需要繼續(xù)進(jìn)行
 if($len <= 1) {
 return $arr;
 } 
 
 // 選擇第一個(gè)元素作為基準(zhǔn)元素
 $pivot = $arr[0]; 
 
 // 初始化左數(shù)組
 $left = $right = array(); 
 
// 初始化大于基準(zhǔn)元素的右數(shù)組
 $right = array(); 
 
 // 遍歷除基準(zhǔn)元素外的所有元素，按照大小關(guān)系放入左右數(shù)組內(nèi)
 for ($i = 1; $i < $len ; $i++) {
 if ($arr[$i] < $pivot) {
 $left[] = $arr[$i];
 } else {
 $right[] = $arr[$i];
 }
 } 
 
 // 再分別對左右數(shù)組進(jìn)行相同的排序
 $left = quickSort($left);
 $right = quickSort($right); 
 
 // 合并基準(zhǔn)元素和左右數(shù)組
 return array_merge($left, array($pivot), $right);
 }

原地排序版本，不需要額外的存儲(chǔ)空間：

function partition(&$arr, $leftIndex, $rightIndex)
 {
 $pivot = $arr[($leftIndex + $rightIndex) / 2]; 
 while ($leftIndex <= $rightIndex) {
 while ($arr[$leftIndex] < $pivot) {
 $leftIndex++;
 }

 while ($arr[$rightIndex] > $pivot) {
 $rightIndex--;
 }
 
 if ($leftIndex <= $rightIndex) {
 list($arr[$leftIndex], $arr[$rightIndex]) = [$arr[$rightIndex], $arr[$leftIndex]]; 

 $leftIndex++;
 $rightIndex--;
 }
 } 

 return $leftIndex;
 }
 
function quickSort(&$arr, $leftIndex, $rightIndex)
 {
 if ($leftIndex < $rightIndex) {
 $index = partition($arr, $leftIndex, $rightIndex);
 
 quickSort($arr, $leftIndex, $index - 1);
 quickSort($arr, $index, $rightIndex);
 }
 }

2 冒泡排序

冒泡排序是一種簡單的排序算法。

算法重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。

走訪數(shù)列的工作重復(fù)地進(jìn)行，直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。

因?yàn)榕判蜻^程讓較大的數(shù)往下沉，較小的往上冒，故而叫冒泡法。

算法步驟：

從第一個(gè)元素開始，比較相鄰的元素，如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

從開始第一對到結(jié)尾的最后一對，對每一對相鄰元素作同樣的工作。比較結(jié)束后，最后的元素應(yīng)該會(huì)是最大的數(shù)。

對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

重復(fù)上面的步驟，每次比較的對數(shù)會(huì)越來越少，直到?jīng)]有任何一對數(shù)字需要比較。

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

function bubbleSort($arr)
 {
 $len = count($arr);
 
 for($i = 1; $i < $len; $i++) {
 for($k = 0; $k < $len - $i; $k++) {
 if($arr[$k] > $arr[$k + 1]) {
 $tmp = $arr[$k + 1];
 $arr[$k + 1] = $arr[$k];
 $arr[$k] = $tmp;
 }
 }
 } 
 return $arr;
 }

3 插入排序

插入排序是一種簡單直觀的排序算法。

插入排序的工作原理是：將需要排序的數(shù)，與前面已經(jīng)排好序的數(shù)據(jù)從后往前進(jìn)行比較，使其插入到相應(yīng)的位置。

插入排序在實(shí)現(xiàn)上，通常采用in-place排序，即只需用到O(1)的額外空間的排序。

因而，在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

算法步驟：

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

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

如果以排序的元素大于新元素，將該元素移到下一位置；

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

將新元素插入到該位置中；

重復(fù)步驟2。

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

function insertSort($arr)
 {
 $len = count($arr); 
 
 for ($i = 1; $i < $len; $i++) {
 $tmp = $arr[$i];
 for ($j = $i - 1; $j >= 0; $j--) {
 if ($tmp < $arr[$j]) {
 $arr[$j + 1] = $arr[$j];
 $arr[$j] = $tmp;
 } else {
 break;
 }
 }
 }
 
 return $arr;
 }

4 選擇排序

選擇排序是一種簡單直觀的排序算法。

算法步驟：

首先，在序列中找到最小元素，存放到排序序列的起始位置；

接著，從剩余未排序元素中繼續(xù)尋找最小元素，放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢。

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

function selectSort($arr)
 {
 $len = count($arr); 
 for ($i = 0; $i < $len; $i++) {
 $p = $i;
 
 for ($j = $i + 1; $j < $len; $j++) {
 if ($arr[$p] > $arr[$j]) {
 $p = $j;
 }
 }
 
 $tmp = $arr[$p];
 $arr[$p] = $arr[$i];
 $arr[$i] = $tmp;
 }
 
 return $arr;
 }

5 歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。

歸并排序?qū)⒋判虻男蛄蟹殖扇舾山M，保證每組都有序，然后再進(jìn)行合并排序，最終使整個(gè)序列有序。

該算法是采用分治法的一個(gè)非常典型的應(yīng)用。

算法步驟：

申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；

設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動(dòng)指針到下一位置

重復(fù)步驟3直到某一指針達(dá)到序列尾

將另一序列剩下的所有元素直接復(fù)制到合并序列尾

排序效果：

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

/**
 * 歸并排序
 *
 * @param array $lists
 * @return array
 */
 function merge_sort(array $lists)
 {
 $n = count($lists);
 if ($n <= 1) {
 return $lists;
 }
 $left = merge_sort(array_slice($lists, 0, floor($n / 2)));
 $right = merge_sort(array_slice($lists, floor($n / 2)));
 $lists = merge($left, $right);
 return $lists;
 } 
function merge(array $left, array $right)
 {
 $lists = [];
 $i = $j = 0;
 while ($i < count($left) && $j < count($right)) {
 if ($left[$i] < $right[$j]) {
 $lists[] = $left[$i];
 $i++;
 } else {
 $lists[] = $right[$j];
 $j++;
 }
 }
 $lists = array_merge($lists, array_slice($left, $i));
 $lists = array_merge($lists, array_slice($right, $j));
 return $lists;
 }

6 堆排序

堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。

堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

堆排序的平均時(shí)間復(fù)雜度為Ο(nlogn) 。

算法步驟：

創(chuàng)建一個(gè)堆H[0..n-1]；

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小1，并調(diào)用shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；

重復(fù)步驟2，直到堆的尺寸為1。

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

/**
 * 堆排序
 *
 * @param array $lists
 * @return array
 */
 function heap_sort(array $lists)
 {
 $n = count($lists);
 build_heap($lists);
 while (--$n) {
 $val = $lists[0];
 $lists[0] = $lists[$n];
 $lists[$n] = $val;
 heap_adjust($lists, 0, $n);
 //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL;
 }
 return $lists;
 } 
function build_heap(array &$lists)
 {
 $n = count($lists) - 1;
 for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
 heap_adjust($lists, $i, $n + 1);
 //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL;
 }
 //echo "build ok: " . implode(', ', $lists) . PHP_EOL;
 }

 function heap_adjust(array &$lists, $i, $num)
 {
 if ($i > $num / 2) {
 return;
 }
 $key = $i;
 $leftChild = $i * 2 + 1;
 $rightChild = $i * 2 + 2;
 
 if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
 $key = $leftChild;
 }
 if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
 $key = $rightChild;
 }
 if ($key != $i) {
 $val = $lists[$i];
 $lists[$i] = $lists[$key];
 $lists[$key] = $val;
 heap_adjust($lists, $key, $num);
 }
 }

7 希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。

但希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率

但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位

算法步驟：

先將整個(gè)待排序的記錄序列分割成為若干子序列，分別進(jìn)行直接插入排序

待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行依次直接插入排序。

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

/**
 * 希爾排序 標(biāo)準(zhǔn)
 *
 * @param array $lists
 * @return array
 */
 function shell_sort(array $lists)
 {
 $n = count($lists);
 $step = 2;
 $gap = intval($n / $step);
 while ($gap > 0) {
 for ($gi = 0; $gi < $gap; $gi++) {
 for ($i = $gi; $i < $n; $i += $gap) {
 $key = $lists[$i];
 for ($j = $i - $gap; $j >= 0 && $lists[$j] > $key; $j -= $gap) {
 $lists[$j + $gap] = $lists[$j];
 $lists[$j] = $key;
 }
 }
 }
 $gap = intval($gap / $step);
 }
 return $lists;
 }

8 基數(shù)排序

基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。

由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

說基數(shù)排序之前，我們簡單介紹桶排序：

桶排序是將陣列分到有限數(shù)量的桶子里。

每個(gè)桶子再個(gè)別排序，有可能再使用別的排序算法，或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序。

桶排序是鴿巢排序的一種歸納結(jié)果。

當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間O(n)。

但桶排序并不是比較排序，他不受到 O(n log n) 下限的影響。

簡單來說，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，然后對每個(gè)桶里面的在進(jìn)行排序。

例如，要對大小為[1..1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序

首先，可以把桶設(shè)為大小為10的范圍，具體而言，設(shè)集合B[1]存儲(chǔ)[1..10]的整數(shù)，集合B[2]存儲(chǔ) (10..20]的整數(shù)，……集合B[i]存儲(chǔ)( (i-1)*10, i*10]的整數(shù)，i = 1,2,..100?？偣灿?100個(gè)桶。

然后，對A[1..n]從頭到尾掃描一遍，把每個(gè)A[i]放入對應(yīng)的桶B[j]中。再對這100個(gè)桶中每個(gè)桶里的數(shù)字排序，這時(shí)可用冒泡，選擇，乃至快排，一般來說任何排序法都可以。

最后，依次輸出每個(gè)桶里面的數(shù)字，且每個(gè)桶中的數(shù)字從小到大輸出，這樣就得到所有數(shù)字排好序的一個(gè)序列了。

假設(shè)有n個(gè)數(shù)字，有m個(gè)桶，如果數(shù)字是平均分布的，則每個(gè)桶里面平均有n/m個(gè)數(shù)字。

如果對每個(gè)桶中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是

O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)

從上式看出，當(dāng)m接近n的時(shí)候，桶排序復(fù)雜度接近O(n)

當(dāng)然，以上復(fù)雜度的計(jì)算是基于輸入的n個(gè)數(shù)字是平均分布這個(gè)假設(shè)的。這個(gè)假設(shè)是很強(qiáng)的，實(shí)際應(yīng)用中效果并沒有這么好。如果所有的數(shù)字都落在同一個(gè)桶中，那就退化成一般的排序了。

前面說的幾大排序算法，大部分時(shí)間復(fù)雜度都是O（n2），也有部分排序算法時(shí)間復(fù)雜度是O(nlogn)。而桶式排序卻能實(shí)現(xiàn)O（n）的時(shí)間復(fù)雜度。但桶排序的缺點(diǎn)是：

1）首先是空間復(fù)雜度比較高，需要的額外開銷大。排序有兩個(gè)數(shù)組的空間開銷，一個(gè)存放待排序數(shù)組，一個(gè)就是所謂的桶，比如待排序值是從0到m-1，那就需要m個(gè)桶，這個(gè)桶數(shù)組就要至少m個(gè)空間。

2）其次待排序的元素都要在一定的范圍內(nèi)等等。

/**
 * 基數(shù)排序
 *
 * @param array $lists
 * @return array
 */
 function radix_sort(array $lists)
 {
 $radix = 10;
 $max = max($lists);
 $k = ceil(log($max, $radix));
 if ($max == pow($radix, $k)) {
 $k++;
 }
 for ($i = 1; $i <= $k; $i++) {
 $newLists = array_fill(0, $radix, []);
 for ($j = 0; $j < count($lists); $j++) {
 $key = $lists[$j] / pow($radix, $i - 1) % $radix;
 $newLists[$key][] = $lists[$j];
 }
 $lists = [];
 for ($j = 0; $j < $radix; $j++) {
 $lists = array_merge($lists, $newLists[$j]);
 }
 }
 return $lists;
 }

9 總結(jié)

各種排序的穩(wěn)定性，時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性總結(jié)如下圖：