빠른 정렬을 위한 PHP

세 가지 php 빠른 배열 예시를 작성했습니다.
첫 번째는 효율이 낮지만 가장 쉽고 쉽다풀다
두 번째는 알고리즘의 도론에서 제공하는 단방향이다한 번에 중간값 찾는 방법,
세 번째는 쌍방향으로 돌아다니면서 중간값의 경전을 빨리 찾는 것이다계산법.
세 그룹의 알고리즘 구현과 비교는 다음과 같다.

방법 1: 이 방법은 비교적 직관적이지만 손상된다대량의 공간을 잃는 대가로, 효율이 비교적 높다.낮은 merge 함수.세 가지 방법 중 효율이 가장 낮다.최악의 경우 알고리즘이 (O(n*n))

function quick_sort($array) {
    if(count($array) <= 1) {
	    return $array;
    }
    $key = $array[0];
    $rightArray = array();
    $leftArray = array();
    for($i = 1; $i < count($array); $i++) {
        if($array[$i] >= $key) {
            $rightArray[] = $array[$i];
        } else {
            $leftArray[] = $array[$i];
        }
    }
    $leftArray = quick_sort($leftArray);
    $rightArray = quick_sort($rightArray);
    return array_merge($leftArray, array($key), $rightArray);
}

방법 2: 이 알고리즘은 Nico Lomuto 메서드(관심 있는 Google에 자세히 설명되어 있음)라고 불리는 알고리즘의 도론에서 나온 것으로, 가장 고전적인 한 방향의 한 번에 한 번 탐색하여 중간값을 찾는다.
그러나 이러한 알고리즘은 최악의 경우(예를 들어 값이 같은 배열의 경우, n-1번의 분할이 필요하며, 각각의 분할에 O(n)의 시간이 소요되며, 원소 하나를 제거하는 데) 최악의 경우 O(n*n)이다

function quick_sort(&$array, $start, $end) {
    if ($start >= $end) return;
    $mid = $start;
    for ($i = $start + 1; $i <= $end; $i++) {
        if ($array[$i] < $array[$mid]) {
           $mid++;
           $tmp = $array[$i];
           $array[$i] = $array[$mid];
           $array[$mid] = $tmp;
        }
    }
    $tmp = $array[$start];
    $array[$start] = $array[$mid];
    $array[$mid] = $tmp;
    quick_sort($array, $start, $mid - 1);
    quick_sort($array, $mid + 1, $end);
}

방법 3: 이 방법은 기본적으로 교과서적인 일반적인 방식으로, 먼저 왼쪽에서 오른쪽으로 중간 요소보다 작은 스킵을 통과하고, 동시에 오른쪽에서 왼쪽으로 큰 요소 스킵을 통과하고, 교차하지 않으면 양쪽 값을 교환하고, 중간 지점을 찾을 때까지 순환합니다.
이 방법은 같은 원소를 다룰 때도 교환하는 것으로 최악의 경우 O(nlogn) 효율이 있다는 점에 유의한다.다음 함수에서 $array[$right] > $key를 $array[]로 바꾸면$right] > =$key 또는 $array[$left] < $key를 $array[$left] < = $key로 바꾸면 최악의 경우 O(n*n)로 전락할 뿐만 아니라, 매번 비교되는 소모 외에 n번의 상호작용에 대한 추가 오버헤드가 발생할 수 있다.이 문제에는 또 다른 두 개의 시험 지점이 있는데, 억지로 외우는 학우를 대상으로 한다.

1. 중간에 있는 두 개의 while이 호환되는지 여부.물론 호환이 되지 않습니다. 왜냐하면 빠른 디스크에 대해 초기 왼쪽 값을 저장할 추가 공간이 필요하기 때문입니다. 이렇게 하면 왼쪽과 오른쪽이 바뀌면 오른쪽을 덮어쓰게 됩니다.
중간값의 왼쪽값입니다. 그렇지 않으면 문제가 발생할 수 있습니다.$array[$left] = $array[$right] 이 문장을 보세요;
2.$array[$right] = $key; 이 문장의 뜻은 생략해도 되는지 여부.이 문장은 생략할 수 없으며, 예를 들어 두 값의 순서(5,2)와 같은 극단적인 경우를 고려하여 점진적으로 보면 알 수 있다

function quick_sort_swap(&$array, $start, $end) {
    if($end <= $start) {
        return;
    }
    $key = $array[$start];
    $left = $start;
    $right = $end;
    while($left < $right) {
        while($left < $right && $array[$right] > $key){
            $right--;
        }
        $array[$left] = $array[$right];
        while($left < $right && $array[$left] < $key){
            $left++;
        }
        $array[$right] = $array[$left];
    }
    $array[$right] = $key;
    quick_sort_swap($array, $start, $right - 1);
    quick_sort_swap($array, $right+1, $end);
}

방법 3원문의 코드 실행이 잘못되었으므로 필자는 다시 한 부를 고쳐 쓴다

function quickSort(&$arr,$start,$end){
    if($start > $end){
        return;
    }
    $key = $arr[$start];
    $left = $start;
    $right = $end;
    while($left<$right){
        while($left<$right && $arr[$right]>=$key){
            $right--;
        }
        while($left<$right && $arr[$left]<=$key){
            $left++;
        }
        if($left<$right){
            $tmp = $arr[$left];
            $arr[$left] = $arr[$right];
            $arr[$right] = $tmp;
        }
    }
    $arr[$start] = $arr[$left];
    $arr[$left] = $key;
    quickSort($arr,$start,$right-1);
    quickSort($arr,$right+1,$end);
}