PHP sorting algorithm principle and summary

Bubble sorting principle

Principle description:

Compare two adjacent elements at a time, the larger element is moved backward, and the smaller element is moved forward (swap Location). until the largest element is found. Just like bubbles, big ones sink downwards and small ones rise upwards.

Process:

There is an unordered array $arr = [8, 9, 3, 6, 1, 4]

第一次外循环 ：找出最大值 9，要俩俩相比，比 5 次。
8 9 3 6 1 4 第一次， 8 跟 9 比，9 大，所以没有交换位置。
8 3 9 6 1 4 第二次， 9 跟 3 比， 9 大，交换位置。
8 3 6 9 1 4 第三次， 9 跟 6 比， 9 大，交换位置。
8 3 6 1 9 4 第四次， 9 跟 1 比， 9 大，交换位置。
8 3 6 1 4 9 第五次， 9 跟 4 比， 9 大，交换位置。
第二次外循环：找出第二大值 8，要俩俩相比，比 4 次。因为上一步已经找到最大值了。
3 8 6 1 4 9 第一次，8 跟 3 比，8 大， 交换位置。
3 6 8 1 4 9 第二次，8 跟 6 比，8 大， 交换位置。
3 6 1 8 4 9 第三次，8 跟 1 比，8 大， 交换位置。
3 6 1 4 8 9 第四次，8 跟 4 比，8 大， 交换位置。
第三次外循环：找出第三大的值 6，要俩俩相比，比三次。
3 6 1 4 8 9 第一次，3 跟 6 比，6 大，位置没有变化。
3 1 6 4 8 9 第二次，6 跟 1 比，6 大，交换位置。
3 1 4 6 8 9 第三次，6 跟 4 比，6 大，交换位置。
第四次外循环：找出第四大的值 4，要俩俩相比，比 2 次。
1 3 4 6 8 9 第一次， 3 跟 1 比， 3 大，交换位置。
1 3 4 6 8 9 第二次， 3 跟 4 比， 4 大，位置不变。
第五次外循环：找出第五大的值 3， 比一次就够了。
1 3 4 6 8 9 比一次。1 跟 3 比，3 大，位置没有变化。

Summary:

1. The outer loop requires the number of elements - 1 time. Responsible for finding the maximum value.

2. The inner loop decreases once layer by layer. Responsible for comparing the two and exchanging element positions.

Code:

<?php
        function bubbleSort($arr) 
        {
            $len = count($arr);//获取元素个数
            for ($i = 0; $i < $len - 1; $i ++) {//找出最大值
                $flag = 0;//做一个标记
                for($j = 0; $j < $len - 1 - $i; $j++) {//俩俩相比较，交换位置
                    if ($arr[$j] > $arr[$j + 1]) {
                        //$temp = $arr[$j];//存当前元素
                        //$arr[$j] = $arr[$j + 1];//把当前元素的值换成下一个元素的值
                        //$arr[$j + 1] = $temp;//把下一个元素的值换成上一个元素的值。
                        list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];//来自lovecn的评论，有时候思维有些固化。
                        $flag = 1;//交换位置就记录。
                    }
                }
                if ($flag == 0) {//没有发生交换位置，说明排序已经完成。可以推出循环。
                    break;
                }
            }
            return $arr;
        }

Quick sort principle (recursive)

Principle description:

From array Take the first value as the reference object, put the value smaller than this value on the left, and place the value larger than this value on the right, so there will be two new arrays, recursively process the two arrays, and then the reference object on the left, Merge on the right. Note: If there is recursion, you must find the recursive exit, otherwise the recursion will continue.

Process:

It’s too troublesome to describe the process in words, so I found a picture on the Internet, the process is very clear.

Code:

    <?php
        function quickSort($arr)
        {
            $len = count($arr);
            //递归出口
            if($len <= 1) {
                return $arr;
            }
            $markValue = $arr[0];//参照物。
            $left = $right = [];//定义左边和右边。
            for($i = 1; $i < $len; $i++) {//从1开始循环，因为第一个元素当作参照物。
                if($arr[$i] > $markValue) {//大于参照物的放在右边。
                    $right[] = $arr[$i];
                } else {//小于和等于参照物的元素都放进左边，这样会避免如果数组有重复元素时，会漏掉元素。
                    $left[] = $arr[$i];
                }
            }
            return array_merge(quickSort($left), [$markValue], quickSort($right));
        }

Insertion sort

Principle description:

Will be sorted The array is divided into two parts, the first element of the array is placed in the ordered set, and the remaining elements are placed in the unordered set. Compare the number that needs to be sorted with the previously sorted data from back to front until you find a number that is less than or equal to it, and insert it into the corresponding position.

My memory method:

Suppose there are two boxes. The first box is transparent and empty, and is used to contain ordered elements. The second box is opaque and empty. Full, containing unordered elements. (Actually, you can pretend to be anything, whatever you like and is easy for you to remember is best).

1. Step one: Pick up an element from the opaque box and throw it directly into the transparent box
2. Step two: Take out an element from the opaque box and put it in In front of the transparent box, make a comparison. If it's big, put it in the back; if it's small, put it in the front.
3. Repeat the second step, but the number of comparisons we need to make each time increases because there are more elements in the transparent box until we find the right position.

Process:

<?php
    function insertSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一个元素或者没有元素，排序无意义。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            for($j = $i + 1; $j > 0; $j--){//每次比较次数增加。因为有序集合元素在增加。
                if ($arr[$j] < $arr[$j - 1]) {
                    list($arr[$j], $arr[$j - 1]) = [$arr[$j - 1], $arr[$j]];//交换位置。
                }
            }
        }
        return $arr;
    }

Selection sort

Principle description:

One time at a time Remove the minimum element or maximum element from the array and place it at the specified position.

Step one: Give the first element a Holy Fire Order, and compare it with each subsequent element (I take the smallest element). If you encounter an element that is smaller than it, give it the Holy Fire Token until you know how to give the Holy Fire Token to the smallest element.

Step 2: Exchange positions, hand the Holy Fire Order to the second brother Element, and repeat the first step.

Process:

<?php
    function selectSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一个元素或者没有元素，排序没有意义。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            $p = $i;//给第一个元素圣火令。
            for($j =  $i + 1; $j < $len; $j++) {
                if ($arr[$j] < $arr[$p]) {//有圣火令的元素和后面的元素比较，把圣火令交给较小的元素。
                    $p = $j;
                }
            }
            list($arr[$p], $arr[$i]) = [$arr[$i], $arr[p]];
        }
        return $arr;
    }

The above is the detailed content of PHP sorting algorithm principle and summary. For more information, please follow other related articles on the PHP Chinese website!