PHP는 인내 정렬 알고리즘을 구현합니다.

인내 정렬은 카드 게임 인내에서 영감을 받아 이름을 딴 정렬 알고리즘입니다. 이 알고리즘의 변형은 주어진 배열에서 가장 긴 증가 부분 수열의 길이를 효율적으로 계산합니다.

이 알고리즘의 이름은 인내심 카드 게임의 단순화된 버전에서 유래되었습니다. 게임은 섞인 카드 덱으로 시작됩니다. 카드는 다음 규칙에 따라 테이블 위에 차례대로 쌓입니다.

처음에는 "힙"이 없습니다. 처리된 첫 번째 카드는 개별 카드로 구성된 새 카드를 구성합니다.

각 후속 카드는 기존 "더미"의 맨 왼쪽에 배치되며 맨 위 카드의 값은 새 카드의 값보다 크거나 모든 기존 "더미"의 오른쪽에 배치됩니다. 새로운 "더미".

배분할 카드가 더 이상 남지 않으면 게임이 종료됩니다.

이 글은 이 카드 게임을 아래와 같이 2단계 정렬 알고리즘으로 변환합니다. 완벽하게 정렬된 도메인의 n개 요소 배열이 주어지면 배열을 카드 모음으로 생각하고 인내 정렬 게임을 시뮬레이션합니다. 게임이 끝나면 정렬된 순서는 가장 작은 가시 카드를 반복적으로 제거하여 복원됩니다. 즉, 각각 내부적으로 정렬된 p-힙의 p-way 병합을 수행합니다.

인내 정렬 알고리즘을 구현한 PHP의 코드 예는 다음과 같습니다.

<?php
class PilesHeap extends SplMinHeap {
    public function compare($pile1, $pile2) {
        return parent::compare($pile1->top(), $pile2->top());
    }
}
function patience_sort($n) {
    $piles = array();
    //排序成堆
    foreach ($n as $x) {
        //二进位检索
        $low = 0; $high = count($piles)-1;
        while ($low <= $high) {
            $mid = (int)(($low + $high) / 2);
            if ($piles[$mid]->top() >= $x)
                $high = $mid - 1;
            else
                $low = $mid + 1;
        }
        $i = $low;
        if ($i == count($piles))
            $piles[] = new SplStack();
        $piles[$i]->push($x);
    }
    // 优先队列允许我们有效地合并堆
    $heap = new PilesHeap();
    foreach ($piles as $pile)
        $heap->insert($pile);
    for ($c = 0; $c < count($n); $c++) {
        $smallPile = $heap->extract();
        $n[$c] = $smallPile->pop();
        if (!$smallPile->isEmpty())
            $heap->insert($smallPile);
    }
    assert($heap->isEmpty());
}
$a = array(100, 54, 7, 2, 5, 4, 1);
patience_sort($a);
print_r($a);

출력:

Array 
( 
[0] => 100 
[1] => 54 
[2] => 7 
[3] => 2 
[4] => 5 
[5] => 4 
[6] => 1 
)

이 문서는 인내 정렬 알고리즘을 간단하고 이해하기 쉽게 소개합니다. 도움이 필요한 친구에게 도움이 됩니다!

위 내용은 PHP는 인내 정렬 알고리즘을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!