一 ： 歸并排序
將兩個的有序數(shù)列合并成一個有序數(shù)列，我們稱之為"歸并"。
歸并排序(Merge Sort)就是利用歸并思想對數(shù)列進(jìn)行排序。根據(jù)具體的實現(xiàn)，歸并排序包括"從上往下"和"從下往上"2種方式鼻疮。
從下往上的歸并排序：將待排序的數(shù)列分成若干個長度為1的子數(shù)列，然后將這些數(shù)列兩兩合并琳轿；得到若干個長度為2的有序數(shù)列判沟，再將這些數(shù)列兩兩合并；得到若干個長度為4的有序數(shù)列崭篡，再將它們兩兩合并挪哄；直接合并成一個數(shù)列為止。這樣就得到了我們想要的排序結(jié)果
從上往下的歸并排序：它與"從下往上"在排序上是反方向的琉闪。它基本包括3步：
① 分解 -- 將當(dāng)前區(qū)間一分為二迹炼，即求分裂點 mid = (low + high)/2;
② 求解 -- 遞歸地對兩個子區(qū)間a[low...mid] 和 a[mid+1...high]進(jìn)行歸并排序。遞歸的終結(jié)條件是子區(qū)間長度為1颠毙。
③ 合并 -- 將已排序的兩個子區(qū)間a[low...mid]和 a[mid+1...high]歸并為一個有序的區(qū)間a[low...high]斯入。
/**
* 歸并排序?qū)崿F(xiàn)過程
* @param Array $arr 待排序的區(qū)間數(shù)組
* @param Int $start 第一個區(qū)間數(shù)組的起始位置
* @param Int $mid 第一個區(qū)間數(shù)組的結(jié)束位置，第二個區(qū)間數(shù)組的起始位置
* @param Int $end 第二個區(qū)間數(shù)組的結(jié)束位置
* @return void */
function merge(Array &$arr,$start,$mid,$end)
{
$i = $start;
$j = $mid + 1;
$k = 0;
while($i <= $mid && $j <= $end)
{
if ($arr[$i] <= $arr[$j]) //判斷兩個區(qū)間數(shù)組各自數(shù)據(jù)的大小蛀蜜，并歸類
$tmp[$k++] = $arr[$i++];
else
$tmp[$k++] = $arr[$j++];
}
while($i <= $mid) //防止第一個區(qū)間有一個數(shù)據(jù)沒有歸類
{
$tmp[$k++] = $arr[$i++];
}
while($j <= $end) //防止第二個區(qū)間有一個數(shù)據(jù)沒有歸類
{
$tmp[$k++] = $arr[$j++]; // 將排序后的元素刻两，全部都整合到數(shù)組arr中。
}
for ($i = 0; $i < $k; ++$i)
$arr[$start + $i] = $tmp[$i];
} /**
* 歸并排序(從上往下)
* @param Array $arr 待排序的數(shù)組
* @param Int $start 數(shù)組起始位置
* @param Int end 數(shù)組結(jié)束位置
* @return void */
function merge_sort(Array &$arr,$start=0,$end=0)
{
$len = count($arr);
if($len <= 1 || $start >= $end)
return $arr;
$mid = intval(($start + $end) / 2); //分區(qū)間
merge_sort($arr,$start,$mid);
merge_sort($arr,$mid+1,$end);
merge($arr,$start,$mid,$end);
}
//從下往上與此剛好相反
二 ： 快速排序
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分滴某，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小磅摹，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行霎奢，以此達(dá)到整個數(shù)據(jù)變成有序序列户誓。快速排序主體算法時間運算量約 O(log2n) 幕侠，劃分子區(qū)函數(shù)運算量約 O(n) 厅克，所以總的時間復(fù)雜度為 O(nlog2n) ，它顯然優(yōu)于冒泡排序 O(n2). 可是算法的優(yōu)勢并不是絕對的橙依。試分析，當(dāng)原文件關(guān)鍵字有序時硕旗，快速排序時間復(fù)雜度是 O(n2), 這種情況下快速排序不快窗骑。而這種情況的冒泡排序是 O(n), 反而很快。在原文件記錄關(guān)鍵字無序時的多種排序方法中漆枚，快速排序被認(rèn)為是最好的一種排序方法创译。
/**
* 快速排序
* @param Array $arr 待排序的數(shù)組
* @return Array 排序后的數(shù)組 */
function quick_sort(Array $arr)
{
$len = count($arr);
if($len <= 1)
return $arr;
$tmp = $arr[0];
$left_arr = [];
$right_arr = [];
for($i = 1; $i < $len; ++$i)
{
if($arr[$i] <= $tmp)
$left_arr[] = $arr[$i];
else
$right_arr[] = $arr[$i];
} //遞歸分類
$left_arr = quick_sort($left_arr);
$right_arr = quick_sort($right_arr);
return array_merge($left_arr,array($tmp),$right_arr);
}
三 ：冒泡排序
兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進(jìn)行交換墙基，直到?jīng)]有反序的數(shù)據(jù)元素為止软族。該算法的時間復(fù)雜度為O(n2)刷喜。但是，當(dāng)原始關(guān)鍵字序列已有序時立砸，只進(jìn)行一趟比較就結(jié)束掖疮，此時時間復(fù)雜度為O(n)。
/**
* 冒泡排序
* @param Array $arr 待排序的數(shù)組
* @return Array 排序后的數(shù)組 */
function bubble_sort(Array $arr)
{
$len = count($arr);
for($i = 0; $i < $len; ++$i)
{
for($j = $len - 1; $j > $i; --$j)
{
if($arr[$j] < $arr[$j-1])
{
$tmp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $tmp;
}
}
}
return $arr;
}
四 ：插入排序
每次將一個待排序的數(shù)據(jù)元素插入到前面已經(jīng)排好序的數(shù)列中颗祝，使數(shù)列依然有序浊闪，知道待排序數(shù)據(jù)元素全部插入完為止。如果目標(biāo)是把n個元素的序列升序排列螺戳，那么采用插入排序存在最好情況和最壞情況搁宾。最好情況就是，序列已經(jīng)是升序排列了倔幼，在這種情況下盖腿，需要進(jìn)行的比較操作需(n-1)次即可。最壞情況就是损同，序列是降序排列翩腐，那么此時需要進(jìn)行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數(shù)加上 (n-1)次揖庄。平均來說插入排序算法的時間復(fù)雜度為O(n^2)栗菜。因而，插入排序不適合對于數(shù)據(jù)量比較大的排序應(yīng)用蹄梢。但是疙筹，如果需要排序的數(shù)據(jù)量很小，例如禁炒，量級小于千而咆，那么插入排序還是一個不錯的選擇
/**
* 插入排序
* @param Array $arr 待排序的數(shù)組
* @return Array 排序后的數(shù)組 */
function insert_sort(Array $arr)
{
$len = count($arr);
for($i = 1; $i < $len; ++$i)
{
$tmp = $arr[$i]; $j = $i - 1; //把數(shù)據(jù)插入到合適的位置(交換位置)
while($j >= 0 && $arr[$j] > $tmp)
{
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
--$j;
}
}
return $arr;
}
五 ：選擇排序
每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素幕袱，順序放在已排好序的數(shù)列的最后暴备，直到全部待排序的數(shù)據(jù)元素排完。時間復(fù)雜度為o(n2),不穩(wěn)定排序们豌，適合規(guī)模比較小的
/**
* 選擇排序
* @param Array $arr 待排序的數(shù)組
* @return Array 排序后的數(shù)組 */
function select_sort(Array $arr)
{
$len = count($arr);
for($i = 0; $i < $len; ++$i)
{
$k = $i; //標(biāo)記當(dāng)前索引
for($j = $i + 1; $j < $len; ++$j)
{
if($arr[$j] < $arr[$k])
$k = $j; //獲取當(dāng)前最小值索引
if($k != $i) //如果最小值得索引發(fā)生變化
{
$tmp = $arr[$i];
$arr[$i] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}
六 ：二分查找
/**
* 二分查找
* @param Array $arr 待查找的數(shù)組
* @param Int $key 要查找的關(guān)鍵字
* @return Int */
function bin_search(Array $arr,$key)
{
$high = count($arr);
if($high <= 0)
return 0;
$low = 0;
while($low <= $high)
{
//當(dāng)前查找區(qū)間arr[low..high]非空
$mid=intval(($low + $high) / 2);
if($arr[$mid] == $key)
return $mid; //查找成功返回
if($arr[$mid] > $key)
$high = $mid - 1; //繼續(xù)在arr[low..mid-1]中查找
else
$low = $mid + 1; //繼續(xù)在arr[mid+1..high]中查找
}
return 0; //當(dāng)low>high時表示查找區(qū)間為空涯捻，查找失敗
}
$arr = array(1,2,4,6,10,40,50,80,100,110);
echo bin_search($arr,80);
