PHP implements four basic sorting algorithms, four algorithms in php_PHP tutorial

PHP implements four basic sorting algorithms, and PHP has four 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 sort

Idea Analysis: In a group of numbers to be sorted, for the currently unsorted sequence, compare and adjust the two adjacent numbers from front to back, so that the larger number sinks down and the smaller number goes up. Risk. 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:

1. $arr=array(1,43,54,62,21 ,66,32,78,36,76,39 ); > function bubbleSort($arr) {  $len=count($arr); //This layer loop controls the number of rounds that need to bubble
3. for
($i=
4. 1;$i<$len;$i )
5. { //This layer of loop is used to control the number of times a number needs to be compared in each round
6. for($k=0;$k<$len-$i;$k )
7. {
8. if($arr[$k]>$arr[$k 1])
9. {
10. $tmp=$arr[$k 1]; $arr[$k 1
]=$arr[$k];
12. $arr[$k]=$tmp; }
13. } }
14. return
$arr;
16. }
2. Selection sorting
18. 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 loop 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 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 to 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, comparison and insertion
    6. for($j=$i-1;$j>=0;$j--) { 
    7. if($tmp < $arr[$j]) {
    8. //It is found that the inserted element should be smaller, swap the positions, and swap the later elements with the previous elements
    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
    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. }
    http://www.bkjia.com/PHPjc/973828.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/973828.htmlTechArticlePHP implements four basic sorting algorithms, php has four algorithms. Many people say that algorithms are the core of programs, and algorithms Good or bad determines the quality of the program. As a junior phper, although I rarely come into contact with...