Common sorting algorithms are: bubble sort, quick sort, selection sort, insertion sort, here are the ones I prepared for my recent interview Study notes, and I hope it can help you.
Requirement: Sort an array with multiple numbers from small to large.
Sort algorithm
【 1].Bubble sorting
Idea analysis:
Imagine that there are N number of hydrogen balloons that have not been arranged in a large pool. The larger ones pop out first, and then the The smaller ones rise upward. That is, two adjacent numbers are compared each time, with the smaller one in front and the larger one in the back, otherwise the positions are swapped.
Code implementation
/**
* 交换方法
* @param array $arr 目标数组
* @param $a 索引a
* @param $b 索引b
* @param bool $flag 交换标志
* @return bool
*/
function swap(array &$arr,$a,$b,$flag = false){
// 遍历i后面的元素，只要该元素小于当前元素，就把较小的往前冒泡
if($arr[$a] > $arr[$b]){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; $flag = true;
} return $flag;
} /**
* 第一种写法
* @param $arr 所要排序的数组
* @return mixed 返回的数组
*/
function bubbleSort($arr) {
$len = count($arr); if ($len <= 1) {return $arr;} //该层循环控制 需要冒泡的轮数
for ($i = 0; $i < $len-1; $i++) { //该层循环用来控制每轮 冒出一个数 需要比较的次数
for ($j = $i + 1; $j < $len; $j++) { // 或者 $this->swap($arr,$j,$j+1);
$this->swap($arr,$i,$j);
}
} return $arr;
} //第二种写法
public function BubbleSort2($arr){
$len = count($arr); if ($len <= 1) {return $arr;} for ($i = 0;$i < $len-1;$i++){ //TODO 本趟排序开始前，交换标志应为假
$flag = false; for ($j = 0;$j <= $len-2;$j++){ $flag = $this->swap($arr,$j,$j+1,$flag);
} if(!$flag) return $arr;
} return $arr;
} //第三种写法
function BubbleSort3(array &$arr){
$len = count($arr); if ($len <= 1) {return $arr;} for($i = 0;$i < $len-1;$i++){ //从后往前逐层上浮小的元素 $j >= 0
for($j = $len - 2;$j >= $i ;$j --){ $this->swap($arr,$j,$j+1);
}
} return $arr;
} //第四种写法
function bubbleSort4($arr)
{
$len = count($arr); if ($len <= 1) {return $arr;} for($i = 0;$i < $len-1;$i++) { for($j = 0;$j < $len-$i-1;$j++) { $this->swap($arr,$j,$j+1);
}
} return $arr;
}Copy after login
Summary:
Time complexity: O(n^2)
Supplement: You can use the PHP built-in function sort() or rsort().
The above functions can be used to index the array according to Sort by key and assign new keys to the cells in the array. This will delete the original keys rather than just reorder them. If successful, return TRUE, otherwise return FALSE
[2]. Select sorting
Idea analysis:
Each time from the data elements to be sorted Select the smallest (or largest) element from the sequence and store it at the beginning of the sequence until all the data elements to be sorted are arranged
Code implementation
/*
* @param 选择排序法
* 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
* */
function selectSort($arr){
//双重循环完成，外层控制轮数，内层控制比较次数
$len = count($arr); if ($len <= 1) {return $arr;} for ($i = 0; $i < $len-1; $i++) { $minIndex = $i; // 找出i后面最小的元素与当前元素交换
for ($j = $i + 1; $j < $len; $j++) { if ($arr[$minIndex] > $arr[$j]){ $minIndex = $j;
}
} if ($minIndex != $i) { $temp = $arr[$i]; $arr[$i] = $arr[$minIndex]; $arr[$minIndex] = $temp;
}
} return $arr;
}Copy after login
Summary:
Time complexity: O(n^2)
Unstable sorting method (for example, in the sequence [5, 5, 3], the first [5] and [3] are exchanged for the first time, causing the first 5 to be moved behind the second 5).
In a selection, if an element is smaller than the current element, and the small element appears behind an element that is equal to the current element, then the stability will be destroyed after the exchange.
The best case is that it is already in order and exchanged 0 times; the worst case is exchanged n-1 times and n/2 times in reverse order. The number of exchanges is much less than that of bubble sort. Since exchange requires more CPU time than comparison, when the n value is small, selection sort is faster than bubble sort
【三】.Insertion sort
Idea analysis:
Code implementation
There are two ways of writing, mainly the loop writing method is slightly different Different, please refer to it. /*
* 插入排序法
* 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
* */
function insertSort($arr){
$len = count($arr); if ($len <= 1) {return $arr;} //先默认$array[0]，已经有序，是有序表
for($i = 1;$i < $len;$i++){ if ($arr[$i] < $arr[$i-1]){ $insertVal = $arr[$i]; //$insertVal是准备插入的数
$insertIndex = $i - 1; //有序表中准备比较的数的下标
while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){ $arr[$insertIndex + 1] = $arr[$insertIndex]; //将数组往后挪
$insertIndex--; //将下标往前挪，准备与前一个进行比较
} if($insertIndex + 1 !== $i){ $arr[$insertIndex + 1] = $insertVal;
}
}
} return $arr;
} function insertSort2($arr){
$len = count($arr); if ($len <= 1) {return $arr;} //先默认$array[0]，已经有序，是有序表
for($i = 1;$i < $len;$i++){ if ($arr[$i] < $arr[$i-1]){ $insertVal = $arr[$i]; //$insertVal是准备插入的数
//$j 有序表中准备比较的数的下标
//$j-- 将下标往前挪，准备与前一个进行比较
for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){ $arr[$j+1]= $arr[$j];//将数组往后挪
} $arr[$j + 1] = $insertVal;
}
} return $arr;
}Copy after login
Idea analysis:
Split the data to be sorted into independent There are two parts. All the data in one part is smaller than all the data in the other part.
代码实现
/**
* @param $arr 目标数组
* @param int $l 左起坐标
* @param $r 右起坐标 初始化传入数组时，$r = count($arr)-1
* @return mixed
*/
public function quick_sort(&$arr, $l=0, $r)
{
$length = count($arr); //先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
if(!is_array($arr)||$length <= 1) {return $arr;} if ($l < $r)
{ $i = $l; $j = $r; $baseVal = $arr[$l]; while ($i < $j)
{ // 从右向左找第一个小于$baseVal的数
while($i < $j && $arr[$j] >= $baseVal) $j--; if($i < $j) $arr[$i++] = $arr[$j]; // 从左向右找第一个大于等于$baseVal的数
while($i < $j && $arr[$i] < $baseVal) $i++; if($i < $j) $arr[$j--] = $arr[$i];
} $arr[$i] = $baseVal; $this->quick_sort($arr, $l, $i - 1); // 递归调用
$this->quick_sort($arr, $i + 1, $r); return $arr;
}
} /*
* 快速排序法
* */
public function quick_sort2($arr) {
$length = count($arr); //先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
if(!is_array($arr)||$length <= 1) {return $arr;} //选择第一个元素作为基准
$baseValue = $arr[0]; //遍历除了标尺外的所有元素，按照大小关系放入两个数组内
//初始化两个数组
$leftArr = array(); //小于基准的
$rightArr = array(); //大于基准的
//使用for循环进行遍历，把选定的基准当做比较的对象
for($i = 1; $i<$length; $i++) { if( $arr[$i] < $baseValue) { //放入左边数组
$leftArr[] = $arr[$i];
} else { //放入右边数组
$rightArr[] = $arr[$i];
}
} //再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
$leftArr = $this->quick_sort2($leftArr); $rightArr = $this->quick_sort2($rightArr); //合并 左边 标尺 右边， 注意：array($baseValue),关联着重复数据
return array_merge($leftArr, array($baseValue), $rightArr);
}Copy after login
小结：
【五】.计数排序
思路分析
代码实现
/**
* 计数排序
* @param $arr
* @return array
*/
function countingSort($arr)
{
$len = count( $arr ); if( $len <= 1 ) return $arr; // 找出待排序的数组中最大值和最小值
$min = min($arr); $max = max($arr); // 计算待排序的数组中每个元素的个数
$countArr = array(); for($i = $min; $i <= $max; $i++)
{ $countArr[$i] = 0;
} foreach($arr as $v)
{ $countArr[$v] += 1;
} $resArr = array(); foreach ($countArr as $k=>$c) { for($i = 0; $i < $c; $i++)
{ $resArr[] = $k;
}
} return $resArr;
}Copy after login
小结：
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序不是比较排序，排序的速度快于任何比较排序算法
最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n+k)
平均情况：T(n) = O(n+k)
限制条件很多 注意
【六】.桶排序
思路分析
代码实现
/**
* 木桶排序设计
* @param $arr 目标数组
* @param int $bucketCount 分配的木桶数目（整数）
* @return array
*/
public function bucketSort($arr,$bucketCount = 10)
{
$len = count($arr); $max = max($arr)+1; if ($len <= 1) {return $arr;} //填充木桶
$arrFill = array_fill(0, $bucketCount, []); //开始标示木桶
for($i = 0; $i < $len ; $i++)
{ $key = intval($arr[$i]/($max/$bucketCount));
array_push($arrFill[$key] , $arr[$i]); //TODO 测试发现：如果此处调用，耗时翻倍
/*if(count($arrFill[$key])){
$arrFill[$key] = $this->insertSort($arrFill[$key]);
}*/
} //对每个不是空的桶进行排序
foreach ($arrFill as $key=>$f){ if (count($f)){ $arrFill[$key] = $this->insertSort($f);
}
} //开始从木桶中拿出数据
for($i = 0; $i < count($arrFill); $i ++)
{ if($arrFill[$i]){ for($j = 0; $j <= count($arrFill[$i]); $j++)
{ //这一行主要用来控制输出多个数字
if ($arrFill[$i][$j]){ $arrBucket[] = $arrFill[$i][$j];
}
}
};
} return $arrBucket;
}Copy after login
注：
总结：
附录
【1】Example sharing of common sorting algorithms in PHP
【2】自行分析
/**
* @param $arr 目标数组
* @return array 返回的已排序数组
*/
public function bOrCSort($arr)
{
$len = count($arr); $max = max($arr); if ($len <= 1) {return $arr;} //填充木桶
$arrFill = array_fill(0, $max, 0); for($i = 0; $i < $len ; $i++)
{ $arrFill[$arr[$i]] ++;
} //开始从木桶中拿出数据
for($i = 0; $i <= $max; $i ++)
{ for($j = 1; $j <= $arrFill[$i]; $j++)
{ //这一行主要用来控制输出多个数字
$arrRes[] = $i;
}
} return $arrRes;
}Copy after login
【3】用时测试
bucketsort 用时：1013.6640071869 ms
countingSort 用时：5.6858062744141 ms
quick_sort 用时：66540.108919144 ms
selectSort 用时：15234.955072403 ms
bubbleSort 用时：162055.89604378 ms
insertSort 用时：12029.093980789 ms
内置sort 用时：3.0169486999512 ms
Copy after login
【4】参考文章
【5】提示
The above is the detailed content of Example sharing of common sorting algorithms in PHP. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
