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 sort

Idea analysis: In a group of numbers to be sorted, for the sequence that has not yet been sorted, compare and adjust the two adjacent numbers from front to back, so that the larger number sinks down, and the larger number sinks. The small one rises upward. That is, whenever two adjacent numbers are compared and their ordering is found to be opposite to the ordering requirements, they are swapped.

Code implementation:

$arr=array(1,43,54,62,21,66,32,78,36,76,39);
function bubbleSort($arr)
{
 $ len=count($arr);
 //This layer of loop controls the number of rounds that need to bubble
 for($i=1;$i<$len;$i++)
 { //This layer of loop is used to control each round The number of times a number needs to be compared
 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. Select sort

Idea analysis: In 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. This cycle continues until the penultimate number is compared with the last number.

Code implementation:

function selectSort($arr) {
//Double loop is completed, the outer layer controls the number of rounds, and the inner layer controls the number of comparisons
 $len=count($arr);
 for($ i=0; $i<$len-1; $i++) {
 //Assume the position of the minimum value first
 $p = $i;

 for($j=$i+1; $j<$len ; $j++) {
 //$arr[$p] is the currently known minimum value
 if($arr[$p] > $arr[$j]) {
 //Compare and find smaller, Record the position of the minimum value; and use the known minimum value for comparison in the next comparison.
 $p = $j;
 }
 }
 //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.
 if($p != $i) {
 $tmp = $arr[$p];
 $arr[$p] = $arr[$i];
 $arr[$i] = $tmp;
 }
 }
 //Return the final result
 return $arr;
}

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 of. Repeat this cycle until everything is in order.

Code implementation:

function insertSort($arr) {
 $len=count($arr);
 for($i=1, $i<$len; $i++) {
 $tmp = $arr[$i];
 //Inner loop control, compare and insert
 for($j=$i-1;$j>=0;$j--) {
 if($tmp < $arr [$j]) {
 //It is found that the inserted element is smaller, swap the positions, and swap the later elements with the previous ones
 $arr[$j+1] = $arr[$j];
 $arr[ $j] = $tmp;
 } else {
 //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.
 break;
 }
 }
 }
 return $arr;
}

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:

function quickSort($arr) {
 //First determine whether you need to continue
 $length = count($arr);
 if($length <= 1) {
 return $arr;
 }
 //Select the first element as the base
 $base_num = $arr[0];
 //Traverse all elements except the ruler and put them into two arrays according to their size relationship
 //Initialize both array
 $left_array = array(); // Smaller than the baseline
 $right_array = array(); // Larger than the baseline
 for($i=1; $i<$length; $i++) {
 if($ base_num > $arr[$i]) {
 //Put in the left array
 $left_array[] = $arr[$i];
 } else {
 //Put in the right array
 $right_array[] = $arr[ $i];
 }
 }
 //Then perform the same sorting on the left and right arrays and call this function recursively
 $left_array = quick_sort($left_array);
 $right_array = quick_sort($right_array);
 //Merge
 return array_merge($left_array, array($base_num), $right_array);
}

Original text: http://www.php100.com/html/dujia/2015/0210/8604.html

Four types, PHP