PHP four basic algorithm code examples_PHP tutorial-PHP Tutorial-php.cn

PHP four basic algorithm code examples_PHP tutorial

WBOY

Release： 2016-07-13 10:25:44

Original

784 people have browsed it

PHP’s four basic algorithms: bubble, selection, insertion and quick sort
Many people say that the algorithm is the core of the program. The key to a program being better than worse is the quality of the 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. Below is my analysis of the four methods according to my own understanding.
Requirements: Use bubble sort, quick sort, selection sort, and insertion sort to sort the values in the array below in ascending order.
$arr(1,43,54,62,21,66,32,78,36,76,39);

1. Bubble sorting method
* Idea analysis: The method is as its name suggests, just like bubbling, the largest number emerges from the array each time.
* For example: 2,4,1 // The first bubble is 4
* 2,1,4 // The second bubble is 2
* 1,2, 4 // It ended up like this

* Code implementation:

Copy code The code is as follows:

$arr=array(1,43,54, 62,21,66,32,78,36,76,39);
function getpao($arr)
{
$len=count($arr);
//Set an empty The array is used to receive bubbles that pop up
//This layer loop controls the number of rounds of bubbles required
for($i=1;$i<$len;$i++)
{ //This The layer loop is used to control the number of times a number needs to be compared in each round
for($k=0;$k<$len-$i;$k++)
{
if($arr[$ k]>$arr[$k+1])
                                                                    $arr ;
          $arr[$k]=$tmp;

2. Selection sorting method:
Selection sorting method idea: Select a corresponding element each time, and then place it in the specified position

Copy code

The code is as follows:

function select_sort($arr) {
//The implementation idea of double loop is completed, the outer layer controls the number of rounds and the current minimum value. The number of comparisons in the inner control

//The position of the current minimum value of $i, the elements that need to be compared for($i=0, $len=count($arr); $i<$len-1 ; $i++) { . for($j=$i+1; $j<$len; $j++) { //$arr[$p] is the currently known minimum value

if($arr[$ p] > $arr[$j]) {

//Compare, find the smaller one, record the position of the minimum value; and in the next comparison,
// The known minimum value should be used Compare.
$p = $j;
//If it is found that the position of the minimum value is different from the current assumed position $i, the positions can be interchanged
If($p != $i) {
$tmp = $arr[$p | > return $arr;
}

3. Insertion sort method
Insertion sort method idea: Insert the elements to be sorted into the specified position of the array whose sort number has been assumed.

Copy code

The code is as follows:

function insert_sort($arr) {
//Distinguish which part is sorted
//Which part is unsorted
//Find one of the elements that needs to be sorted
//This element starts from the second element and ends with the last element that needs to be sorted
//It can be marked using a loop
//i loop controls the elements that need to be inserted each time , once the elements that need to be inserted are controlled,
//Indirectly, the array has been divided into 2 parts. The subscript is smaller than the current one (the one on the left), which is the sorted sequence
for($i=1, $ len=count($arr); $i<$len; $i++) {
//Get the current element value that needs to be compared.
$tmp = $arr[$i];
//Inner loop controls comparison and insertion
for($j=$i-1;$j>=0;$j--) {
//$arr[$i];//The element that needs to be inserted; $arr[$j];//The element that needs to be compared
的> // find that the inserted element should be small, and exchange positions
// Exchange the later elements with the previous elements //Set the previous number to the current number that needs to be exchanged Since it is an array that has been sorted, there is no need to compare the previous ones again.
break;
//Return
return $arr;
}

4. Quick sort method

Copy code

The code is as follows:

function quick_sort($arr) {

//First determine whether you need to continue
$length = count($arr);

if($length <= 1) { return $arr; } //If No return, indicating that the number of elements in the array is more than 1 and needs to be sorted //Select a ruler

//Select the first element

$base_num = $arr[0];
/ /Traverse all elements except the ruler and put them into two arrays according to their size
//Initialize two arrays
$left_array = array();//
less than the ruler $right_array = array( );//
greater than the ruler for($i=1; $i<$length; $i++) {
if($base_num > $arr[$i]) {
//Put Into the left array
$left_array[] = $arr[$i]; }
}
//Then perform the same sorting on the left and right arrays respectively
//Recursively call this function and record the result
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
//Merge the left ruler and the right
return array_merge($left_array, array($base_num), $right_array);
}