Detailed explanation of usage examples of quicksort in php

This article mainly introduces the implementation method of PHP quick sort quicksort. It analyzes the principle of quick sort and the related operating skills of PHP to implement quick sort in the form of examples. Friends in need can refer to the following

The example in this article describes PHP quick sort quicksort. 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 recursively sorts the subsequences 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;

Carry out the sequence Reorder, move elements smaller than the axis to the front of the axis, and move elements larger than the axis to the back of 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 Use the first element $arr[0] = 5 as the axis to set the flag bit low...top represents the beginning and the end
2 3 0 11 44 ​​7 23 2 Start comparing from the opposite direction (right): 2<5 Replace the first position with 2, low++
2 3 0 11 44 ​​7 23 11 Start comparing from 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, that is, 5
2 3 0 5 44 7 23 11
This way Can be divided into two parts 2 3 0 and 44 23 11
This way we can get the recursive continuation starting step

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;
    }
}

The above is the detailed content of Detailed explanation of usage examples of quicksort in php. For more information, please follow other related articles on the PHP Chinese website!