常見排序算法及PHP 實現，你學會了嗎？
10大排序算法對比
冒泡排序
算法描述
冒泡排序是一種交換排序，它的基本思想是：對待排序記錄從后往前（逆序）進行多遍掃描，當發現相鄰兩條記錄的次序與排序要求的規則不符時，就將這兩個記錄進行交換。這樣，值較小的記錄將逐漸從后面向前移動，就像氣泡在水中向上浮一樣。
實現步驟
假設需要排序的記錄有n 個，其值保存在數組A 中，使用冒泡排序法，需對數組A進行n-1 次掃描，完成排序操作。具體過程如下：
1. 將A[n-1] 與A[n] 進行比較,若A[n] < A[n-1] ，則交換兩元系的位置。
2. 修改數組下標，使需要比較的兩個元素為A[n-1] 和A[n-2] ，重復步驟(1)，對這兩個元素進行比較。重復這個過程，直到對A[1] 和A[0] 進行比較完為止。完成第1 遍掃描。
3. 經過第1 遍掃描后，最小的元素已經像氣泡一樣“浮”到最上面，即位于元素A[0] 中了。接下來重復前面的步驟，進行第2 遍掃描，只是掃描結束位置到A[2] 與A[1] 進行比較完為止（因為A[0]中已經是最小的數據，不用再進行比較）。
4. 通過n-1 遍掃描，前n-1 個數都已經排序完成，最后一個元素A[n] 肯定就是最大的數了。至此，完成排序操作。
圖片
代碼實現
/**
* 冒泡排序
* @param array $arr
*/
function bubbleSort(array &$arr) : void{
$length = count($arr);
// 外層循環，從數組首部開始，每完成一次循環，可確定$arr[$i] 位置的元素
for ($i = 0; $i < $length; $i++){
// 內層循環，$j 從后往前循環
for ($j = $length - 1; $j > $i; $j--) {
// 若前面的值大于后面的值，則互換位置
if ($arr[$j] < $arr[$j - 1]) {
// 互換數組兩個位置的值
[$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
}
}
}
}希爾排序
算法描述
希爾排序可以說是插入排序的一種變種。無論是插入排序還是冒泡排序，如果數組的最大值剛好是在第一位，要將它挪到正確的位置就需要 n - 1 次移動。
實現步驟
希爾排序的思想是采用插入排序的方法，先讓數組中任意間隔為 h 的元素有序，剛開始 h 的大小可以是 h = n / 2,接著讓 h = n / 4，讓 h 一直縮小，當 h = 1 時，也就是此時數組中任意間隔為1的元素有序，此時的數組就是有序的了。
代碼實現
function shell_sort(array $arr){
// 將$arr按升序排列
$len = count($arr);
$f = 3;// 定義因子
$h = 1;// 最小為1
while ($h < $len/$f){
$h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
}
while ($h >= 1){ // 將數組變為h有序
for ($i = $h; $i < $len; $i++){ // 將a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的關鍵
for ($j = $i; $j >= $h; $j -= $h){
if ($arr[$j] < $arr[$j-$h]){
$temp = $arr[$j];
$arr[$j] = $arr[$j-$h];
$arr[$j-$h] = $temp;
}
//print_r($arr);echo '<br/>'; // 打開這行注釋，可以看到每一步被替換的情形
}
}
$h = intval($h/$f);
}
return $arr;
}選擇排序
算法描述
選擇排序是通過n-i 次關鍵字間的比較，從n-i+1 個記錄中選出關鍵字最小的記錄，并和第i ( 1 <= i <= n ) 個記錄交換。
實現步驟
1. 維護數組中最小的前n 個元素的已排序序列。
2. 每次從剩余未排序的元素中選取最小的元素，將其放在已排序序列的后面，作為序列的第n+1 個記元素。
3. 以空序列作為排序工作的開始，直到未排序的序列里只剩一個元素時（它必然為最大），只需直接將其放在已排序的記錄之后，整個排序就完成了。
圖片
代碼實現
/**
* 選擇排序
* @param array $arr
*/
function selectionSort(array &$arr) : void{
$length = count($arr);
// 外層循環，從數組首部開始，每完成一次循環，可確定一個元素的位置
for ($i = 0; $i < $length - 1; $i++) {
// 選定的最小值的索引
$minIdx = $i;
// 從$i + 1 位開始循環，判斷當前選定的元素是否是當次循環的最小值
for ($j = $i + 1; $j < $length; $j++) {
// 若出現比選定的值還小的值，則替換最小值的索引
if ($arr[$minIdx] > $arr[$j]) {
$minIdx = $j;
}
}
// 互換數組兩個位置的值
[$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
}
}
/**
* 選擇排序- 方法2
* @param array $arr
*/
function selectionSort2(array &$arr) : void{
$length = count($arr);
// 外層循環，從數組首部開始，每完成一次循環，依次確定數組元素的位置
for ($i = 0; $i < $length; $i++) {
// 從$i + 1 位開始循環，依次判定$arr[$i] 與$arr[$j] 的大小
for ($j = $i + 1; $j < $length; $j++) {
// 若$arr[$i] 比$arr[$j] 大，則互換兩個元素的位置
if ($arr[$i] > $arr[$j]) {
// 互換數組兩個位置的值
[$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
}
}
}
}插入排序
算法描述
插入排序是通過構建有序序列，從未排序數據中選擇一個元素，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在從后向前掃描過程中，需要把已排序元素逐個向后移動，為最新元素提供插入空間。
實現步驟
1. 對于第1 個元素，因為沒有比較，將其作為已經有序的序列。
2. 從數組中獲取下一個元素，在已經排序的元素序列中從后向前掃描，并進行判斷。
3. 若排序序列的元素大于新元素，則將該元素向后移動一位。
4. 重復步驟(3)，直到在已排序的元素中找到小于或者等于新元素的元素，將新元素插入到該元素的后面。
5. 重復步驟(2) ~ (4)，直到完成排序。
圖片
代碼實現
/**
* 插入排序
* @param array $arr
*/
function insertionSort(array &$arr) : void{
$length = count($arr);
// 從數組首部開始排序，每完成一次循環，可確定一個元素的位置
for ($i = 0; $i < $length - 1; $i++) {
// 內層循環從$i + 1 個元素開始，一位一位向前比較
// 若前面的值比自己大，則替換，直到前面的值比自己小了，停止循環
for ($j = $i + 1; $j > 0; $j--) {
if ($arr[$j] >= $arr[$j - 1]) {
break;
}
[[$arr[$j], $arr[$j - 1]]] = [[$arr[$j - 1], $arr[$j]]];
}
}
}
/**
* 插入排序- 方法2
* @param array $arr
*/
function insertionSort2(array &$arr) : void{
$length = count($arr);
// 從數組首部開始排序，每完成一次循環，可確定一個元素的位置
for ($i = 0; $i < $length - 1; $i++) {
// 從第二個元素開始，選擇固定位置的值作為基準值
$currentVal = $arr[$i + 1];
// 初始鍵位于選定值的前一個位置
$preIdx = $i;
// 拿基準值一步一步向前比較，直到基準值比前面的值小，則兩值互換位置
while ($preIdx >= 0 && $currentVal < $arr[$preIdx]) {
$arr[$preIdx + 1] = $arr[$preIdx];
$arr[$preIdx] = $currentVal;
$preIdx--;
}
}
}快速排序
算法描述
快速排序是通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。
實現步驟
快速排序使用分治策略來把待排序數據序列分為兩個子序列，具體步驟如下：
1. 從數列中挑出一個元素，以該元素為“基準”。
2. 掃描一遍數列，將所有比“基準”小的元素排在基準前面，所有比“基準”大的元素排在基準后面。
3. 通過遞歸，將各子序列劃分為更小的序列，直到把小于基準值元素的子數列和大于基誰值元素的子數列排序。
圖片
代碼實現
/**
* 快速排序
* @param $arr
*/
function quickSort(& $arr) : void{
$length = count($arr);
// 若數組為空，則不需要運行
if ($length <= 1) {
return;
}
$middle = $arr[0]; // 選定一個中間值
$left = []; // 接收小于中間值
$right = [];// 接收大于中間值
// 循環比較
for ($i = 1; $i < $length; $i++) {
if ($middle < $arr[$i]) {
// 大于中間值
$right[] = $arr[$i];
} else {
// 小于或等于中間值
$left[] = $arr[$i];
}
}
// 遞歸排序劃分好的左右兩邊
quickSort($left);
quickSort($right);
$arr = array_merge($left, [$middle], $right);
}堆排序
算法描述
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
實現步驟
1、將初始待排序關鍵字序列(R1,R2….Rn)構建成最大堆，此堆為初始的無序區。
2、將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]。
3、由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。
圖片
代碼實現
//因為是數組,下標從0開始,所以,下標為n根結點的左子結點為2n+1,右子結點為2n+2;
//初始化值,建立初始堆
$arr=array(49,38,65,97,76,13,27,50);
$arrSize=count($arr);
//將第一次排序抽出來，因為最后一次排序不需要再交換值了。
buildHeap($arr,$arrSize);
for($i=$arrSize-1;$i>0;$i--){
swap($arr,$i,0);
$arrSize--;
buildHeap($arr,$arrSize);
}
//用數組建立最小堆
function buildHeap(&$arr,$arrSize){
//計算出最開始的下標$index,如圖,為數字"97"所在位置,比較每一個子樹的父結點和子結點,將最小值存入父結點中
//從$index處對一個樹進行循環比較,形成最小堆
for($index=intval($arrSize/2)-1; $index>=0; $index--){
//如果有左節點,將其下標存進最小值$min
if($index*2+1<$arrSize){
$min=$index*2+1;
//如果有右子結點,比較左右結點的大小,如果右子結點更小,將其結點的下標記錄進最小值$min
if($index*2+2<$arrSize){
if($arr[$index*2+2]<$arr[$min]){
$min=$index*2+2;
}
}
//將子結點中較小的和父結點比較,若子結點較小,與父結點交換位置,同時更新較小
if($arr[$min]<$arr[$index]){
swap($arr,$min,$index);
}
}
}
}
//此函數用來交換下數組$arr中下標為$one和$another的數據
function swap(&$arr,$one,$another){
$tmp=$arr[$one];
$arr[$one]=$arr[$another];
$arr[$another]=$tmp;
}歸并排序
算法描述
歸并是一種典型的序列操作，其工作是把兩個或更多有序序列合并為一個有序序列。基于歸并的思想也可以實現排序，稱為歸并排序。
實現步驟
1. 初始時，把待排序序列中的n 個元素看成n 個有序子序列（因為只有1 個元素的序列總是排好序的），每個子序列的長度均為1。
2. 把序列組里的有序子序列兩兩歸并，每完成一論歸并，序列組里的序列個數減半，每個子序列的長度加倍。
3. 對加長的有序子序列重復上面的操作，最終得到一個長度為n 的有序序列。這種歸并方法也稱為簡單的二路歸并排序，其中每次操作都是把兩個有序序列合并為一個有序序列。也可考慮三路歸并或更多路的歸并。
圖片
代碼實現
/**
* 歸并排序
* @param array $arr
* @return array
*/
function mergeSort(array $arr){
// 計算數組長度，若長度不大于1，則不需要排序
$length = count($arr);
if ($length <= 1) {
return $arr;
}
// 獲取數組中間位置的索引
$midIdx = floor($length / 2);
// 把數組從中間拆分成左右兩部分
$left = mergeSort(array_slice($arr, 0, $midIdx));
$right = mergeSort(array_slice($arr, $midIdx));
// 合并兩部分，同時進行排序
return merge($left, $right);
}
/**
* 合并數組，同時進行排序
* @param array $left
* @param array $right
* @return array
*/
function merge(array $left, array $right){
// 分別計算左右兩數組的長度
$lLength = count($left);
$rLength = count($right);
// 左右兩數組的索引
$l = $r = 0;
$lists = [];
// 只有左右兩數組都未遍歷完成時，才有必要繼續遍歷
// 當其中一個數組的元素遍歷完成，說明另一個數組中未遍歷過的值比遍歷過的值都大
while ($l < $lLength && $r < $rLength) {
// 比較$left[$l] 和$right[$r]，取其中較小的值加入到$lists 數組中
if ($left[$l] < $right[$r]) {
$lists[] = $left[$l];
$l++;
} else {
$lists[] = $right[$r];
$r++;
}
}
// 合并$lists 和$left、$right 中剩余的元素
return array_merge($lists, array_slice($left, $l), array_slice($right,$r));
}
/**
* 合并數組，同時進行排序- 方法2
* @param array $left
* @param array $right
* @return array
*/
function merge2(array $left, array $right){
// 分別計算左右兩數組的長度
$lLength = count($left);
$rLength = count($right);
// 左右兩數組的索引
$l = $r = 0;
$lists = [];
// 只有左右兩數組都未遍歷完成時，才有必要繼續遍歷
// 當其中一個數組的元素遍歷完成，說明另一個數組中未遍歷過的值比遍歷過的值都大
while ($l < $lLength && $r < $rLength) {
// 比較$left[$l] 和$right[$r]，取其中較小的值加入到$lists 數組中
if ($left[$l] < $right[$r]) {
$lists[] = $left[$l];
// PHP 中unset 掉數組中的元素后，其他元素的鍵名不變
unset($left[$l]);
$l++;
} else {
$lists[] = $right[$r];
unset($right[$r]);
$r++;
}
}
// 合并$lists 和$left、$right 中剩余的元素
return array_merge($lists, $left, $right);
}
/**
* 合并數組，同時進行排序- 方法3
* @param array $left
* @param array $right
* @return array
*/
function merge3(array $left, array $right){
// 分別計算左右兩數組的長度
$lLength = count($left);
$rLength = count($right);
$lists = [];
// 只有左右兩數組都未遍歷完成時，才有必要繼續遍歷
// 當其中一個數組的元素遍歷完成，說明另一個數組中未遍歷過的值比遍歷過的值都大
while ($lLength > 0 && $rLength > 0) {
// 比較$left[$l] 和$right[$r]，取其中較小的值加入到$lists 數組中
if ($left[0] < $right[0]) {
$lists[] = $left[0];
// PHP 中unset 掉數組中的元素后，其他元素的鍵名不變
unset($left[0]);
// 重建數組索引，始終讓比較的值在第一位
$left = array_values($left);
$lLength--;
} else {
$lists[] = $right[0];
unset($right[0]);
$right = array_values($right);
$rLength--;
}
}
// 合并$lists 和$left、$right 中剩余的元素
return array_merge($lists, $left, $right);
}
