在PHP中已經(jīng)有現(xiàn)成的函數(shù)幫助我們?yōu)閿?shù)組排序，那我們還有必要去自己實現(xiàn)為數(shù)組排序的算法嗎？有的。我們知道其實 程序 = 數(shù)據(jù)結構 + 算法，可見算法在我們程序中是非常關鍵的組成部分，好的算法可以讓程序的執(zhí)行效率更高，占用空間更少。
舉個例子，我們寫一個計算1+2+3+4+……+999+1000的程序，方法1我們可以先計算1+2 = 3，然后計算3+3 = 6，然后計算6+4 = 10 ，然后 10+5 =15 …… 計算999次，最后得到結果。方法2我們可以使用中學學過的等差數(shù)列求和公式Sn=n(a1+an)/2 ， 直接計算1000 * （1+1000）/ 2 得到結果，使用方法2的程序只需計算1次，就能得到結果，所以效率更高。這就是算法的作用和魅力所在。
下面我們通過排序算法了解計算機是怎么為我們的數(shù)組排序的，去入門算法。
注：為方便描述，下面的排序全為正序（從小到大排序）
一、冒泡排序
假設有一個數(shù)組[a,b,c,d]
冒泡排序依次比較相鄰的兩個元素，如果前面的元素大于后面的元素，則兩元素交換位置；否則，位置不變。具體步驟：
1，比較a,b這兩個元素，如果a>b,則交換位置，數(shù)組變?yōu)椋篬b,a,c,d]
2，比較a,c這兩個元素，如果a<c,則位置不變，數(shù)組變?yōu)椋篬b,a,c,d]
3，比較c,d這兩個元素，如果c>d,則交換位置，數(shù)組變?yōu)椋篬b,a,d,c]
完成第一輪比較后，可以發(fā)現(xiàn)最大的數(shù)c已經(jīng)排（冒）在最后面了，接著再進行第二輪比較，但第二輪比較不必比較最后一個元素了，因為最后一個元素已經(jīng)是最大的了。
第二輪比較結束后，第二大的數(shù)也會冒到倒數(shù)第二的位置。
依次類推，再進行第三輪，，，
就這樣最大的數(shù)一直往后排（冒），最后完成排序。所以我們稱這種排序算法為冒泡排序。
$arr = [9,4,7,1,8,6,3,10,2];
function bubbleSort($arr)
{
$len = count($arr);
//該層循環(huán)輪數(shù)
for ($i = 1; $i < $len; $i++) {
//該層依次比較相鄰的兩個數(shù)
for ($k = 0; $k < $len - $i; $k++) {
//如果前面的元素大于后面的元素，調(diào)換位置：
if ($arr[$k] > $arr[$k + 1]) {
$tmp = $arr[$k + 1]; // 聲明一個臨時變量
$arr[$k + 1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}
$arr = bubbleSort($arr);
print_r($arr);
二、選擇排序
選擇排序是一種直觀的算法，每一輪會選出列中最小的值，把最小值排到前面。具體步驟如下:
- 第一輪，先把數(shù)組中的第一個元素作為最小值，最小值的位置（索引）保存在一個變量$min中
- 接著拿第二個元素與我們初始設定的最小值比較，如果第二個元素比最小值小，那么$min的值變?yōu)榈诙€元素的位置（索引），否則，不做處理。
- 接著同樣的去拿最新的最小值與第三個元素比較，與第四個，第五個，，，到最后，這得到的$min就是數(shù)組中的最小值, 然后把最小值與第一個元素交換位置，至此，第一輪循環(huán)結束。
4，用同樣的方法進行第二輪查找，找到第二個最小值，與第二個元素交換位置；然后第三個，第四個，直至排序完成
$arr = [9,4,7,1,8,6,3,10,2];
//實現(xiàn)思路 雙重循環(huán)完成，外層控制輪數(shù)，當前的最小值。內(nèi)層控制比較次數(shù)
function selectSort($arr) {
$len = count($arr);
//$i 當前最小值的位置， 需要參與比較的元素
for ($i = 0; $i < $len - 1; $i++) {
//先假設最小的值的位置
$min = $i;
//所以$arr[$min] 是 當前已知的最小值
//$j 當前都需要和哪些元素比較，$i 后邊的。
for ($j = $i + 1; $j < $len; $j++) {
//比較，發(fā)現(xiàn)更小的,記錄下最小值的位置；并且在下次比較時，應該采用已知的最小值進行比較。
$min = ($arr[$min] <= $arr[$j]) ? $min : $j;
}
//已經(jīng)確定了當前的最小值的位置，保存到$min中。
//如果發(fā)現(xiàn) 最小值的位置與當前假設的位置$i不同，則位置互換即可
if ($min != $i) {
$tmp = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}
$arr = selectSort($arr);
print_r($arr);
三、插入排序
插入排序步驟大致如下：
- 先定義第一個元素為有序數(shù)列，第二個元素與第一個元素相比，如果第二元素小于第一個元素，則把第二個元素插到第一個元素的前面，否則，順序不變。如此，第一個元素和第二個元素就組成了一個新的有序數(shù)列
- 第三個元素與前面所述的有序數(shù)列比較，如果第三個元素小于第二個元素，則第三個元素再與第一個元素比較，如果第三個元素大于第一個元素，那么第三個元素就插入到第一二元素中間，此時有序數(shù)列變成了三個元素。
- 如此重復，進行第四個，第五個，第六個，，，元素到排序
//插入排序
$arr = [9,4,7,1,8,6,3,10,2];
function insertSort($arr)
{
$len=count($arr);
for($i=1; $i<$len; $i++) {
//獲得當前需要比較的元素值
$tmp = $arr[$i];
//內(nèi)層循環(huán)控制 比較 并 插入
for($j=$i-1; $j>=0; $j--) {
//$arr[$i];需要插入的元素
//$arr[$j];需要比較的元素
if($tmp < $arr[$j])
{
//發(fā)現(xiàn)插入的元素要小，交換位置
//將后邊的元素與前面的元素互換
$arr[$j+1] = $arr[$j];
//將前面的數(shù)設置為 當前需要交換的數(shù)
$arr[$j] = $tmp;
} else {
//如果碰到不需要移動的元素
//由于是已經(jīng)排序好是數(shù)組，則前面的就不需要再次比較了。
break;
}
}
}
//將這個元素 插入到已經(jīng)排序好的序列內(nèi)。
//返回
return $arr;
}
$arr = insertSort($arr);
print_r($arr);
四、快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來，且在大部分真實世界的數(shù)據(jù)，可以決定設計的選擇，減少所需時間的二次方項之可能性。
步驟：
從數(shù)列中挑出一個元素，稱為 “基準”（pivot），
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
//快速排序
$arr = [9,4,7,1,8,6,3,10,2];
function quickSort($arr)
{
//判斷參數(shù)是否是一個數(shù)組
if(!is_array($arr)) return false;
//遞歸出口:數(shù)組長度為1，直接返回數(shù)組
$length = count($arr);
if($length<=1) return $arr;
//數(shù)組元素有多個,則定義兩個空數(shù)組
$left = $right = array();
//使用for循環(huán)進行遍歷，把第一個元素當做比較的對象
for($i=1; $i<$length; $i++)
{
//判斷當前元素的大小
if($arr[$i] < $arr[0]){ //從小到大 < || 從大到小 >
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//遞歸調(diào)用
$left=quickSort($left);
$right=quickSort($right);
//將所有的結果合并
return array_merge($left,array($arr[0]),$right);
}
$arr = quickSort($arr);
print_r($arr);
