PHP quick sort quicksort example detailed explanation

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

quicksort

In the quick sort algorithm, the divide and conquer strategy is used. First, the sequence is divided into two subsequences, and the subsequences are sorted recursively until the entire sequence is sorted. (That is, the idea of ​​dividing it into two)

The steps are as follows:

Select a key element in the sequence as the axis;

Reorder the sequence, move elements smaller than the axis to the front of the axis, and larger than the axis The elements are moved behind the axis. After the division, the axis is at its final position;

recursively reorders two subsequences: the subsequence with smaller elements and the subsequence with larger elements.

For example, the sequence $arr:

5 3 0 11 44 ​​7 23 2 Set the first element $arr[0] = 5 as the axis and set the flag low... top represents the beginning and the end
2 3 0 11 44 ​​7 23 2 from the opposite Start comparing in the direction (right): 2<5 Replace the first position with 2, low++
2 3 0 11 44 ​​7 23 11 Start comparing in the opposite direction (left) until: 5<11 Replace the last position with 11, top–
Repeat the above steps until low == top Replace the position with the axis element, which is 5
2 3 0 5 44 7 23 11
This way it can be divided into two parts 2 3 0 and 44 23 11
This way you can get Recursively continue with the starting steps

Algorithm implementation:

class quick_sort{
    function quicksort(&$arr,$low,$top){
      if($low < $top){
        $pivotpos = $this->partition($arr,$low,$top);
        $this->quicksort($arr,$low,$pivotpos-1);
        $this->quicksort($arr,$pivotpos+1,$top);
      }
    }
    function partition(&$arr, $low ,$top){
      if($low == $top){
        return;
      }
  //   设置初始数值
      $com = $arr[$low];
      while($low!=$top){
  //      将比初始数值小的替换到左边
        while($top&&$top!=$low){
          if($com > $arr[$top]){
          $arr[$low++] = $arr[$top];
          break;
          }else{
            $top--;
          }
        }
  //      将比初始数值大的替换到右边
        while($low&&$low!=$top){
          if($com < $arr[$low]){
            $arr[$top--] = $arr[$low];
            break;
          }else{
            $low++;
          }
        }
      }
      $arr[$low] = $com;
      return $low;
    }
}

I hope this article will be helpful to everyone in PHP programming.

For more detailed explanations of PHP quicksort quicksort examples and related articles, please pay attention to the PHP Chinese website!