基础算法:冒泡排序、选择排序、插入排序、快速排序的PHP实现过程
算法作为程序的核心，无论使用哪种语言都是不能忽略的。在PHP中虽然接触的不多，但是基本的四种算法还是必须要掌握的。(以下示例默认排序方式为从小到大排序)
冒泡排序
重复地走访要排序的数组，依次比较两个元素。若它们的顺序错误则交换它们位置，走访数组的工作是重复地进行直到某次走访不在发生交换位置操作，则排序完成。
思路：
- 遍历数组，比较相邻元素大小，前者大于后者则交换它们的位置
- 每遍历一轮则最后一个元素为最大元素
- 根据步骤二规则，下次遍历的元素截止到上一轮最大元素前即可
- 持续遍历数组，直到没有元素需要比较
/**
* 冒泡排序
* @param $arr
* @return array
*/
function bubbleSort($arr) {
// 首先得到数组长度，通过数组长度确定遍历几轮及每轮多少次交换操作
$len = count($arr);
// 确定遍历轮数
for ($i = 1; $i < $len; $i++) {
// 确定每轮的交换次数
for ($k = 0; $k < $len - $i; $k++) {
// 每次交换前比较元素大小，若前者大则交换位置(后者大则无需交换)
if ($arr[$k] > $arr[$k + 1]) {
// 通过一个临时变量来达到交换目的
$tmp = $arr[$k + 1];
$arr[$k + 1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}选择排序
在未排序的数组中找到最小元素，将其放在排序数组的末尾。然后在剩余未排序的数组中继续寻找最小元素，并将其放在排序数组的末尾。重复此操作，直到所有元素都排序完成。
/**
* 选择排序
* @param $arr
* @return array
*/
function selectSort($arr) {
// 首先得到数组长度，通过数组长度确定遍历查找次数
$len = count($arr);
// 遍历所要排序数组(根据该算法特性，遍历到最后一个元素时已不需要继续操作)
for ($i = 0; $i < $len - 1; $i++) {
// 假定第$i次元素为最小元素的下标
$minKey = $i;
// 遍历最小元素后面的所有元素
for ($j = $i + 1; $j < $len; $j++) {
// 若该值小于假定的最小值，则将该值作为最小值
$minKey = ($arr[$minKey] > $arr[$j]) ? $j : $minKey;
}
// 该轮最小值的下标此时已确定，并保存在$minKey中
// 若最小值的位置不是假定位置，则将位置交换
if ($minKey != $i) {
$tmp = $arr[$minKey];
$arr[$minKey] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
思路：
- 数组第一个元素划分为有序数组
- 取出下一个元素，将该元素与有序数组的元素从后向前依次比较
- 若该元素小于有序数组的对比元素，则交换他们的位置
- 重复步骤三，直到该元素大于或等于对比元素，结束有序数组遍历
- 重复步骤二，直到取完剩余数组元素
/**
* 插入排序
* @param $arr
* @return array
*/
function insertSort($arr) {
// 首先得到数组长度
$len = count($arr);
// 遍历未排序的数组元素(默认第一个元素作为有数组元素)
for ($i = 1; $i < $len; $i++) {
// 当前需要比较的元素
$tmp = $arr[$i];
// 遍历有序数组(从后向前遍历，即先遍历最大值)
for ($j = $i - 1; $j >= 0; $j--) {
// 若比较元素小于当前排序数组元素
if ($tmp < $arr[$j]) {
// 将比较元素与前面的元素互换
$arr[$j + 1] = $arr[$j];
$arr[$j] = $tmp;
} else {
// 比较元素位置不需要移动，无需再和剩余有序数组比较
break;
}
}
}
return $arr;
}快速排序
在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。
思路：
- 从数列中挑出一个元素，称为”基准”
- 重复排序数组，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
/**
* 快速排序
* @param $arr
* @return array
*/
function quickSort($arr) {
// 首先得到数组长度
$len = count($arr);
// 判断数组长度
if ($len <= 1) {
return $arr;
}
// 定义两个空数组
$left = [];
$right = [];
// 第一个元素作为比较的对象
$middle = $arr[0];
// 遍历去除作为比较的第一个元素的数组
for ($i = 1; $i < $len; $i++) {
// 判断当前元素与比较对象的大小
if ($arr[$i] < $middle) {
// 当前值小则放入左边数组中
$left[] = $arr[$i];
} else {
// 当前值大则放入右侧数组中
$right[] = $arr[$i];
}
}
//递归调用
$left = quickSort($left);
$right = quickSort($right);
//将所有的结果合并
return array_merge($left, [$middle], $right);
}
