PHP 퀵 정렬 퀵 정렬 예 자세한 설명

이 기사의 예에서는 PHP 빠른 정렬을 설명합니다. 참고하실 수 있도록 모두와 공유해 주세요. 자세한 내용은 다음과 같습니다.

quicksort

퀵 정렬 알고리즘에서는 분할 정복 전략을 사용합니다. 먼저, 시퀀스를 두 개의 하위 시퀀스로 나누고 전체 시퀀스가 ​​정렬될 때까지 하위 시퀀스를 재귀적으로 정렬합니다. (즉, 2개로 나누는 아이디어)

단계는 다음과 같습니다.

시퀀스의 핵심 요소를 축으로 선택하고

재순서화합니다. 순서를 변경하고 축을 변경합니다. 작은 요소는 축 앞쪽으로 이동하고, 축보다 큰 요소는 축 뒤쪽으로 이동합니다. 분할 후 축은 최종 위치에 있습니다.

은 두 개의 하위 시퀀스, 즉 더 작은 요소가 있는 하위 시퀀스와 더 큰 요소가 있는 하위 시퀀스를 재귀적으로 재정렬합니다.

예를 들어 $arr:

5 3 0 11 44 ​​​​7 23 2 첫 번째 요소 $arr[0] = 5를 플래그를 낮게 설정하는 축으로 설정합니다. .. top은 시작과 끝을 나타냅니다
2 3 0 11 44 ​​​​7 23 2 반대 방향(오른쪽)에서 비교 시작: 2<5 첫 번째 위치를 2, low++로 대체
2 3 0 11 44 ​​​​7 23 11 :5<11까지 반대 방향(왼쪽)에서 비교를 시작합니다. 마지막 위치를 11, top–
으로 교체합니다. low == top이 될 때까지 위 단계를 반복합니다. 위치를 축 요소로 교체합니다. , 이는 5
2 3 0 5 44 7 23 11
이 방법으로 2 3 0과 44 23 11의 두 부분으로 나눌 수 있습니다
이 방법으로 재귀 연속 시작 단계를 얻을 수 있습니다

알고리즘 구현:

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

이 기사가 PHP 프로그래밍에 종사하는 모든 사람에게 도움이 되기를 바랍니다.

PHP 퀵소트 퀵소트 예제 및 관련 글에 대한 자세한 설명은 PHP 중국어 홈페이지를 참고해주세요!