An example of how to implement quick sort recursively in PHP

This article mainly introduces the method of PHP recursive implementation of quick sorting. It briefly describes the principle of quick sorting and analyzes the relevant operating skills of PHP using recursive algorithms to implement quick sorting in the form of examples. Friends in need can refer to the following

The example in this article describes the method of implementing quick sort recursively in PHP. Share it with everyone for your reference, the details are as follows:

First we need to understand the principle of quick sort:Find any element in the current array (generally select the first element ), as a standard, create two empty arrays and traverse the entire array elements. If the traversed element is smaller than the current element, then put it in the array on the left, otherwise put it in the array on the right, and then do the same with the new array. operation.

It is not difficult to find that this is consistent with the principle of recursion, so we can use recursion to implement it.

To use recursion, you need to find the recursion point and recursion exit:

Recursion point: If the elements of the array are greater than 1, then It needs to be decomposed again, so our recursion point is that the number of newly constructed array elements is greater than 1

Recursive exit:When do we no longer need to process a new array? No more sorting? That's when the number of array elements becomes 1, so this is our exit.

Understand the principle, let’s take a look at the code implementation~

<?php
//快速排序
//待排序数组
$arr=array(6,3,8,6,4,2,9,5,1);
//函数实现快速排序
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);
}
//调用
echo "<pre class="brush:php;toolbar:false">";
print_r(quick_sort($arr));

Running results:

Array
(
  [0] => 1
  [1] => 2
  [2] => 3
  [3] => 4
  [4] => 5
  [5] => 6
  [6] => 6
  [7] => 8
  [8] => 9
)

PS: Here is another demonstration tool about sorting recommended for your reference:

##Online animation demonstration insertion/selection/bubble/merge/Hill/quick sort algorithm process tool:
http://tools.jb51.net/aideddesign/paixu_ys

Articles you may be interested in:

Detailed tutorial on how to implement git deployment in PHP

Dichotomy of PHP implementation Search algorithm example analysis and explanation

Example explanation of the half search algorithm implemented in PHP

The above is the detailed content of An example of how to implement quick sort recursively in PHP. For more information, please follow other related articles on the PHP Chinese website!