PHP 实现常用的四种算法排序

冒泡排序

• 介绍

从第一个数据开始，依次比较相邻元素的大小。如果前者大于后者，则进行交换操作，把大的元素往后交换。通过多轮迭代，直到没有交换操作为止。

• 图解

• 创建 bubble.php 内容如下：

<?php
function bubble($arr){
	$c = count($arr);
	if ($c<=1) {
		return $arr;
	}
	for ($i=0; $i < $c; $i++) { 
		for ($j=$i+1; $j < $c; $j++) { 
			if ($arr[$i]>$arr[$j]) {
				$temp = $arr[$i];
				$arr[$i] = $arr[$j];
				$arr[$j] = $temp;
			}
		}
	}
	return $arr;
}
var_dump(bubble([29,10,14,37,15]));

• 执行

$ php bubble.php
array(5) {
  [0] =>
  int(10)
  [1] =>
  int(14)
  [2] =>
  int(15)
  [3] =>
  int(29)
  [4] =>
  int(37)
}

插入排序

• 介绍

选取未排序的元素，插入到已排序区间的合适位置，直到未排序区间为空。

• 图解

• 创建 insert.php 内容如下：

<?php
function insert($arr){
	$c = count($arr);
	if ($c<=1) {
		return $arr;
	}
	for ($i=1; $i < $c; $i++) { 
		$temp = $arr[$i];
		for ($j=$i-1; $j >= 0; $j--) { 
			if ($arr[$j]>$temp) {
				$arr[$j+1] = $arr[$j];
			}else{
				break;
			}
		}
		$arr[$j+1] = $temp;
	}
	return $arr;
}
var_dump(insert([29,10,14,37,15]));

• 执行

$ php insert.php
array(5) {
  [0] =>
  int(10)
  [1] =>
  int(14)
  [2] =>
  int(15)
  [3] =>
  int(29)
  [4] =>
  int(37)
}

归并排序

• 介绍

归并排序的原理其实就是分治法（二分法）。它采用了二分的迭代方式，首先将数组不断地二分，直到最后每个部分只包含 1 个数据。然后再对每个部分分别进行排序，最后将排序好的相邻的两部分合并在一起，这样整个数组就有序了。

• 图解

• 创建 merge.php 内容如下：

<?php 
function customMergeSort(&$arr, $start, $end){
	if ($start < $end) {
		$middle = floor(($start+$end)/2);
		customMergeSort($arr, $start, $middle);
		customMergeSort($arr, $middle+1, $end);
		customDoubleMerge($arr, $start, $middle, $end);
	}
}

function customDoubleMerge(&$arr, $start, $middle, $end){
	$leftLen = $middle-$start+1;
	$rightLen = $end-$middle;
	$arrLeft = $arrRight = [];
	for ($i=0; $i < $leftLen; $i++) { 
		$arrLeft[$i] = $arr[$start+$i];
	}
	for ($j=0; $j < $rightLen; $j++) { 
		$arrRight[$j] = $arr[$middle+$j+1];
	}
	$i = $j = 0;
	$k = $start;
	for (; $i < $leftLen && $j < $rightLen && $k < $end; $k++) { 
		if ($arrLeft[$i]<=$arrRight[$j]) {
			$arr[$k] = $arrLeft[$i];
			$i++;
		} else {
			$arr[$k] = $arrRight[$j];
			$j++;
		}

	}
	for (; $i < $leftLen && $k <= $end; $k++) { 
		$arr[$k] = $arrLeft[$i];
		$i++;
	}
	for (; $j < $rightLen && $k <= $end; $k++) { 
		$arr[$k] = $arrRight[$j];
		$j++;
	}
}

$arr = [29,10,14,37,15];
$c = count($arr);
customMergeSort($arr, 0, $c-1);
var_dump($arr);

• 执行

$ php merge.php
array(5) {
  [0] =>
  int(10)
  [1] =>
  int(14)
  [2] =>
  int(15)
  [3] =>
  int(29)
  [4] =>
  int(37)
}

快速排序

• 介绍

快速排序法的原理也是分治法。它的每轮迭代，会选取数组中任意一个数据作为分区点，将小于它的元素放在它的左侧，大于它的放在它的右侧。再利用分治思想，继续分别对左右两侧进行同样的操作，直至每个区间缩小为 1，则完成排序。

• 图解

• 创建 quick.php 内容如下：

<?php
function quick($arr){
	$c = count($arr);
	if ($c<2) {
		return $arr;
	}
	$left = $right = [];
	$middle = $arr[0];
	for ($i=1; $i < $c; $i++) { 
		if ($arr[$i]<$middle) {
			array_push($left,$arr[$i]);
			
		}else{
			array_push($right,$arr[$i]);
		}
	}
	return array_merge(quick($left),[$middle],quick($right));
}
var_dump(quick([29,10,14,37,15]));

• 执行

$ php quick.php
array(5) {
  [0] =>
  int(10)
  [1] =>
  int(14)
  [2] =>
  int(15)
  [3] =>
  int(29)
  [4] =>
  int(37)
}

选择排序

• 介绍

每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

• 图解

• 创建 select.php 内容如下：

<?php
function select($arr){
	$c = count($arr);
	if ($c < 2) {
		return $c;
	}
	for ($i=0; $i < $c; $i++) { 
		$minKey = $i;
		for ($j=$i+1; $j < $c; $j++) { 
			if ($arr[$j]<=$arr[$minKey]) {
				$minKey = $j;
			}
		}
		if ($minKey!=$i) {
			$temp = $arr[$i];
			$arr[$i] = $arr[$minKey];
			$arr[$minKey] = $temp;
		}
	}
	return $arr;
}
var_dump(select([29,10,14,37,15]));

• 执行

$ php select.php
array(5) {
  [0] =>
  int(10)
  [1] =>
  int(14)
  [2] =>
  int(15)
  [3] =>
  int(29)
  [4] =>
  int(37)
}

关联

[[Go 实现常用的五种算法排序]]