PHP實現(xiàn)常見排序算法圖解(冒泡,插入,選擇,歸并,堆,希爾,基數(shù))
本文將依次介紹一些常用的排序算法，以及PHP實現(xiàn)。常見的排序算法，雖然很基礎，但是很見功力，如果能思路清晰，很快寫出來各個算法的代碼實現(xiàn)，還是需要花一點功夫的，今天，就跟大家盤點下常用的一些算法。
1 快速排序
快速排序是由東尼·霍爾發(fā)展的一種排序算法。
在平均狀況下，排序 n 個項目要Ο(n log n)次比較。
在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。
事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內(nèi)部循環(huán)可以在大部分的架構(gòu)上，很有效率地被實現(xiàn)出來。
快速排序采用分治法實現(xiàn)排序，具體步驟：
從數(shù)列中挑出一個數(shù)作為基準元素。通常選擇第一個或最后一個元素。
掃描數(shù)列，以基準元素為比較對象，把數(shù)列分成兩個區(qū)。規(guī)則是：小的移動到基準元素前面，大的移到后面，相等的前后都可以。分區(qū)完成之后，基準元素就處于數(shù)列的中間位置。
然后再用同樣的方法，遞歸地排序劃分的兩部分。
遞歸的結(jié)束條件是數(shù)列的大小是0或1，也就是永遠都已經(jīng)被排序好了。
PHP代碼實現(xiàn)：
function quickSort($arr) { // 先設定結(jié)束條件，判斷是否需要繼續(xù)進行
if(count($arr) <= 1) { return $arr;
} // 選擇第一個元素作為基準元素
$baseValue = $arr[0]; // 初始化小于基準元素的左數(shù)組
$leftArray = array(); // 初始化大于基準元素的右數(shù)組
$rightArray = array(); // 遍歷除基準元素外的所有元素，按照大小關(guān)系放入左右數(shù)組內(nèi)
array_shift($arr); foreach ($arr as $value) { if ($value < $baseValue) {
$leftArray[] = $value;
} else {
$rightArray[] = $value;
}
} // 再分別對左右數(shù)組進行相同的排序
$leftArray = quickSort($leftArray);
$rightArray = quickSort($rightArray); // 合并基準元素和左右數(shù)組
return array_merge($leftArray, array($baseValue), $rightArray);
}2 冒泡排序
冒泡排序是一種簡單的排序算法。
算法重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。
走訪數(shù)列的工作重復地進行，直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
因為排序過程讓較大的數(shù)往下沉，較小的往上冒，故而叫冒泡法。
算法步驟：
從第一個元素開始，比較相鄰的元素，如果第一個比第二個大，就交換他們兩個。
從開始第一對到結(jié)尾的最后一對，對每一對相鄰元素作同樣的工作。比較結(jié)束后，最后的元素應該會是最大的數(shù)。
對所有的元素重復以上的步驟，除了最后一個。
重復上面的步驟，每次比較的對數(shù)會越來越少，直到?jīng)]有任何一對數(shù)字需要比較。
PHP代碼實現(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ù)從后往前進行比較，使其插入到相應的位置。
插入排序在實現(xiàn)上，通常采用in-place排序，即只需用到O(1)的額外空間的排序。
因而，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
算法步驟：
從第一個元素開始，該元素可以認為已經(jīng)被排序；
取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；
如果以排序的元素大于新元素，將該元素移到下一位置；
重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
將新元素插入到該位置中；
重復步驟2。
PHP代碼實現(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ù)尋找最小元素，放到已排序序列的末尾。
重復第二步，直到所有元素均排序完畢。
PHP代碼實現(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īng)排序序列之和，該空間用來存放合并后的序列；
設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接復制到合并序列尾
排序效果：
PHP實現(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)所設計的一種排序算法。
堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。
堆排序的平均時間復雜度為Ο(nlogn) 。
算法步驟：
創(chuàng)建一個堆
H[0..n-1]；把堆首（最大值）和堆尾互換；
把堆的尺寸縮小
1，并調(diào)用shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應位置；重復步驟
2，直到堆的尺寸為1。
PHP實現(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 希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。
但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時， 效率高， 即可以達到線性排序的效率
但插入排序一般來說是低效的， 因為插入排序每次只能將數(shù)據(jù)移動一位
算法步驟：
先將整個待排序的記錄序列分割成為若干子序列，分別進行直接插入排序
待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
PHP實現(xià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ù)字，然后按每個位數(shù)分別比較。
由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
說基數(shù)排序之前，我們簡單介紹桶排序：
桶排序是將陣列分到有限數(shù)量的桶子里。
每個桶子再個別排序，有可能再使用別的排序算法，或是以遞回方式繼續(xù)使用桶排序進行排序。
桶排序是鴿巢排序的一種歸納結(jié)果。
當要被排序的陣列內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間O(n)。
但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
簡單來說，就是把數(shù)據(jù)分組，放在一個個的桶中，然后對每個桶里面的在進行排序。
例如，要對大小為[1..1000]范圍內(nèi)的n個整數(shù)A[1..n]排序
首先，可以把桶設為大小為10的范圍，具體而言，設集合B[1]存儲[1..10]的整數(shù)，集合B[2]存儲 (10..20]的整數(shù)，……集合B[i]存儲( (i-1)*10, i*10]的整數(shù)，i = 1,2,..100?？偣灿?nbsp; 100個桶。
然后，對A[1..n]從頭到尾掃描一遍，把每個A[i]放入對應的桶B[j]中。 再對這100個桶中每個桶里的數(shù)字排序，這時可用冒泡，選擇，乃至快排，一般來說任 何排序法都可以。
最后，依次輸出每個桶里面的數(shù)字，且每個桶中的數(shù)字從小到大輸出，這 樣就得到所有數(shù)字排好序的一個序列了。
假設有n個數(shù)字，有m個桶，如果數(shù)字是平均分布的，則每個桶里面平均有n/m個數(shù)字。
如果對每個桶中的數(shù)字采用快速排序，那么整個算法的復雜度是
O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)
從上式看出，當m接近n的時候，桶排序復雜度接近O(n)
當然，以上復雜度的計算是基于輸入的n個數(shù)字是平均分布這個假設的。這個假設是很強的 ，實際應用中效果并沒有這么好。如果所有的數(shù)字都落在同一個桶中，那就退化成一般的排序了。
前面說的幾大排序算法 ，大部分時間復雜度都是O（n2），也有部分排序算法時間復雜度是O(nlogn)。而桶式排序卻能實現(xiàn)O（n）的時間復雜度。但桶排序的缺點是：
1）首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數(shù)組的空間開銷，一個存放待排序數(shù)組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數(shù)組就要至少m個空間。
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)定性，時間復雜度、空間復雜度、穩(wěn)定性總結(jié)如下圖：
關(guān)于時間復雜度：
(1)平方階(O(n2))排序
各類簡單排序:直接插入、直接選擇和冒泡排序；
(2)線性對數(shù)階(O(nlog2n))排序
快速排序、堆排序和歸并排序；
(3)O(n1+§))排序,§是介于0和1之間的常數(shù)。
希爾排序
(4)線性階(O(n))排序
基數(shù)排序，此外還有桶、箱排序。
關(guān)于穩(wěn)定性：
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序
總結(jié)：
冒泡排序
思路：在要排序的一組數(shù)中，對當前還未排好的序列，從前往后對相鄰的兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即，每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換
時間復雜度為：O(n2)
快速排序
思路：選擇一個基準元素，通常選擇第一個元素或者最后一個元素。通過一趟掃描，將待排序列分成兩部分，一部分比基準元素小，一部分大于等于基準元素。此時基準元素在其排好序后的正確位置，然后再用同樣的方法遞歸地排序劃分的兩部分
時間復雜度：O(n*log2n)
插入排序
思路：將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止
時間復雜度：O(n2)
選擇排序
思路：在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當中再找最小（或者最大）的與第2個位置的數(shù)交換，依次類推，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止
時間復雜度：O(n2)
<?php
//冒泡排序
function bubbleSort($arr){
$len=count($arr);
if($len<=1){ return $arr;}
for($i=0;$i<$len;$i++){//冒泡的輪數(shù)
for($j=$len-1;$j>$i;$j--){ //冒出一個數(shù) 需要比較的次數(shù)
if($arr[$j-1]>$arr[$j]){
$tmp=$arr[$j];
$arr[$j]=$arr[$j-1];
$arr[$j-1]=$tmp;
}
}
//echo implode(" ",$arr).'<br/>';
}
return $arr;
}
//快速排序
function quickSort($arr){
$len=count($arr);
if($len<=1){ return $arr;}
$base=$arr[0];//第一個元素作為基準
$left=array();
$right=array();
for($i=1;$i<$len;$i++){//遍歷除了基準外的所有元素，比它小放左，比它大放右
if($base>$arr[$i]){
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//再分別對左邊和右邊的數(shù)組進行相同的排序處理方式遞歸調(diào)用這個函數(shù)
$left=quickSort($left);
$right=quickSort($right);
return array_merge($left,array($base),$right);//合并
}
//插入排序
function insertSort($arr){
$len=count($arr);
if($len<=1){ return $arr;}
for($i=1;$i<$len;$i++){
$tmp=$arr[$i];
for($j=$i-1;$j>=0;$j--){ //內(nèi)層循環(huán)控制，比較并插入
if($tmp<$arr[$j]){//發(fā)現(xiàn)插入的元素要小，交換位置，將后邊的元素與前面的元素互換
$arr[$j+1]=$arr[$j];
$arr[$j]=$tmp;
}
}
}
return $arr;
}
//選擇排序
function selectSort($arr){
$len=count($arr);
if($len<=1){ return $arr;}
for($i=0;$i<$len-1;$i++){
$p=$i;//先假設最小的值的位置
for($j=$i+1;$j<$len;$j++){
if($arr[$p]>$arr[$j]){//$arr[$p] 是當前已知的最小值
$p=$j;//比較，發(fā)現(xiàn)更小的,記錄下最小值的位置；并且在下次比較時采用已知的最小值進行比較。
}
}
//已經(jīng)確定了當前的最小值的位置，保存到$p中。如果發(fā)現(xiàn)最小值的位置與當前假設的位置$i不同，則位置互換即可。
if($p!=$i){
$tmp=$arr[$p];
$arr[$p]=$arr[$i];
$arr[$i]=$tmp;
}
}
return $arr;
}
$arr=array(3,2,4,1);
echo implode(" ",bubbleSort($arr)).'<br/>';
echo implode(" ",quickSort($arr)).'<br/>';
echo implode(" ",insertSort($arr)).'<br/>';
echo implode(" ",selectSort($arr)).'<br/>';如對本文有疑問，請?zhí)峤坏浇涣髡搲瑥V大熱心網(wǎng)友會為你解答??！ 點擊進入論壇
