PHP의 배열 정렬 및 검색 알고리즘

PHP는 다양한 데이터 유형과 알고리즘을 지원하는 매우 인기 있는 프로그래밍 언어이며, 그 중 배열 정렬 및 검색 알고리즘이 기본적이고 중요한 부분입니다. 이 기사에서는 PHP에서 일반적으로 사용되는 배열 정렬 및 검색 알고리즘과 해당 애플리케이션 시나리오 및 효율성 분석을 소개합니다.

1. 배열 정렬

PHP는 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬 등 다양한 배열 정렬 방법을 제공합니다. 다음은 일반적으로 사용되는 여러 알고리즘에 대한 소개 및 샘플 코드입니다.

1. 버블 정렬

버블 정렬은 간단하지만 비효율적인 정렬 알고리즘의 기본 개념은 배열의 첫 번째 순서부터 시작하는 것입니다. , 인접한 요소의 크기가 순서대로 비교됩니다. 왼쪽 요소가 오른쪽 요소보다 크면 위치가 바뀝니다. 이 비교 라운드 후에 가장 큰 요소가 배열의 끝으로 이동됩니다. 그런 다음 첫 번째 요소부터 시작하여 위 작업을 반복하면 시간 복잡도는 O(n^2)입니다.

샘플 코드:

function bubble_sort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

2. 삽입 정렬

삽입 정렬은 정렬 목적을 달성하기 위해 이미 정렬된 시퀀스에 정렬할 데이터를 삽입하는 것입니다. 이전 요소가 정렬되었다고 가정하고 배열의 두 번째 요소부터 시작하여 삽입 작업에 적합한 위치를 찾습니다. 버블 정렬과 마찬가지로 시간 복잡도도 O(n^2)입니다.

샘플 코드:

function insertion_sort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $temp = $arr[$i];
        for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$j + 1] = $temp;
    }
    return $arr;
}

3. Quick Sort

Quick Sort는 일반적으로 사용되는 효율적인 정렬 알고리즘입니다. 기본 아이디어는 배열의 모든 요소를 ​​기본 값으로 선택한 다음 나머지 요소를 두 개로 나누는 것입니다. 하위 수열: 왼쪽의 숫자는 모두 기준값보다 작고 오른쪽의 숫자는 모두 기준값보다 큽니다. 그런 다음 하위 시퀀스의 길이가 1 또는 0이 될 때까지 왼쪽 및 오른쪽 하위 시퀀스에 대해 위 단계를 반복합니다. 퀵 정렬은 시간복잡도가 O(n log2 n)로 불안정 정렬이다.

샘플 코드:

function quick_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $pivot_key = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] <= $pivot_key) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($pivot_key), $right_arr);
}

2. 배열 검색

PHP의 배열 검색 알고리즘에는 주로 선형 검색, 이진 검색 및 해시 검색이 포함됩니다. 다음은 일반적으로 사용되는 여러 알고리즘에 대한 소개 및 샘플 코드입니다.

1. 선형 검색

선형 검색은 배열의 첫 번째 요소부터 시작하여 값을 비교하는 것입니다. 요소의 키워드를 하나씩 확인하여 동일한지 확인합니다. 존재하는 경우 요소의 첨자를 반환하고, 그렇지 않으면 -1을 반환합니다. 선형탐색의 시간복잡도는 O(n)이다.

샘플 코드:

function linear_search($arr, $key) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        if ($arr[$i] == $key) {
            return $i;
        }
    }
    return -1;
}

2. 이진 검색

이진 검색은 정렬된 배열을 두 부분으로 나누고, 중간 요소와 키워드의 크기를 매번 비교하는 것입니다. 같음 그런 다음 요소의 첨자를 반환합니다. 그렇지 않으면 대상 요소를 찾을 때까지 크기 관계에 따라 검색 범위가 절반으로 줄어듭니다. 이진 검색의 시간 복잡도는 O(log2n)입니다.

샘플 코드:

function binary_search($arr, $key) {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($arr[$mid] == $key) {
            return $mid;
        } elseif ($arr[$mid] > $key) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

3. 해시 검색

해시 검색은 해시 테이블을 활용하는 효율적인 검색 알고리즘입니다. 기본 아이디어는 각 요소의 키를 해시 테이블에 매핑하고 해시 함수를 통해 위치를 계산한 다음 해당 위치에서 필요한 요소를 찾는 것입니다. 해시 검색의 시간 복잡도는 O(1)이지만 해시 테이블을 구축하고 유지 관리해야 합니다.

위는 PHP에서 일반적으로 사용되는 배열 정렬 및 검색 알고리즘에 대한 소개 및 샘플 코드입니다. 실제 응용 프로그램 시나리오 및 데이터 크기에 따라 다른 알고리즘을 선택하면 코드의 효율성을 높일 수 있습니다.

위 내용은 PHP의 배열 정렬 및 검색 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!