PHP에서 빠른 정렬을 구현하는 방법

PHP에서 빠른 정렬을 구현하는 방법: 먼저 PHP 샘플 파일을 만든 다음 교환 함수와 기본 함수를 만든 다음 하위 하위 테이블과 상위 하위 테이블을 재귀적으로 정렬하고 마지막으로 QuickSort 알고리즘을 호출합니다.

추천: "PHP 비디오 튜토리얼"

기본 아이디어:

Quicksort는 버블 정렬을 개선한 것입니다. 그의 기본 아이디어는 정렬할 레코드를 한 번의 정렬을 통해 두 개의 독립적인 부분으로 나누는 것입니다. 그러면 레코드의 두 부분이 빠르게 개별적으로 정렬될 수 있습니다. 전체 정렬 프로세스는 전체 시퀀스를 정렬하는 목적을 달성하기 위해 재귀적으로 수행될 수 있습니다.

기본 알고리즘 단계:

예:

지금 정렬할 레코드가 다음과 같다고 가정합니다.

6   2   7   3   8   9

첫 번째 단계는 레코드의 첫 번째 레코드를 가리키는 $low 변수를 만들고, $high는 다음을 가리키는 변수를 만드는 것입니다. 마지막 레코드인 $pivot는 정렬할 레코드의 첫 번째 요소(반드시 첫 번째 요소일 필요는 없음)에 대한 피벗으로 지정됩니다. 여기서는 다음과 같습니다.

$low = 0;
$high = 5;
$pivot = 6;

두 번째 단계에서는 $pivot보다 작은 모든 숫자를 $pivot의 왼쪽에 있으므로 $high에서 시작하여 오른쪽에서 왼쪽으로 찾고 변수 $high의 값을 지속적으로 감소시키면서 6보다 작은 숫자를 찾을 수 있습니다. 6보다 크므로 데이터 3을 첨자 0의 위치($low가 가리키는 위치)로 이동하여 첨자 0의 데이터 6을 첨자 3으로 이동하고 첫 번째 비교를 완료합니다.

3   2   7   6   8   9

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

세 번째 단계, 두 번째 비교를 시작합니다. 이번에는 $pivot보다 큰 것을 찾아야 하고, 앞에서 뒤로 찾아야 합니다. 변수 $low를 증가시키고 아래 첨자 2의 데이터가 $pivot보다 큰 첫 번째 데이터임을 확인하므로 아래 첨자 2($low가 가리키는 위치)에 데이터 7을 사용하고 아래 첨자 3($low가 가리키는 위치)에 데이터 7을 사용합니다. at by $high) 6개의 데이터가 교환되고 데이터 상태는 다음 표와 같습니다.

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

두 번째 및 세 번째 단계를 완료하는 것을 사이클 완료라고 합니다.

네 번째 단계(즉, 다음 주기 시작)는 두 번째 단계의 과정을 모방합니다.
다섯 번째 단계는 세 번째 단계의 과정을 따라하는 것입니다.

두 번째 루프를 실행한 후 데이터 상태는 다음과 같습니다.

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

이 단계에서 $low 및 $high "만남"을 발견합니다. 둘 다 아래 첨자 2를 가리킵니다. 이로써 첫 번째 비교가 끝났습니다. 결과는 다음과 같습니다. $pivot(=6) 왼쪽에 있는 모든 숫자는 그보다 작고, $pivot 오른쪽에 있는 모든 숫자는 그보다 큽니다.

그런 다음 데이터 {3, 2} 및 {7, 8, 9}를 $pivot 양쪽에 그룹화하고 더 이상 그룹화가 불가능할 때까지 위의 프로세스를 각각 수행합니다.

참고: 빠른 정렬의 첫 번째 단계는 최종 결과를 직접 얻지 않으며 k보다 크고 k보다 작은 숫자만 k의 양쪽으로 나눕니다. 최종 결과를 얻으려면 첨자 2의 양쪽에 있는 배열에 대해 이 단계를 다시 수행한 다음 배열이 더 이상 분해될 수 없을 때까지(단 하나의 데이터만) 배열을 분해하여 올바른 결과를 얻어야 합니다.

알고리즘 구현:

//交换函数
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

//主函数：
function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

주 함수에서 빠른 정렬의 첫 번째 단계는 전체 배열을 정렬하므로 시작점은 $low=0,$high=count($arr)-1입니다.
그러면 QSort() 함수는 재귀 호출 프로세스이므로 캡슐화됩니다.

function QSort(array &$arr,$low,$high){
    //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);	//对低子表（$pivot左边的记录）进行递归排序
        QSort($arr,$pivot + 1,$high);	//对高子表（$pivot右边的记录）进行递归排序
    }
}

위의 QSort() 함수에서 Partition() 함수가 전체 코드의 핵심이라는 것을 알 수 있습니다. 예: 키워드 중 하나를 선택합니다. 예를 들어 첫 번째 키워드를 선택합니다. 그런 다음 왼쪽의 값이 그것보다 작고 오른쪽의 값이 그것보다 커지도록 특정 위치에 배치하려고 최선을 다합니다. 이러한 키워드를 피벗(Pivot)이라고 부릅니다.

코드로 바로 이동:

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端

        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

전체 결합 코드는 다음과 같습니다.

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

알고리즘 호출:

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

복잡도 분석:

최적의 상황, 즉 숫자 축을 선택한 경우 전체 배열의 중간 값에 있으면 배열은 매번 두 부분으로 나뉩니다. 따라서 최적의 경우 시간 복잡도는 O(nlogn)입니다(힙 정렬 및 병합 정렬과 동일).

최악의 경우 정렬할 순서가 정방향 또는 역순인 경우 피벗 선택 시 에지 데이터만 선택할 수 있습니다. 각 분할은 이전 분할보다 하나의 레코드가 줄어들고 다른 분할은 , 이러한 상황의 최종 시간 복잡도는 O(n^2)입니다.

최상의 경우와 최악의 경우를 기준으로 하면 평균 시간 복잡도는 O(nlogn)입니다.

퀵 정렬은 불안정한 정렬 방법입니다.

퀵 정렬은 상대적으로 발전된 정렬이며 20세기 10대 알고리즘 중 하나로 꼽히기 때문입니다. . . . 이렇게 멋진 알고리즘이 있는데 왜 우리는 그것으로부터 배우면 안 될까요?

이 알고리즘은 이미 매우 훌륭하지만 위의 알고리즘 프로그램에는 아직 개선할 부분이 있습니다.

위 내용은 PHP에서 빠른 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!