빠른 정렬을 위한 PHP 코드 예제

이 글의 내용은 PHP에서 빠른 정렬을 구현하기 위한 코드 예제입니다. 필요한 친구들이 참고할 수 있기를 바랍니다.

Quick sort

파티션 교환 정렬(partition-exchange sort)로도 알려진 퀵 정렬(영어: Quicksort)은 퀵 정렬이라고도 불리는 것은 Tony Hall이 처음 제안한 정렬 알고리즘입니다. 평균적으로 n개 항목을 정렬하려면 O(n log n) 비교가 필요합니다. 최악의 경우에는 O(n2) 비교가 필요하지만 이는 일반적이지 않습니다. 실제로 퀵 정렬 O(n log n)은 내부 루프가 대부분의 아키텍처에서 효율적으로 달성될 수 있기 때문에 다른 알고리즘보다 훨씬 빠른 경우가 많습니다.

단계는 다음과 같습니다.

시퀀스에서 "피벗"이라는 요소를 선택합니다.

시퀀스를 재정렬합니다. 피벗 값보다 작은 모든 요소는 피벗 앞에 배치되고, 피벗보다 큰 모든 요소는 피벗 값은 피벗 요소 앞에 배치되고 베이스 뒤에 배치됩니다(양쪽에 같은 숫자가 올 수 있음). 이 분할 후 데이텀은 시퀀스의 중간에 있습니다. 이를 파티션 작업이라고 합니다.

기본 값보다 작은 요소의 하위 배열과 기본 값보다 큰 요소의 하위 배열을 재귀적으로 정렬합니다.

재귀가 맨 아래에 도달하면 배열의 크기가 0 또는 1이 되어 정렬이 완료되었음을 의미합니다. 이 알고리즘은 각 반복마다 적어도 하나의 요소를 최종 위치로 이동하므로 확실히 종료됩니다.

위키피디아 소개. 핵심 아이디어는 recursion을 사용하는 것입니다. 아래 애니메이션은 매우 생생합니다.

애니메이션 데모

예

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function quickSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $leftArray = $rightArray = array();
    $middle = $arr[0];// 基准值

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i] < $middle) {
            $leftArray[] = $arr[$i];
        } else {
            $rightArray[] = $arr[$i];
        }
    }

    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);

    return array_merge($leftArray, array($middle), $rightArray);
    // 倒序
    // return array_merge($rightArray, array($middle), $leftArray);
}

print_r(quickSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33

위 내용은 빠른 정렬을 위한 PHP 코드 예제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!