PHP implements 4 sorting algorithms_PHP tutorial

php implements 4 sorting algorithms

The article comes from "PHP100 Chinese website"

Premise: Use bubble sort, quick sort, selection sort, and insertion sort to sort the values ​​in the following array 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 downward and the smaller number moves downward. Coming up. 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 loop controls the number of rounds that need to bubble
for($i=1;$i { //This layer of loop is used to control the number of times a number needs to be compared in each round
for($k=0;$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: 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:
function selectSort($arr) {
//The 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 //First assume the position of the smallest value
$p = $i;

for($j=$i+1; $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;
}

3. Insertion sort

Idea analysis: In a set of numbers to be sorted, assuming that the previous numbers are already in order, now the nth number needs to be inserted into the previous ordered numbers so that these n numbers are also in order. Repeat this cycle until everything is in order.

Code implementation:
function insertSort($arr) {
$len=count($arr);
for($i=1, $i $tmp = $arr[$i];
//Inner loop control, compare and insert
for($j=$i-1;$j>=0;$j--) {
if($tmp //It is found that the inserted element is 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;
}

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) {
//Determine first whether you need to continue
$length = count($arr);
if($length 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
//Initialize two arrays
$left_array = array(); //
less than the baseline $right_array = array(); //
greater than the baseline for($i=1; $i if($base_num > $arr[$i]) {
//Put it into the left array
$left_array[] = $arr[$i];
} else {
//Put it on the right
$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);
}

http://www.bkjia.com/PHPjc/962641.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/962641.htmlTechArticlephp implements 4 sorting algorithms. The article comes from "PHP100 Chinese website" Prerequisite: use bubble sorting and quick sorting respectively Method, selection sort method, insertion sort method sort the items in the following array from small to small...