PHP 빠른 정렬 알고리즘_php 기술에 대한 자세한 설명

콘셉트

다음은 Baidu Encyclopedia에서 가져온 매우 생생한 사진입니다.

퀵 정렬 알고리즘은 버블 알고리즘을 최적화한 것입니다. 그의 아이디어는 먼저 배열을 분할하고 큰 요소 값을 임시 배열에 넣고 작은 요소 값을 다른 임시 배열에 넣는 것입니다(분할 지점은 배열의 모든 요소 값이 될 수 있으며 일반적으로 첫 번째 요소를 사용합니다) 요소, 즉 $array[0]) 그런 다음 위의 두 임시 배열 분할을 계속 반복하고 마지막으로 작은 배열 요소와 큰 배열 요소를 병합합니다. 여기서는 재귀라는 개념이 사용됩니다.

PHP 구현

코드 복사 코드는 다음과 같습니다.

/*
퀵 정렬
*/

quickSort($array) 기능
{
If(!isset($array[1]))
          $배열 반환;
$mid = $array[0]; //분할 키워드를 가져옵니다. 일반적으로 첫 번째 요소입니다.
$leftArray = 배열()
$rightArray = 배열();

foreach($array를 $v로)
{
If($v > $mid)
               $rightArray[] = $v; //$mid보다 큰 숫자를 배열에 넣습니다.
           if($v < $mid)
              $leftArray[] = $v; //$mid보다 작은 숫자를 다른 배열에 넣습니다
}

$leftArray = QuickSort($leftArray); //더 작은 배열을 다시 분할합니다
$leftArray[] = $mid; //소형 배열의 끝에 분할된 요소를 추가합니다.

$rightArray =quickSort($rightArray); //더 큰 배열을 다시 분할
Return array_merge($leftArray,$rightArray); //두 결과 결합
}

버블 알고리즘과 비교

이제 이전에 작성한 버블 알고리즘으로 구현된 정렬을 비교해 보면 이 알고리즘이 버블 알고리즘보다 훨씬 효율적이라는 것을 알 수 있습니다.

코드 복사 코드는 다음과 같습니다.

$a = array_rand(range(1,3000), 1500); //버블 알고리즘이 1600개 요소를 초과하는 경우에도 메모리가 부족하다는 메시지가 표시되지만 여기서는 둘 사이의 차이를 측정하기 위해 설정하면 됩니다. 1500, 버블 알고리즘도 실행될 수 있음을 보장합니다.
shuffle($a); //섞인 배열을 가져옵니다
$t1 = 마이크로타임(true);
QuickSort($a); //빠른 정렬
$t2 = 마이크로타임(true);
echo (($t2-$t1)*1000).'ms
';

require('./maopao.php'); //여기에 인용된 내용은 이전에 작성한 버블 알고리즘 정렬입니다
$t1 = 마이크로타임(true);
마오파오($a) //거품
$t2 = 마이크로타임(true);
echo (($t2-$t1)*1000).'ms';

실행 결과:

코드 복사 코드는 다음과 같습니다.

12.10880279541ms
772.64094352722ms