[PHP Interview] An explanation of two simple sorting algorithms that must be asked in the interview: bubble sort and quick sort

Generally when facing interviews, we have no problem answering the interview questions. For PHP developers, in addition to being familiar with the projects they are doing, they also need to understand basic algorithms. Let’s share the algorithms that are often asked in PHP interviews: bubble sort and quick sort.

Bubble sorting: one-to-one comparison sorting

Basic idea:

Repeatedly visit the element sequence to be sorted , compare two adjacent elements in turn, and swap them if their order (such as from large to small) is wrong. The work of visiting elements is repeated until no adjacent elements need to be exchanged, which means that the elements have been sorted.

Illustration:

1. The first time: holding the first element of the array, Start comparing from the second element respectively. If the previous element is larger than the later element, swap the two elements to get the larger value. Continue the backward comparison until the end of the array element to achieve a bubbling (bubble Once, the maximum value of the current "remaining" array is obtained and placed at the "end" of the array)

2. Starting from the second time, the comparison still starts from the first element, but only the array is compared. The length should be -1 position, and the number of comparisons each time is -1

3. Repeat the comparison until finally there is no more numbers to compare

Code:

$arr = array(3,2,6,0,1,4,7);
        //因为排序需要每次将一个元素与数组的其他元素进行比较，所以需要两层循环来控制
        //外层循环控制冒泡次数
        //内存循环比较每次的大小，得到每次的最大值（泡）
 
        for($i = 0,$length = count($arr);$i < $length;$i++){
        
                 //内存循环
                 for($j = 0;$j < ($length - $i - 1);$j++){
                         //拿着j变量所对应的数组元素，与后面的元素进行比较
                         if($arr[$j] > $arr[$j + 1]){
                                  //交换位置
                                  $temp              = $arr[$j];
                                  $arr[$j]           = $arr[$j+1];
                                  $arr[$j+1]         = $temp;
                         }
                 }
        }

Summary:

The best time complexity of bubble sorting is O(n). Although it is not the optimal algorithm, it is something we often come into contact with and will also be asked in interviews. So we must understand the basic principles, be able to understand them, and be able to write them

Quick sort: Exchange space for time

Basic idea ：

Divide the data to be sorted into two independent parts through one sorting. All the data in one part is smaller than all the data in the other part, and then use this method to separate the two parts of the data. Quick sort, the entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.

Illustration:

Find any element in the current array, as a standard, create two new empty arrays and traverse the entire array element, the traversed element is smaller than the current element, then put it in the array on the left; if it is larger, put it in another array

Recursive idea

1. Recursion point: If two If the elements of an array are greater than 1, they need to be decomposed again

2. Recursive exit: when the array element becomes 1

Code:

//待排序数组
        $arr = array(5,3,8,2,6,4,7);
        //函数实现快速排序
        function quick_sort($arr){
                 //判断参数是否是一个数组
                 if(!is_array($arr)) return false;
 
                 //递归出口：数组长度为1就直接返回数组
                 $length = count($arr);
                 if($length <= 1) return $arr;

                 //数组元素有多个
                 $left = $right = array();
                 //使用for循环进行遍历，把第一个元素当做比较的对象
                 for($i = 1;$i < $length;$i++){
                         //判断当前元素值的大小
                         if($arr[$i] < $arr[0]){
                                  //当前元素小于标准元素，放到左边数组
                                  $left[] = $arr[$i];
                         }else{
                                  $right[] = $arr[$i];
                         }
                 }
                 //递归调用
                 $left = quick_sort($left);
                 $right = quick_sort($right);
 
                 //将所有的结果合并
                 return array_merge($left,array($arr[0]),$right);
        }

Summary:

Quick sort is the fastest sorting method among general sorting methods. It is based on recursion and uses space for time. In general interviews, you will be asked to know the basic principles.

[Related tutorials: PHP video tutorial]

The above is the detailed content of [PHP Interview] An explanation of two simple sorting algorithms that must be asked in the interview: bubble sort and quick sort. For more information, please follow other related articles on the PHP Chinese website!