Algorithm and data structure
algorithm
The algorithm is the core of the program. The quality of the algorithm directly determines the quality of the program
Several basic algorithms
Binary search
Bubble sorting
Insert sort
Sort selection
Quick sort
Binary search
Assuming that the data is sorted in ascending order, for the given value x, the comparison starts from the middle position of the sequence. If the current position value is equal to x, the search is successful; If x is less than the current position value, search in the first half of the sequence; If x is greater than the current position value, continue to search in the second half of the sequence until it is found. (used when there is a large amount of data)
//Binary search
function bin_search($arr,$low,$high,$k)
{
if($low <= $high)
{
$mid = intval(($low + $high)/2);
if($arr[$mid] == $k)
{
return $mid;
}
else if($k < $arr[$mid])
{
return bin_search($arr,$low,$mid-1,$k);
}
else
{
return bin_search($arr,$mid+1,$high,$k);
}
}
return -1;
}
$arr = array(1,2,3,4,5,6,7,8,9,10);
print(bin_search($arr,0,9,3));
Bubble sorting
Bubble Sort is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares the two elements in turn, and exchanges them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need to exchange, that is, the sequence has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the sequence through exchange.
Steps:
1. Compare adjacent elements. If the first one is bigger than the second, exchange them.
2. Do the same work for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the largest number.
3. Repeat the above steps for all elements except the last one.
4. Continue to repeat the above steps for fewer and fewer elements each time until there is no pair of numbers to compare.
$arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//Bubble sorting
function bubbleSort($arr) {
$len = count($arr);
//This layer circulates to control the number of rounds that need to bubble
for ($i = 1; $i < $len; $i++) {
//This layer loop is used to control the number of times a number needs to be compared in each round
for ($k = 0; $k < $len - $i; $k++) {
if ($arr[$k] > $arr[$k + 1]) { //From small to large < | from large to small >
$tmp = $arr[$k + 1]; // Declare a temporary variable
$arr[$k + 1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}
$arr = bubbleSort($arr);
print_r($arr);
Sort selection
Selection sort is a simple and intuitive sorting algorithm.
1. First, find the smallest element in the unordered sequence and store it at the beginning of the sorted sequence,
2. Then, continue to find the smallest element from the remaining unordered elements,
3. Then put it at the end of the sorting sequence.
4. Wait until all elements are sorted.
$arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//Sort selection
//Realize the idea of double cycle completion, the outer layer controls the number of rounds, and the current minimum value. Internal control comparison times
function selectSort($arr) {
$len = count($arr);
//The position of the current minimum value of $i, and the elements to be compared
for ($i = 0; $i < $len - 1; $i++) {
//First assume the location of the minimum value
$p = $i;
//Which elements do $j need to compare with at present? The elements after $i.
for ($j = $i + 1; $j < $len; $j++) {
//$arr[$p] is the currently known minimum
//Compare and find smaller ones, and record the position of the minimum value; And in the next comparison, the known minimum value should be used for comparison.
$p = ($arr[$p] <= $arr[$j]) ? $p : $j;
}
//The location of the current minimum value has been determined and saved to $p.
//If the location of the minimum value is found to be different from the currently assumed location $i, the location can be interchanged
if ($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//Return the final result
return $arr;
}
$arr = selectSort($arr);
print_r($arr);
Insert sort
The algorithm description of Insertion Sort is a simple and intuitive sorting algorithm.
Its working principle is to build an ordered sequence, scan the unordered data from back to front in the sorted sequence, find the corresponding position and insert it. In the implementation of insertion sort, in place sort is usually adopted (that is, the sort that only needs the additional space of O(1)). Therefore, in the process of scanning from back to front, the sorted elements need to be moved back step by step to provide insertion space for the latest elements.
Steps:
1. Starting from the first element, the element can be considered to have been sorted
2. Take out the next element and scan from back to front in the sorted element sequence
3. If the element (sorted) is larger than the new element, move the element to the next position
4. Repeat step 3 until you find the position where the sorted element is less than or equal to the new element
5. Insert the new element into this location
6. Repeat step 2
$arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//Insert sort
function insert_sort($arr)
{
$len=count($arr);
for($i=1; $i<$len; $i++) {
//Get the element value that needs to be compared currently
$tmp = $arr[$i];
//Inner loop control comparison and insertion
for($j=$i-1; $j>=0; $j--) {
//$arr[$i]; Elements to be inserted
//$arr[$j]; Elements to compare
if($tmp < $arr[$j]) //From small to large < | from large to small >
{
//It is found that the inserted element should be small and the position should be exchanged
//Swap the back element with the front element
$arr[$j+1] = $arr[$j];
//Set the previous number to the current number to be exchanged
$arr[$j] = $tmp;
} else {
//If you encounter an element that does not need to be moved
//Because it is an array that has been sorted, the previous ones do not need to be compared again.
break;
}
}
}
//Insert this element into the sorted sequence.
//return
return $arr;
}
$arr = insert_sort($arr);
print_r($arr);
Quick sort
Quick sort is a sort algorithm developed by Tony hall.
On average, n items need to be sorted Ο (n log n) comparisons. In the worst case, you need Ο (n2) times, but this situation is not common.
In fact, quick sort is usually significantly better than others Ο (n log n) algorithm is faster because its inner loop can be implemented efficiently in most architectures, and in most real-world data, it can determine the design choice and reduce the possibility of the quadratic term of the required time.
Steps:
1. Pick out an element from the sequence, which is called "pivot",
2. Reorder the sequence. All elements smaller than the benchmark value are placed in front of the benchmark, and all elements larger than the benchmark value are placed behind the benchmark (the same number can be on either side). After the partition exits, the benchmark is in the middle of the sequence. This is called a partition operation.
3. Recursively sort the subsequence that is less than the reference value element and the subsequence that is greater than the reference value element.
<?php
$arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//Quick sort
function quick_sort($arr)
{
//Determine whether the parameter is an array
if(!is_array($arr)) return false;
//Recursive exit: when the length of the array is 1, the array is returned directly
$length = count($arr);
if($length<=1) return $arr;
//If there are multiple array elements, define two empty arrays
$left = $right = array();
//Use the for loop to traverse and treat the first element as the object of comparison
for($i=1; $i<$length; $i++)
{
//Determine the size of the current element
if($arr[$i] < $arr[0]){ //From small to large < | from large to small >
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//Recursive call
$left=quick_sort($left);
$right=quick_sort($right);
//Merge all results
return array_merge($left,array($arr[0]),$right);
}
$arr = quick_sort($arr);
print_r($arr);
Merge sort
Using recursion, first split, then merge, and then sort.
Steps:
The average score is divided into two subsequences
Repeat the previous step recursively until the subsequence has only one element
The parent sequence merges two sub sequences and sorts them, and recursively returns the sequence
data structure
SPL refers to SPL - Standard PHP Library.
Bidirectional linked list
A double linked list (DLL) is a list of nodes linked in two directions. When the underlying structure is DLL, the operation of iterator, the access to both ends, and the addition or deletion of nodes all have O (1) overhead. Therefore, it provides a suitable implementation for stack and queue.
SplDoublyLinkedList
SplStack
SplQueue
heap
Heap is a tree structure that follows the attributes of heap: each node is greater than or equal to its children, and the implemented comparison method for the global heap is used for comparison.
SplHeap
SplMaxHeap
SplMinHeap
SplPriorityQueue
array
An array is a structure that stores data in a continuous manner and can be accessed through an index. Don't confuse them with php arrays: php arrays are actually implemented as ordered lists.
SplFixedArray
mapping
A map is a data that has key value pairs. PHP arrays can be seen as mappings from integers / strings to values. SPL provides mapping from object to data. This mapping can also be used as an object set.
SplObjectStorage