PHP 빠 른 정렬 알고리즘 구현 원리 및 코드 상세 설명

알고리즘 원리
다음 동 도 는 5 분 동안 알고리즘 을 배 워 서 빠 른 정렬 알고리즘 의 원리 와 절 차 를 보 여 줍 니 다.

단계:
배열 에서 기준 치 를 선택 하 십시오.
배열 에서 기준 치 보다 큰 것 을 같은 쪽 에 놓 고 기준 치 보다 작은 것 을 다른 쪽 에 놓 으 며 기준 치 는 중간 위치 에 있 습 니 다.
재 귀적 으로 양쪽 의 배열 을 정렬 하 다.
코드 구현

function quickSort($arr)

{

 $len = count($arr);

 if ($len <= 1) {

  return $arr;

 }

 

 $v = $arr[0];

 $low = $up = array();

 for ($i = 1; $i < $len; ++$i) {

  if ($arr[$i] > $v) {

   $up[] = $arr[$i];

  } else {

   $low[] = $arr[$i];

  }

 }

 $low = quickSort($low);

 $up = quickSort($up);

 

 return array_merge($low, array($v), $up);

}

테스트 코드:

$startTime = microtime(1);

 

$arr = range(1, 10);

shuffle($arr);

 

echo "before sort: ", implode(', ', $arr), "
";

$sortArr = quickSort($arr);

echo "after sort: ", implode(', ', $sortArr), "
";

 

echo "use time: ", microtime(1) - $startTime, "s
";

테스트 결과:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8

after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

use time: 0.0009009838104248s

시간 복잡 도
빠 른 정렬 의 시간 복잡 도 는 최 악의 경우 O(N2),평균 시간 복잡 도 는 O(N*lgN)다.
이 말 은 이해 하기 쉽다.정렬 된 수열 에 N 개의 수가 있다 고 가정 하 자.한 번 옮 겨 다 니 는 시간의 복잡 도 는 O(N)입 니 다.몇 번 옮 겨 다 녀 야 합 니까?최소 lg(N+1)회,최대 N 회.
1)왜 최소한 lg(N+1)회 인가?빠 른 정렬 은 분 치 법 으로 옮 겨 다 니 는 것 입 니 다.우 리 는 이 진 트 리 로 간주 합 니 다.옮 겨 다 니 는 횟수 는 이 진 트 리 의 깊이 입 니 다.완전 이 진 트 리 의 정의 에 따라 그 깊이 는 적어도 lg(N+1)입 니 다.따라서 빠 른 정렬 횟수 는 lg(N+1)회 가 가장 적다.
2)왜 최대 N 번 인가?이것 은 매우 간단 해 야 합 니까?아니면 빠 른 정렬 을 이 진 트 리 로 보 는 것 입 니까?그 깊이 가 가장 큰 것 은 N 입 니 다.따라서 빨리 읽 고 정렬 하 는 횟수 는 최대 N 회 다.