PHP의 Quicksort 사용 예에 ​​대한 자세한 설명

이 글에서는 주로 PHP 퀵 정렬 quicksort의 구현 방법을 소개합니다. 퀵 정렬의 원리와 PHP의 관련 연산 기술을 분석하여 퀵 정렬이 필요한 친구들이 참고할 수 있습니다

이 기사에서는 PHP 빠른 정렬 정렬 퀵 정렬의 예를 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

quicksort

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

단계는 다음과 같습니다.

시퀀스의 핵심 요소를 축으로 선택합니다.

시퀀스를 재정렬하고 요소를 축보다 작게 이동합니다. 축이 더 큰 요소는 축 뒤로 이동됩니다. 분할 후 축은 최종 위치에 있습니다.

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

예를 들어 $arr:

5 3 0 11 44 ​​​​7 23 2 첫 번째 요소 $arr[0] = 5를 축으로 설정하고 플래그를 low로 설정합니다... top은 시작을 나타내고 end

2 3 0 11 44 ​​​​7 23 2 반대 방향에서 비교 시작(오른쪽): 2<5 첫 번째 위치를 2, low++로 교체

2 3 0 11 44 ​​​​7 23 11 에서 비교 시작 5<11까지 반대 방향(왼쪽): 5<11 마지막 위치를 11, top–
낮음 == 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의 Quicksort 사용 예에 ​​대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!