How to implement array sorting in PHP: quick sort, insertion sort, merge sort algorithm

There are many ways to sort arrays in php, and each array sorting has its own different principles. Let’s take a closer look at the examples of quick sort algorithm, merge sort algorithm and insertion sort algorithm.

Traversal of special-shaped arrays

Find the average of the numbers in the following array:

$arr1 = array(
1, 2, array(31, 32, 33), 4,
array(51, 52, 53, array(541, 542, 543, 544) ),
6, array(71, 72, 73),
);
$count = 0; //计数
$sum = GetArraySum($arr1);
echo “\

Quick sort algorithm

Principle description:

For such an array: [5, 1,2, 6,7];

Take out the first item (and use it as the intermediate array), and After comparing the remaining items, they are divided into two arrays:

The left array item is smaller than the middle item, and the right array item is not smaller than the middle item.

If the left array and the right array are already sorted arrays, then merge the three to get the final result.

If the left array and the right array are not sorted arrays, continue to use this function recursively to obtain the ordered arrays.

Schematic diagram:

Principal data:

$arr1 = [5, 2, 1, 6,7]; / /Data that effectively illustrates the principle 1

Small: [2, 1], Large: [6, 7], Middle: [5]

Combine the three: [1 , 2, 5, 6, 7];

$arr1 = [2, 1]; //Data that effectively illustrates the principle 2

Middle: [2], Left: [1] , []

Specific case:

$arr1 = [5, 2, 4, 6, 1, 3];
$arr1 = [5, 2, 4, 6, 1, 3];
//$arr1 = [5, 3, 2, 8, 7];
echo “\

Insertion sort algorithm

Principle description:

For such an array: [2 , 3, 4, 1];

To insert a certain number n into a sorted array,

Just add n followed by the item of the array from back to front In a comparison, as long as an item is found to be larger than n,

will move the item back one place, and then continue to take it out and compare it. If it is larger than n, move it back one place, and so on.

In the end, when there is nothing larger than n, put n into the position that was left empty when moving backward.

For an array, the first item can be regarded as an "already sorted" array,

then the second item can be "inserted sorted" according to the above principle, so the previous Two can be sorted,

and become a "sorted array" with two elements. This is followed by analogy.

Schematic diagram:

Principle data:

$arr1 = [2, 3, 4, 1]; //Strong explanation Data of the principle 1

$arr1 = [2, 3, 1]; //Data that effectively illustrates the principle 2

$arr1 = [2, 1]; //Data that effectively illustrates the principle Data 3

$arr1 = [1, 2]; //Data 3

that effectively illustrates the principle:

$arr1 = [5, 2, 4, 6, 1, 3];
$arr1 = [2, 3, 4, 1];
$arr1 = [2, 4, 5, 6, 1, 3];
echo “\

Merge sort algorithm

Principle description:

For such an array: $arr1 = [1, 3, 5, 2, 4, 6]; divide it into two: $a = [1 , 3, 5],
$b = [2, 4, 6];

If there are two arrays that have been sorted, then after performing the following operations on the two arrays, You can get a sorted "fusion array" of the two arrays:

Take out the first item a1 of array a, then take out the first item b1 of array b, compare the sizes of a1 and b1,

Put the small one (assumed to be a1) into a new array, and delete the first item of the corresponding array a,

Then take out the first item of the corresponding array (not just now the data), and then continue to compare the sizes of the two

each time, put the smaller one into a new array, and continue the next "delete, fetch, compare". . . .

The final result is that you can get a new sorted array in the new array.

For an array that has not yet been sorted, as long as it is recursively divided into two, the shortest array will eventually be obtained - only one or 0 cells. This kind of array is naturally sorted. In good order.

Schematic diagram:

Principle data:

$arr1 = [1, 3, 5, 4, 6, 7, 8 ]; //The data 1

that strongly illustrates the principle is divided into 2 from the middle: [ ]; [ 6, 7, 8]

[ 1, 3, 4, 5, ]

$arr1 = [1, 3, 2, 4]; //Data that effectively illustrates the principle 2

Demonstration case:

$arr1 = [5, 2, 4, 6, 1, 3];
echo “\

Related recommendations:

php bubble sort quick sort, php bubble sort

php array sorting method sharing (bubble sort, selection Sort)

The above is the detailed content of How to implement array sorting in PHP: quick sort, insertion sort, merge sort algorithm. For more information, please follow other related articles on the PHP Chinese website!