Example of how to implement quick sort 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 achieve quick sorting in the form of examples. Friends who need it can refer to it. I hope it can help. to everyone.

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

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, it needs to be decomposed again, so our recursion point is the newly constructed array The number of elements is greater than 1

Recursive exit: When do we no longer need to sort the new array? 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
)

Related recommendations:

JS Hill sorting and Implementation method of quick sort

Example of php implementing quick sort algorithm for two-dimensional array

How to implement quick sort

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