本文主要介紹了一些常用的排序算法,以及PHP的代碼實(shí)現(xiàn)等,希望對(duì)您能有所幫助。
本文來自于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)元素為比較對(duì)象,把數(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];
}
}
// 再分別對(duì)左右數(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è)。
從開始第一對(duì)到結(jié)尾的最后一對(duì),對(duì)每一對(duì)相鄰元素作同樣的工作。比較結(jié)束后,最后的元素應(yīng)該會(huì)是最大的數(shù)。
對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
重復(fù)上面的步驟,每次比較的對(duì)數(shù)會(huì)越來越少,直到?jīng)]有任何一對(duì)數(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)用。
算法步驟:
申請(qǐng)空間,使其大小為兩個(gè)已經(jīng)排序序列之和,該空間用來存放合并后的序列;
設(shè)定兩個(gè)指針,最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間,并移動(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)方法的:
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí), 效率高, 即可以達(dá)到線性排序的效率
但插入排序一般來說是低效的, 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位
算法步驟:
先將整個(gè)待排序的記錄序列分割成為若干子序列,分別進(jìn)行直接插入排序
待整個(gè)序列中的記錄“基本有序”時(shí),再對(duì)全體記錄進(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è)的桶中,然后對(duì)每個(gè)桶里面的在進(jìn)行排序。
例如,要對(duì)大小為[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è)桶。
然后,對(duì)A[1..n]從頭到尾掃描一遍,把每個(gè)A[i]放入對(duì)應(yīng)的桶B[j]中。 再對(duì)這100個(gè)桶中每個(gè)桶里的數(shù)字排序,這時(shí)可用冒泡,選擇,乃至快排,一般來說任 何排序法都可以。
最后,依次輸出每個(gè)桶里面的數(shù)字,且每個(gè)桶中的數(shù)字從小到大輸出,這 樣就得到所有數(shù)字排好序的一個(gè)序列了。
假設(shè)有n個(gè)數(shù)字,有m個(gè)桶,如果數(shù)字是平均分布的,則每個(gè)桶里面平均有n/m個(gè)數(shù)字。
如果對(duì)每個(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é)如下圖:
關(guān)于時(shí)間復(fù)雜度:
(1)平方階(O(n2))排序
各類簡單排序:直接插入、直接選擇和冒泡排序;
(2)線性對(duì)數(shù)階(O(nlog2n))排序
快速排序、堆排序和歸并排序;
(3)O(n1+§))排序,§是介于0和1之間的常數(shù)。
希爾排序
(4)線性階(O(n))排序
基數(shù)排序,此外還有桶、箱排序。
關(guān)于穩(wěn)定性:
穩(wěn)定的排序算法:冒泡排序、插入排序、歸并排序和基數(shù)排序
不是穩(wěn)定的排序算法:選擇排序、快速排序、希爾排序、堆排序
總結(jié)
以上所述是小編給大家介紹的PHP實(shí)現(xiàn)常用排序算法,希望對(duì)大家有所幫助!
您可能感興趣的文章:- 50個(gè)優(yōu)秀經(jīng)典PHP算法大集合 附源碼
- php計(jì)數(shù)排序算法的實(shí)現(xiàn)代碼(附四個(gè)實(shí)例代碼)
- php經(jīng)典趣味算法實(shí)例代碼
- PHP常見算法合集代碼實(shí)例