Code implementation of four basic sorting algorithms in PHP-PHP Tutorial-php.cn

Code implementation of four basic sorting algorithms in PHP

WBOY

Release： 2016-07-25 08:45:10

Original

1107 people have browsed it

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

$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 be bubbled
for($i=1;$i<$len;$i++)
{ //This layer of loop is used to control the number of bubbles that need to be compared in each round times
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;
}

Copy code

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, and this loop continues until the penultimate number is compared with the last number.

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

Copy code

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.

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]) {
//Find that the inserted element should be smaller, swap the positions, and exchange the later elements with the previous elements
$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;
}

Copy code

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.

function quickSort($arr) {
//Determine first 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 two arrays
$left_array = array(); // Less than the base
$right_array = array(); // Greater than the base
for($i=1; $i<$length; $i++) {
if($base_num > $arr[ $i]) {
//Put it into the left array
$left_array[] = $arr[$i];
} else {
//Put it into the right side
$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);
}