집 > 기사 > 백엔드 개발 > PHP 빠른 정렬 원리, 구현 방법 및 예제 분석

PHP 빠른 정렬 원리, 구현 방법 및 예제 분석

墨辰丷원래의: 2018-06-02 10:00:021366검색

이 글은 주로 PHP 퀵 정렬의 원리와 구현 방법을 소개하고, PHP 퀵 정렬의 알고리즘 원리와 구체적인 구현 기법을 예제 형식으로 분석해 봤습니다. 도움이 필요한 친구가 참고할 수 있습니다

자세한 내용은 다음과 같습니다.

<?php
$n = array(&#39;13&#39;,&#39;14&#39;,&#39;55&#39;,&#39;10&#39;,&#39;54&#39;,&#39;2&#39;,&#39;79&#39;,&#39;106&#39;,&#39;89&#39;,&#39;90&#39;,&#39;22&#39;,&#39;60&#39;,&#39;111&#39;,&#39;77777&#39;,&#39;-110&#39;,&#39;-10&#39;,&#39;123&#39;);
function partition($n,$left,$right)
{
  global $n;
  $pivot = $n[$left];
  $lo=$left;
  $hi=$right+1;
  while($lo+1!=$hi) {
    if($n[$lo+1]<$pivot)
      $lo++;
    else if($n[$hi-1]>$pivot)
      $hi--;
    else{
      $t=$n[$lo+1];
      $n[$lo+1]=$n[$hi-1];
      $n[$hi-1]=$t;
      $lo++;
      $hi--;
    }
  }
  $n[$left]=$n[$lo];
  $n[$lo]=$pivot;
  return $lo;
}
function quicksort($n,$left,$right)
{
  global $n;
  $dp = 0;
  if ($left<$right) {
     $dp=partition($n,$left,$right);
     quicksort($n,$left,$dp-1);
     quicksort($n,$dp+1,$right);
  }
}
quicksort($n,0,sizeof($n)-1);
print_r($n);
?>

빠른 정렬은 위험 방지 알고리즘입니다. 버블 정렬이 개선되었습니다. 기본 아이디어는 단방향 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 나누는 것입니다. 한 부분의 모든 데이터는 다른 부분의 모든 데이터보다 작으며, 그런 다음 데이터의 두 부분을 순차적으로 정렬합니다. 빠른 정렬을 위해서는 전체 정렬 과정을 재귀적으로 수행하여 전체 데이터가 정렬된 순서가 되도록 할 수 있습니다.

정렬할 배열이 A[1]...A[N]이라고 가정하고 먼저 임의의 데이터(보통 첫 번째 데이터)를 키 데이터로 선택한 다음 그보다 작은 숫자를 모두 앞에 배치하고, All 그보다 큰 숫자가 뒤에 배치됩니다. 이 프로세스를 단일 위치 퀵 정렬이라고 합니다. 빠른 정렬 알고리즘은 다음과 같습니다.

1) 두 개의 변수 I와 J를 설정합니다. 정렬이 시작되면 I:=1, J:=N
2) 첫 번째 배열 요소를 키 데이터로 사용하고 값을 할당합니다. X; , 즉 교환;
4), I에서 뒤로 검색, 즉 앞에서 뒤로 검색(I: =I+1), X보다 큰 첫 번째 값을 찾고, 두 값을 교환
5), 단계를 반복합니다. 3, 4 단계, I=J까지;

빠른 정렬은 이 프로세스를 재귀적으로 호출하는 것입니다. 이 데이터 시퀀스를 49를 중간점으로 분할하고 각각 앞부분과 뒷부분에 대해 비슷한 퀵 정렬을 수행하여 빠른 정렬을 완료합니다. 전체 데이터 시퀀스 정렬 정렬하고 마지막으로 이 데이터 시퀀스를 순서 있는 시퀀스로 바꿉니다

요약: 위 내용은 이 문서의 전체 내용이므로 모든 사람의 학습에 도움이 되기를 바랍니다.

PHP 빠른 정렬 원리, 구현 방법 및 예제 분석

관련 기사