Array sorting and search algorithm in PHP

PHP is a very popular programming language that supports various data types and algorithms, of which array sorting and search algorithms are basic and important parts. This article will introduce commonly used array sorting and search algorithms in PHP, as well as their application scenarios and efficiency analysis.

1. Array sorting

PHP provides a variety of array sorting methods, including bubble sort, insertion sort, selection sort, quick sort, merge sort, etc. The following is an introduction and sample code for several commonly used algorithms:

1. Bubble Sort

Bubble sort is a simple but inefficient The basic idea of ​​the sorting algorithm is to start from the first element of the array and compare the sizes of adjacent elements in sequence. If the left element is larger than the right element, their positions are swapped. After this round of comparison, the largest element is moved to the end of the array. Then start from the first element and repeat the above operation, the time complexity is O(n^2).

Sample code:

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. Insertion Sort

Insertion sort is a relatively simple sorting algorithm. Its basic idea is to A data to be sorted is inserted into an already sorted sequence to achieve the purpose of sorting. Assuming that the previous elements have been sorted, start from the second element of the array and look forward to find a suitable position for the insertion operation. Similar to bubble sort, its time complexity is also O(n^2).

Sample code:

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 is a commonly used efficient sorting algorithm. Its basic idea is to select Any element in the array is used as the base value, and then the remaining elements are divided into two subsequences: the numbers on the left are all smaller than the base value, and the numbers on the right are all greater than the base value. Then repeat the above steps for the left and right subsequences until the length of the subsequence is 1 or 0. The time complexity of quick sort is O(n log2 n), and it is unstable sort.

Sample code:

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. Array search

The array search algorithms in PHP mainly include linear search, binary search and hash search. The following is an introduction and sample code for several commonly used algorithms:

1. Linear Search

Linear search is a simple search algorithm. The basic idea is to start from the first element of the array and compare the values ​​and keywords of the elements one by one to see if they are the same. If they exist, return the subscript of the element, otherwise -1 will be returned. The time complexity of linear search is O(n).

Sample code:

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

2. Binary Search

Binary search is also called half search. The basic idea is to divide the ordered array into The two parts compare the size of the middle element and the keyword each time. If they are equal, the subscript of the element is returned. Otherwise, the search range is reduced by half according to the size relationship until the target element is found. The time complexity of binary search is O(log2 n).

Sample code:

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. Hash Search

Hash search is an efficient search algorithm that uses hash tables. The basic idea is to map the key of each element into a hash table, calculate its location through a hash function, and then find the required element in that location. The time complexity of hash search is O(1), but a hash table needs to be constructed and maintained.

The above is an introduction and sample code for array sorting and search algorithms commonly used in PHP. Choosing different algorithms according to actual application scenarios and data size can improve the efficiency of the code.

The above is the detailed content of Array sorting and search algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!