PHP常用基础算法

摘要:冒泡排序、选择排序

冒泡排序

依次比较相邻的两个数,然后根据大小做出排序并移动指针,直至最后两位数。由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。

步骤:

(1)比较相邻的元素。如果第一个比第二个大,就交换他们两个的指针。

(2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

(3)针对所有的元素重复以上的步骤,除了最后一个。

(4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

//大数在前,小数在后
public function bubbleSort($arr){
$len=count($arr);
//该层循环控制 需要冒泡的轮数
for($i=1;$i<$len;$i++){
//该层循环用来控制每轮 冒出一个数 需要比较的次数
for($j=0;$j<$len-$i;$j++){ //把小于号换成大于号就是,小数在前,大数在后
if($arr[$j]<$arr[$j+1]){
list($arr[$j+1],$arr[$j])=[$arr[$j],$arr[$j+1]];
}
}
}
return $arr;
}

选择排序

选择排序在冒泡排序的基础上进行了改进,每次通过列表时只进行一次传递交换。

简单来说就是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 

选择排序是不稳定的排序方法。

步骤:

(1)先假设最小值的位置。

(2)把当前假设的值与剩下的元素做比较。

(3)比较,发现更小的,记录下最小的位置;并在下次比较的时候,采用已知的最小值最比较。

(4)如果发现,最小值的位置与当前假设的最小值的位置不同,则位置互换。反之,假设成立,当前位置保留继续往下找,直到排序完成。

/**
* 选择排序法
* @param array $arr
* @return array
*/
function select_sort($arr) {
// 判断参数是否为数组,且不为空
if (!is_array($arr) || empty($arr)) {
return $arr;
}
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
// 假设最小数的位置
$min = $i;
// 用假设的最小数和$i后面的数循环比较,找到实际的最小数
for ($j = $i + 1; $j < $len; $j++) {
// 后面的数比假设的最小数小,替换最小数
if ($arr[$min] > $arr[$j]) {
$min = $j;
}
}
// 假设的最小数和实际不符,交换位置
if ($min != $i) {
$temp = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $temp;
}
}
return $arr;
}