在PHP中，排序算法用于将一组数据按照特定的顺序进行排列。常见的排序算法包括快速排序、插入排序、希尔排序、归并排序、堆排序、冒泡排序、计数排序、基数排序、桶排序、选择排序等。下面将介绍其中一些常用的PHP排序算法。
冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
以下是一个使用PHP实现冒泡排序的示例代码：
function maopao($arr){
$count=count($arr);
for($i=0;$i<$count;$i++){
for($j=0;$j<$count-$i-1;$j++){
if($arr[$j]<$arr[$j+1]){
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}
}
}
var_dump($arr);
}选择排序（Selection Sort）
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。
以下是一个使用PHP实现选择排序的示例代码：
function selectionSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
// 交换元素
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
return $arr;
}插入排序（Insertion Sort）
插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
以下是一个使用PHP实现插入排序的示例代码：
function insertionSort($arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}快速排序
从1开始每个数和arr[0]比较,分别放进左右数组，递归，合并
function quicksort($arr) {
if(count($arr) <=1) {
return $arr;
}
$larr = [];
$rarr = [];
for ($i=1;$i<count($arr);$i++) {
if($arr[$i] <= $arr[0]) {
$larr[] = $arr[$i];
} else {
$rarr[] = $arr[$i];
}
}
$left = quicksort($larr);
$right = quicksort($rarr);
return array_merge($left,array($arr[0]),$right);
}希尔排序
带基数的插入排序
function shellsort($arr) {
//初始化增量
$increment = count($arr);
while($increment > 1) {
$increment = intval($increment/3) + 1;
for ($i=$increment;$i<count($arr);$i++) {
//待插入值
$temp = $arr[$i];
//待比较位置
$j = $i - $increment;
//降序排列
while($j>=0&&$temp>$arr[$j]) {
$arr[$j+$increment] = $arr[$j];
$arr[$j] = $temp;
$j = $j-$increment;
}
$arr[$j+$increment] = $temp;
}
}
return $arr;
}归并排序
把数组切割,直到不可分割,排序单个小数组，然后合并,递归执行
function merge_sort(&$arr) {
$count = count($arr);
if($count <= 1) {
return $arr;
}
$mid = intval($count/2);
$left = array_slice($arr, 0,$mid);
$right = array_slice($arr, $mid);
merge_sort($left);
merge_sort($right);
$merge=[];
while(count($left)&&count($right)) {
$merge[] = $left[0]<$right[0] ? array_shift($left):array_shift($right);
}
$arr = array_merge($merge,$left,$right);
// var_dump($arr);
}堆排序
以最后一个父节点为起始节点,比较子节点，把最小值或最大值移动到父节点，遍历所有父节点后
function heep_sort($arr) {
//获取数组的长度
$arrsize = count($arr);
while($arrsize > 0) {
//遍历每个节点，和子节点比较得到最小值
for ($i = intval($arrsize/2)-1;$i>=0;$i--) {
//起初认定当前节点最小
$min = $i;
//如果存在左节点
if($i*2+1 < $arrsize) {
//比较和左节点的大小,如果左节点的值更小,那么进行交换
if($arr[$i] > $arr[$i*2+1]) {
$temp = $arr[$i];
$arr[$i] = $arr[$i*2+1];
$arr[$i*2+1] = $temp;
}
}
//如果存在又节点
if($i*2+2 < $arrsize) {
//比较和右节点的大小，如果右节点的值更小，那么进行交换
if($arr[$i] > $arr[$i*2+2]) {
$temp = $arr[$i];
$arr[$i] = $arr[$i*2+2];
$arr[$i*2+2] = $temp;
}
}
//执行完一次遍历,跳到下一个非叶子节点
}
//成功找到第一个最小值,使数组长度减一
//首尾交换，保存最小值
$temp = $arr[0];
$arr[0] = $arr[$arrsize-1];
$arr[$arrsize-1] = $temp;
$arrsize--;
}
return $arr;
}计数排序
时间复杂度O(n+k),n为排序的数的个数,k为要排序的数的最大值,消耗空间来达到快捷,空间换时间，
计算数组的最大和最小值，创建一个键从min到max的数组，计数排序数组的每个值的个数，然后向一个新数组填充入栈
步骤：
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1
function countsort($arr) {
$count = count($arr);
$carr = [];
$min = $arr[0];
$max = $arr[0];
//找最大值和最小值
for ($i=1;$i<$count;$i++) {
if($arr[$i]<$min) {
$min = $arr[$i];
}
if($arr[$i]>$max) {
$max = $arr[$i];
}
}
for ($i=$min;$i<=$max;$i++) {
$carr[$i] = 0;
}
for ($i=1;$i<$count;$i++) {
$carr[$arr[$i]]++;
}
$newarr = [];
for ($i=$max;$i>=$min;$i--) {
while($carr[$i]>0) {
$newarr[]=$i;
$carr[$i]--;
}
}
var_dump($newarr);
}基数排序
//默认降序
function radixSort($arr, $desc=true) {
if (count($arr) <= 1) {
return $arr;
}
$max = $arr[0];
for ($i=1;$i<count($arr);$i++) {
if ($arr[$i] > $max) {
$max = $arr[$i];
}
}
$n = 0;
//记录最大数的位数
while($max > 1) {
$max = $max/10;
$n++;
}
for ($j=1;$j<=$n;$j++) {
$tmp_arr = [];
for ($k=0;$k<count($arr);$k++) {
$r = pow(10,$j-1);
$num = $arr[$k] > $r ? intval($arr[$k]/$r)%10 : 0;
$tmp_arr[$num][] = $arr[$k];
}
$arr=[];
if ($desc) {
for ($m=9;$m>=0;$m--) {
if (!empty($tmp_arr[$m])) {
for ($p=0;$p<count($tmp_arr[$m]);$p++) {
$arr[] = $tmp_arr[$m][$p];
}
}
}
} else {
for ($m=0;$m<=9;$m++) {
if (!empty($tmp_arr[$m])) {
for ($p=0;$p<count($tmp_arr[$m]);$p++) {
$arr[] = $tmp_arr[$m][$p];
}
}
}
}
}
return $arr;
}桶排序
function bucketSort($arr, $bucketSize = 5) {
if (count($arr) === 0) {
return $arr;
}
$minValue = $arr[0];
$maxValue = $arr[0];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $minValue) {
$minValue = $arr[$i];
} else if ($arr[$i] > $maxValue) {
$maxValue = $arr[$i];
}
}
$bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
$buckets = array();
for ($i = 0; $i < $bucketCount; $i++) {
$buckets[$i] = [];
}
for ($i = 0; $i < count($arr); $i++) {
$buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
}
$arr = array();
for ($i = 0; $i < count($buckets); $i++) {
$bucketTmp = $buckets[$i];
sort($bucketTmp);
for ($j = 0; $j < count($bucketTmp); $j++) {
$arr[] = $bucketTmp[$j];
}
}
return $arr;
}