PHP implements four basic sorting algorithms

Many people say that the algorithm is the core of the program, and the quality of the algorithm determines the quality of the program. As a junior PHPer, although I have little exposure to algorithmic things. However, you should still master the basic sorting algorithm. It is an essential tool for program development. Here we introduce four basic algorithms: bubble sort, insertion sort, selection sort, and quick sort, and analyze the ideas of the algorithm.
Premise: Use bubble sort, quick sort, selection sort, and insertion sort to sort the values ​​in the array below in order from small to large.
$arr(1,43,54,62,21,66,32,78,36,76,39);
1. Bubble sorting
Idea analysis: In a set of numbers to be sorted, there are currently no In the arranged sequence, compare and adjust the two adjacent numbers from front to back, so that the larger number sinks and the smaller number rises. That is, whenever two adjacent numbers are compared and it is found that their ordering is opposite to the ordering requirement, they are swapped.
Code implementation:

Java code

1. $arr=array(1,43,54,62,21,66,32,78,36, 76,39 );
2. function bubbleSort($arr)
3. {
4. $len=count($arr);
5. //This layer loop controls the number of rounds that need to bubble
6. for($i=1;$i<$len;$i++)
7. { //This layer of loop is used to control the number of times that a number needs to be compared in each round
8. for($k=0;$k<$len-$i;$k++)
9. {
10. if($arr[$k]>$arr[$k+1])
11. {
12. $tmp=$arr[$k+1];
13. $arr[$k+1]=$arr[$k];
14. $arr[$k]=$tmp;
15. }
16. }
17. }
18. return $arr;
19. }

2. Selection sort
Idea analysis: From a set of numbers to be sorted, select the smallest number and exchange it with the number in the first position. Then find the smallest among the remaining numbers and exchange it with the number in the second position, and this loop continues until the penultimate number is compared with the last number.
Code implementation:

Java code

1. function selectSort($arr) {
2. //The double cycle is completed, the outer layer controls the number of rounds, and the inner layer controls the number of comparisons​
3. $len=count($arr);
4. for($i=0; $i<$len-1; $i++) {
5. //Assume the position of the minimum value first
6. $p = $i;
8. for($j=$i+1; $j<$len; $j++) {
9. //$arr[$p] is the currently known minimum value
10. if($arr[$p] > $arr[$j]) {
11. //Compare, find the smaller one, record the position of the minimum value; and use the known minimum value for comparison in the next comparison.
12. $p = $j;
13. }
14. }
15. //The current minimum value position has been determined and saved to $p. If it is found that the position of the minimum value is different from the currently assumed position $i, the positions can be interchanged.
16. if($p != $i) {
17. $tmp = $arr[$p];
18. $arr[$p] = $arr[$i];
19. $arr[$i] = $tmp;
20. }
21. }
22. //Return to the final result​
23. return $arr;
24. }

3. Insertion sort
Idea analysis: In a set of numbers to be sorted, assuming that the previous numbers are already in order, now we need to insert the nth number into the previous ordered numbers, so that these n numbers are also In order. Repeat this cycle until everything is in order.
Code implementation:

Java code

1. function insertSort($arr) {
2. $len=count($arr);
3. for($i=1, $i<$len; $i++) {
4. $tmp = $arr[$i];
5. //Inner loop control, compare and insert
6. for($j=$i-1;$j>=0;$j--) {
7. if($tmp < $arr[$j]) {
8. //If you find that the inserted element is smaller, swap the positions and swap the later elements with the previous ones
9. $arr[$j+1] = $arr[$j];
10. $arr[$j] = $tmp;
11. } else {
12. //If you encounter an element that does not need to be moved, since it is an array that has been sorted, the previous ones do not need to be compared again.
13. break;
14. }
15. }
16. }
17. return $arr;
18. }

4. Quick sort
Idea analysis: Select a benchmark element, usually the first element or the last element. Through one scan, the column to be sorted is divided into two parts, one part is smaller than the reference element, and the other part is greater than or equal to the reference element. At this time, the base element is at its correct position after sorting, and then the two divided parts are sorted recursively in the same way.
Code implementation:

Java code

1. function quickSort($arr) {
2. //Determine first whether you need to continue
3. $length = count($arr);
4. if($length <= 1) {
5. return $arr;
6. }
7. //Select the first element as the base
8. $base_num = $arr[0];
9. //Traverse all elements except the ruler and put them into two arrays according to their size
10. //Initialize two arrays​
11. $left_array = array(); //less than the benchmark
12. $right_array = array(); //Greater than the benchmark
13. for($i=1; $i<$length; $i++) {
14. if($base_num > $arr[$i]) {
15. //Put it into the left array​
16. $left_array[] = $arr[$i];
17. } else {
18. //Put it on the right side​
19. $right_array[] = $arr[$i];
20. }
21. }
22. //Then perform the same sorting on the left and right arrays and call this function recursively
23. $left_array = quick_sort($left_array);
24. $right_array = quick_sort($right_array);
25. //Merge
26. return array_merge($left_array, array($base_num), $right_array);
27. }

The above introduces the implementation of four basic sorting algorithms in PHP, including aspects. I hope it will be helpful to friends who are interested in PHP tutorials.