PHP 퀵 정렬 알고리즘 구현의 원리와 코드 소개

이 글은 PHP 퀵 정렬 알고리즘 구현의 원리와 코드 소개를 제공합니다. 필요한 친구들이 참고할 수 있기를 바랍니다.

알고리즘 원리

다음 애니메이션은 5분 학습 알고리즘에서 가져온 것으로, 퀵 정렬 알고리즘의 원리와 단계를 보여줍니다.

단계:

• 배열에서 벤치마크 값을 선택하세요.
• 벤치마크 값보다 큰 값은 같은 쪽에 두고, 벤치마크 값보다 작은 값은 반대쪽에 놓습니다. middle
• 재귀 이분법 열 양쪽의 배열 재정렬

코드 구현

function quickSort($arr)
{
    $len = count($arr);
    if ($len  $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), "\n";
$sortArr = quickSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";

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

테스트 결과:

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회입니다.

【관련 추천: PHP 비디오 튜토리얼】

위 내용은 PHP 퀵 정렬 알고리즘 구현의 원리와 코드 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!