PHP에서 빠른 정렬 알고리즘의 최적화 전략과 구현 방법은 무엇입니까?-PHP 튜토리얼-php.cn

PHP에서 빠른 정렬 알고리즘의 최적화 전략과 구현 방법은 무엇입니까?

王林

풀어 주다： 2023-09-19 11:16:01

원래의

932명이 탐색했습니다.

PHP에서 빠른 정렬 알고리즘의 최적화 전략과 구현 방법은 무엇입니까?

PHP의 빠른 정렬 알고리즘의 최적화 전략과 구현 방법은 무엇입니까?

빠른 정렬은 일반적인 정렬 알고리즘의 기본 개념은 요소를 벤치마크 값으로 선택하고 배열을 두 부분으로 나누는 것입니다. 한 부분은 벤치마크 값보다 작고, 다른 부분은 벤치마크 값보다 큽니다. 그런 다음 전체 배열이 정렬될 때까지 두 부분을 개별적으로 신속하게 정렬합니다. 퀵 정렬을 구현할 때 최적화 전략을 통해 알고리즘의 성능을 향상시킬 수 있습니다.

아래에서는 여러 가지 최적화 전략과 구현 방법을 소개하고 구체적인 PHP 코드 예제를 제공합니다.

벤치마크 값을 무작위로 선택
퀵 정렬에서는 벤치마크 값의 선택이 알고리즘 성능에 큰 영향을 미칩니다. 매번 첫 번째 또는 마지막 요소를 기준 값으로 선택하면 배열 자체가 정렬되거나 대략적으로 정렬되면 알고리즘의 시간 복잡도는 O(n^2)에 도달합니다. 이러한 상황을 피하기 위해 요소를 기준 값으로 무작위로 선택하여 최악의 시나리오가 발생할 확률을 줄일 수 있습니다.

샘플 코드:

function partition($arr, $low, $high) {
    $pivot_index = rand($low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

로그인 후 복사

세 숫자의 중간을 찾는 방법
벤치마크 값을 선택할 때 배열의 최소값 또는 최대값을 선택하지 않으면 알고리즘 성능을 향상시킬 수 있습니다. 기준값을 취하는 일반적인 방법은 "세 숫자 방법"을 사용하는 것입니다. 즉, 배열의 시작, 중간, 끝에서 세 개의 요소를 선택한 다음 중간 값을 기준값으로 취하는 것입니다.

샘플 코드:

function getPivotIndex($arr, $low, $high) {
    $mid = intval(($low + $high) / 2);
    
    if ($arr[$low] < $arr[$mid]) {
        if ($arr[$mid] < $arr[$high]) {
            return $mid;
        } else if ($arr[$high] < $arr[$low]) {
            return $low;
        } else {
            return $high;
        }
    } else {
        if ($arr[$low] < $arr[$high]) {
            return $low;
        } else if ($arr[$mid] < $arr[$high]) {
            return $high;
        } else {
            return $mid;
        }
    }
}

function partition($arr, $low, $high) {
    $pivot_index = getPivotIndex($arr, $low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

로그인 후 복사

벤치마크 값을 무작위로 선택하고 세 숫자의 중간을 취하는 등의 최적화 전략을 채택함으로써 퀵 정렬 알고리즘의 성능을 향상시키고 최악의 시나리오가 발생할 확률을 줄일 수 있습니다. 이러한 최적화 전략은 대규모 데이터 세트를 정렬하는 경우 알고리즘 효율성을 향상시키는 데 특히 중요합니다.

위 내용은 PHP에서 빠른 정렬 알고리즘의 최적화 전략과 구현 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!