What are the basic algorithms of PHP?

Many people say that algorithms are the core of programs. The key to whether a program is good or bad is the quality of the program's algorithm. As a junior PHPer, although I have little exposure to algorithmic things. But I think we still need to master the four basic algorithms of bubble sort, insertion sort, selection sort, and quick sort.

Related recommendations: "PHP Tutorial"

Requirements: Use bubble sorting, quick sorting, and selection sorting respectively. , the insertion sort method sorts the values ​​in the array below in ascending order.

$arr=array(11,3,56,62,21,66,32,78,36,76,39,88,34);

1. Bubble sort

Introduction:

Bubble Sort (Bubble Sort, Taiwanese translation: bubble sort or bubble sort) 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 array is repeated until no more exchanges are needed, which means that the array has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the array through swapping.

Steps:

1. Compare adjacent elements. If the first one is bigger than the second one, swap them both.

2. 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.

3. Repeat the above steps for all elements except the last one.

4. Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers 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;
}

Sort effect:

2. Select sorting

Introduction:

Selection sort is a simple and intuitive sorting algorithm. Here's how it works. First, find the smallest element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest element from the remaining unsorted elements, and then put it at the end of the sorted 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;
}

Sort effect:

##3. Insertion sort

Introduction:

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 the sorted sequence, finds the corresponding position and inserts it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.

Steps:

1. Starting from the first element, this element can be considered to have been sorted

2. Take out the next element, and put it in the sorted Scan the element sequence from back to front

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

4. Repeat step 3, Until you find a position where the sorted element is less than or equal to the new element

5. Insert the new element into the position

6. Repeat step 2

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;
}

Sort effect:

4. Quick sort

Introduction:

Quick sort It is a sorting algorithm developed by Tony Hall. 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 Ο(n log n) algorithms because its inner loop can be implemented efficiently on most architectures and works well on most real-world applications. Data can determine design choices, reducing the possibility of quadratic terms in time required.

Steps:

1. Pick an element from the sequence, called the "pivot",

2. Reorder the sequence, all elements Elements smaller than the base value are placed in front of the base, and all elements larger than the base value 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.

3. Recursively sort the subarray of elements smaller than the base value and the subarray of elements greater than the base 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);
}

Sort effect:

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