How to use algorithms in PHP programming?

With the continuous development of computer technology, the role of algorithms in programming is not only increasingly important, but also attracts more and more attention from programmers. In PHP programming, using algorithms can help us complete tasks faster and more efficiently. This article will explore how to use algorithms in PHP programming.

1. Introduction to Algorithms

Algorithm is a method of solving problems. It is a series of orderly operation steps used to solve a certain problem or complete a certain task. In programming, algorithms can help us solve problems faster and more efficiently.

In PHP programming, commonly used algorithms include sorting algorithms, search algorithms, string matching algorithms, etc.

2. Sorting algorithm

The sorting algorithm is an algorithm that sorts a set of data according to certain rules. Commonly used sorting algorithms include bubble sort, insertion sort, selection sort, quick sort and merge sort.

1. Bubble sort

Bubble sort is a simple sorting algorithm. Its principle is to repeatedly traverse the array and compare two adjacent elements each time. If their If the order does not conform to the prescribed order, they are exchanged.

Sample code:

function bubbleSort($arr){
    $len = count($arr);
    for($i=0;$i<$len;$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 sorting algorithm that inserts unsorted data into a sorted data sequence. Its principle is to start from the first element and insert subsequent elements into the sorted data sequence.

Sample code:

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

3. Selection sort

Selection sort is a simple sorting algorithm. Its principle is to select a minimum value from unsorted data. , and then put it into the sorted data sequence.

Sample code:

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

4. Quick sort

Quick sort is an efficient sorting algorithm. Its principle is to divide large data into Move to the right, small data moves to the left, and finally the data is divided into two parts.

Sample code:

function quickSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $pivot = $arr[0];
    $left = $right = array();
    for($i=1;$i<$len;$i++){
        if($arr[$i] < $pivot){
            $left[] = $arr[$i];
        }else{
            $right[] = $arr[$i];
        }
    }
    $left = quickSort($left);
    $right = quickSort($right);
    return array_merge($left,array($pivot),$right);
}

5. Merge sort

Merge sort is a sorting algorithm that draws on the idea of ​​"divide and conquer". Its core is to divide the data into two The parts are sorted separately, and finally the two ordered arrays are combined into one ordered array.

Sample code:

function mergeSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $mid = intval($len/2);
    $left = array_slice($arr,0,$mid);
    $right = array_slice($arr,$mid);
    $left = mergeSort($left);
    $right = mergeSort($right);
    $mergeArr = array();
    while(count($left) && count($right)){
        $mergeArr[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
    }
    return array_merge($mergeArr,$left,$right);
}

3. Search algorithm

The search algorithm is an algorithm for finding a specific element in a set of data. Commonly used search algorithms include sequential search, binary search, hash search, etc.

1. Sequential search

Sequential search is a simple search algorithm. Its principle is to search from the first element of the array until the target element or the end of the array is found.

Sample code:

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

2. Binary search

Binary search is an efficient search algorithm. Its principle is to divide the array into two parts. If the target element is in If the target element is in the second half, continue to search the first half; if the target element is in the second half, continue to search the second half.

Sample code:

function binarySearch($arr,$target){
    $len = count($arr);
    $left = 0;
    $right = $len - 1;
    while($left <= $right){
        $mid = intval(($left+$right)/2);
        if($arr[$mid] == $target){
            return $mid;
        }elseif($arr[$mid] > $target){
            $right = $mid - 1;
        }else{
            $left = $mid + 1;
        }
    }
    return -1;
}

4. String matching algorithm

The string matching algorithm is an algorithm for finding another substring in a long string. Commonly used string matching algorithms include brute force matching algorithm, KMP algorithm, Boyer-Moore algorithm, etc.

1. Brute force matching algorithm

The brute force matching algorithm is a simple string matching algorithm. Its principle is to start from each character in the main string and match the pattern string character by character. match.

Sample code:

function bruteForce($str,$subStr){
    $len1 = strlen($str);
    $len2 = strlen($subStr);
    for($i=0;$i<=$len1-$len2;$i++){
        for($j=0;$j<$len2;$j++){
            if($str[$i+$j] != $subStr[$j]){
                break;
            }
        }
        if($j == $len2){
            return $i;
        }
    }
    return -1;
}

2.KMP algorithm

KMP algorithm is an efficient string matching algorithm. Its principle is to use known information to minimize the number of matches. . The core of the KMP algorithm is to build a prefix table for character matching.

Sample code:

function KMP($str,$subStr){
    $next = getNext($subStr);
    $i = $j = 0;
    $len1 = strlen($str);
    $len2 = strlen($subStr);
    while($i<$len1 && $j<$len2){
        if($j == -1 || $str[$i] = $subStr[$j]){
            $i++;
            $j++;
        }else{
            $j = $next[$j];
        }
    }
    if($j == $len2){
        return $i - $j;
    }else{
        return -1;
    }
}

function getNext($subStr){
    $len = strlen($subStr);
    $next[0] = -1;
    $i = 0;
    $j = -1;
    while($i<$len-1){
        if($j == -1 || $subStr[$i] == $subStr[$j]){
            $i++;
            $j++;
            $next[$i] = $j;
        }else{
            $j = $next[$j];
        }
    }
    return $next;
}

The above is an introduction to using algorithms in PHP programming. In actual programming, choosing the appropriate algorithm according to different situations can effectively improve the efficiency of the program. At the same time, we also need to continue to learn and master more algorithms to cope with more complex programming.

The above is the detailed content of How to use algorithms in PHP programming?. For more information, please follow other related articles on the PHP Chinese website!