一 ： 歸並排序
將兩個的有序數列合並成一個有序數列，我們稱之為"歸並"。
歸並排序(Merge Sort)就是利用歸並思想對數列進行排序。根據具體的實現，歸並排序包括"從上往下"和"從下往上"2種方式。
1. 從下往上的歸並排序：將待排序的數列分成若干個長度為1的子數列，然後將這些數列兩兩合並；得到若干個長度為2的有序數列，再將這些數列兩兩合並；得到若干個長度為4的有序數列，再將它們兩兩合並；直接合並成一個數列為止。這樣就得到了我們想要的排序結果
2. 從上往下的歸並排序：它與"從下往上"在排序上是反方向的。它基本包括3步：
① 分解 -- 將當前區間一分為二，即求分裂點 mid = (low + high)/2;
② 求解 -- 遞歸地對兩個子區間a[low...mid] 和 a[mid+1...high]進行歸並排序。遞歸的終結條件是子區間長度為1。
③ 合並 -- 將已排序的兩個子區間a[low...mid]和 a[mid+1...high]歸並為一個有序的區間a[low...high]。
/**
* 歸並排序實現過程
* @param Array $arr 待排序的區間數組
* @param Int $start 第一個區間數組的起始位置
* @param Int $mid 第一個區間數組的結束位置，第二個區間數組的起始位置
* @param Int $end 第二個區間數組的結束位置
* @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]) //判斷兩個區間數組各自數據的大小，並歸類
$tmp[$k++] = $arr[$i++];
else
$tmp[$k++] = $arr[$j++];
}
while($i <= $mid) //防止第一個區間有一個數據沒有歸類
$tmp[$k++] = $arr[$i++];
while($j <= $end) //防止第二個區間有一個數據沒有歸類
$tmp[$k++] = $arr[$j++];
// 將排序後的元素，全部都整合到數組arr中。
for ($i = 0; $i < $k; ++$i)
$arr[$start + $i] = $tmp[$i];
}
/**
* 歸並排序(從上往下)
* @param Array $arr 待排序的數組
* @param Int $start 數組起始位置
* @param Int end 數組結束位置
* @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); //分區間
merge_sort($arr,$start,$mid);
merge_sort($arr,$mid+1,$end);
merge($arr,$start,$mid,$end);
}
//從下往上與此剛好相反
二 ： 快速排序
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。快速排序主體算法時間運算量約 O(log2n) ，劃分子區函數運算量約 O(n) ，所以總的時間復雜度為 O(nlog2n) ，它顯然優於冒泡排序 O(n2). 可是算法的優勢並不是絕對的。試分析，當原文件關鍵字有序時，快速排序時間復雜度是 O(n2), 這種情況下快速排序不快。而這種情況的冒泡排序是 O(n), 反而很快。在原文件記錄關鍵字無序時的多種排序方法中，快速排序被認為是最好的一種排序方法。
/**
* 快速排序
* @param Array $arr 待排序的數組
* @return Array 排序後的數組
*/
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);
}
三 ：冒泡排序
兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。該算法的時間復雜度為O(n2)。但是，當原始關鍵字序列已有序時，只進行一趟比較就結束，此時時間復雜度為O(n)。
/**
* 冒泡排序
* @param Array $arr 待排序的數組
* @return Array 排序後的數組
*/
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;
}
四 ：插入排序
每次將一個待排序的數據元素插入到前面已經排好序的數列中，使數列依然有序，知道待排序數據元素全部插入完為止。如果目標是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1)次。平均來說插入排序算法的時間復雜度為O(n^2)。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇
/**
* 插入排序
* @param Array $arr 待排序的數組
* @return Array 排序後的數組
*/
function insert_sort(Array $arr)
{
$len = count($arr);
for($i = 1; $i < $len; ++$i)
{
$tmp = $arr[$i];
$j = $i - 1;
//把數據插入到合適的位置(交換位置)
while($j >= 0 && $arr[$j] > $tmp)
{
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
--$j;
}
}
return $arr;
}
五 ：選擇排序
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。時間復雜度為o(n2),不穩定排序，適合規模比較小的
/**
* 選擇排序
* @param Array $arr 待排序的數組
* @return Array 排序後的數組
*/
function select_sort(Array $arr)
{
$len = count($arr);
for($i = 0; $i < $len; ++$i)
{
$k = $i; //標記當前索引
for($j = $i + 1; $j < $len; ++$j)
{
if($arr[$j] < $arr[$k])
$k = $j; //獲取當前最小值索引
if($k != $i) //如果最小值得索引發生變化
{
$tmp = $arr[$i];
$arr[$i] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}
六 ：二分查找
/**
* 二分查找
* @param Array $arr 待查找的數組
* @param Int $key 要查找的關鍵字
* @return Int
*/
function bin_search(Array $arr,$key)
{
$high = count($arr);
if($high <= 0)
return 0;
$low = 0;
while($low <= $high)
{
//當前查找區間arr[low..high]非空
$mid=intval(($low + $high) / 2);
if($arr[$mid] == $key)
return $mid; //查找成功返回
if($arr[$mid] > $key)
$high = $mid - 1; //繼續在arr[low..mid-1]中查找
else
$low = $mid + 1; //繼續在arr[mid+1..high]中查找
}
return 0; //當low>high時表示查找區間為空，查找失敗
}
$arr = array(1,2,4,6,10,40,50,80,100,110);
echo bin_search($arr,80);
