What are the commonly used algorithms in PHP?

There are four basic algorithms related to php, namely: bubble sort, quick sort, selection sort, insertion sort

1: Bubble sorting method

Introduction:(Recommended learning:PHP programming from entry to master)

Bubble Sorting is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing the two elements in turn, and swapping them if they are in the wrong order.

The work of visiting the sequence is repeated until no more exchanges are needed, which means that the sequence has been sorted. The name of this algorithm comes from the fact that smaller and smaller elements will slowly "float" to the top of the array through swapping.

Steps:

①: Compare adjacent elements. If the first one is larger than the second one, swap them both

②: Do the same work for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the largest number.

③: Repeat the above steps for all elements except the last one

④: Continue to repeat the above steps for fewer and fewer elements each time until there is no pair of numbers left Need to compare

Specific code:

$arr=array(1,43,54,62,21,66,32,78,36,76,39);
  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;
  }

2: Selection sorting method

Selection sorting is a simple and intuitive sorting algorithm. Its working principle is as follows: first, find the smallest element in the unsorted sequence, store it at the starting position of the sorted sequence, and then continue to find the smallest element from the remaining unsorted elements. Then put it at the end of the sort sequence. And so on until all elements are sorted.

Specific code:

  //实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数
  function select_sort($arr) {
  //$i 当前最小值的位置， 需要参与比较的元素
  for($i=0, $len=count($arr); $i<$len-1; $i++) {
 //先假设最小的值的位置
  $p = $i;
  //$j 当前都需要和哪些元素比较，$i 后边的。
  for($j=$i+1; $j<$len; $j++) {
  //$arr[$p] 是 当前已知的最小值
 if($arr[$p] > $arr[$j]) {
 //比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。
 $p = $j;
 }
 }
 //已经确定了当前的最小值的位置，保存到$p中。
 //如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
 if($p != $i) {
 $tmp = $arr[$p];
 $arr[$p] = $arr[$i];
 $arr[$i] = $tmp;
 }
 }
 //返回最终结果
 return $arr;
 }

3: Insertion sort

The algorithm description of insertion sort is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence. For unsorted data, it scans from back to front in a sorted sequence to find the corresponding position and insert it.

In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only requires O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly sort the sorted The final elements are gradually moved backward to provide space for the latest elements to be inserted.

Steps:

①Start from the first element, which can be considered to have been sorted

②Take out the next element, after it has been sorted Scan the element sequence from back to front

③If the element (sorted) is larger than the new element, move the element to the next position

④Repeat step ③ until you find the The sorted element is less than or equal to the position of the new element

⑤Insert the new element into the position

⑥Repeat step ②

Specific code:

  function insert_sort($arr)
  {
  $len=count($arr);
  for($i=1; $i<$len; $i++) {
 //获得当前需要比较的元素值。
  $tmp = $arr[$i];
  //内层循环控制 比较 并 插入
  for($j=$i-1; $j>=0; $j--) {
  //$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素 
    if($tmp < $arr[$j]) {
 //发现插入的元素要小，交换位置
 //将后边的元素与前面的元素互换
     $arr[$j+1] = $arr[$j];
 //将前面的数设置为 当前需要交换的数
     $arr[$j] = $tmp;
     } else {
 //如果碰到不需要移动的元素
 //由于是已经排序好是数组，则前面的就不需要再次比较了。
     break;
     }
 }
 }
 //将这个元素 插入到已经排序好的序列内。
 //返回
 return $arr;
 }

4: Quick sort

Introduction:

Quick sort is a method developed by Tony Hall Sorting Algorithm. On average, sorting n items requires O(n log n) comparisons.

In the worst case, O(n2) comparisons are required, but this situation is uncommon. In fact, quicksort is often significantly faster than other O(n log n) algorithms because its inner loop can be implemented efficiently on most architectures, and for most real-world data, Can determine design choices that reduce the possibility of quadratic time required.

Steps:

① Pick out an element from the sequence, called the 'baseline'

② Repeat the sorting sequence, all elements are better than the base value Small ones are placed in front of the base, and all elements larger than the base are placed behind the base (the same number can go to either side). After this partition exits, the base is in the middle of the sequence. This is called a partition operation

③Recursively sort the subarray of elements smaller than the baseline value and the subarray of elements larger than the baseline value

Specific code:

  function quick_sort($arr)
  {
  //判断参数是否是一个数组
  if(!is_array($arr)) return false;
  //递归出口:数组长度为1，直接返回数组
  $length = count($arr);
  if($length<=1) return $arr;
  //数组元素有多个,则定义两个空数组
  $left = $right = array();
 //使用for循环进行遍历，把第一个元素当做比较的对象
 for($i=1; $i<$length; $i++)
 {
 //判断当前元素的大小
 if($arr[$i]<$arr[0]){
 $left[]=$arr[$i];
 }else{
 $right[]=$arr[$i];
 }
 }
 //递归调用
 $left=quick_sort($left);
 $right=quick_sort($right);
 //将所有的结果合并
 return array_merge($left,array($arr[0]),$right);
 }

The above is the detailed content of What are the commonly used algorithms in PHP?. For more information, please follow other related articles on the PHP Chinese website!