This article summarizes common PHP sorting algorithms, which has good reference value when designing algorithms. Now share it with everyone for reference. The details are as follows:
1. Insertion sort
Use text to describe simply, for example, $arr = array(4,2,4,6,3,6,1,7,9); Sort a group of numbers like this:
So, first, compare the second element of the array with the first element. If the first element is greater than the second element, then swap the positions of the two. Next, take the third element of the array and compare it with the first element. Two, the first element is compared, if the third element is smaller, then swap. And so on. This is insertion sort, and its time frequency is: 1+2+...+(n-1)=(n^2)/2. Then its time complexity is O(n^2).
php implementation code is as follows:
<?php
function insertSort($arr){
$count = count($arr);
if($count<2){
return $arr;
}
for($i=1;$i<$count;$i++){
$tmp = $arr[$i];
$j=$i-1;
while(j>=0&&$arr[$j]<$arr[$i]){
$arr[$i] = $arr[$j];
$arr[$j] = $tmp;
$j--;
}
}
return $arr;
}
?>
2. Selection sort
If the selection sorting is described in language, it can be like this, such as: $arr = array(4,3,5,2,1);
First, compare the first one with all the following ones, find the smallest number, and then exchange it with the first array (of course, if it is the first one that is the smallest, then there is no need to exchange it), and then loop , that is: compare the second number with the following number, find the smallest number, and then exchange it with the second number, and so on, that is to say, find the smallest remaining value each time. It can be obtained: the first time, the time frequency is n, (the first one is compared with the following n-1, find the smallest one, and then check whether it is the first one, if not, exchange it) in the future , followed by minus one. Its time complexity is also O(n^2);
php implementation code is as follows:
<?php
function selectSort($arr){
$count = count($arr);
if($count<2){
return $arr;
}
for($i=0;$i<$count;$i++){
$min=$i;
for(j=$i+1;$j<$count;$j++){
if($arr[$min]>$arr[$j]){
$min = $j; //找到最小的那个元素的下标
}
}
if($min!=$i){//如果下标不是$i 则互换。
$tmp= $arr[$i];
$arr[$i] = $arr[$min];
$arr[$min] = $tmp;
}
}
return $arr;
}
?>
3. Bubble sorting
There is actually no significant difference between bubble sort and selection sort. Find the smallest one and put it on the far left. Solve the problems in sequence. The difference is that bubble sorting swaps positions more times, while selection sorting finds the subscript of the smallest element, and then directly swaps positions with the leftmost element.
The php implementation code is as follows:
<?php
function selectSort($arr){
$count = count($arr);
if($count<2){
return $arr;
}
for($i=0;$i<$count;$i++){
for(j=$i+1;$j<$count;$j++){
if($arr[$i]>$arr[$j]){
$tmp= $arr[$i];
$arr[$i] = $arr[$i];
$arr[$i] = $tmp;
}
}
}
return $arr;
}
?>
4. Quick sort
Quick sort, to describe it in language, selects a value $a from the array, and then compares it with the other elements. The one larger than $a is placed in the array right, and vice versa, it is placed in the array left. Then recursively call left and right respectively, that is, subdivide left and right, and finally merge the arrays.
php quick sorting:
<?php
function mySort($arr){
$count = count($arr);
if($count<2){
return $arr;
}
$key = $arr[0];//选择第一个元素作为比较元素，可选其他
$left = array();
$right = array();
for($i=1;$i<$count;$i++){
if($key>=$arr[$i]){
$left[] = $arr[$i];
}else{
$right[] = $arr[$i];
}
}
$left = mySort($left);
$right = mySort($right);
$result = array_merge($left,$right);
return $result;
}
?>
5. Merge sort
In fact, merge sort is an idea of splitting and merging. It has something in common with the idea of quick sort, one pile on the left, one pile on the right, and then merged. Sorting is achieved through recursion. What's the difference? The difference between them is also an essential difference in thinking. The splitting of quick sort selects specific values for size comparison, thus dividing them into left and right. That is, the small pile is placed on the left, and the large pile is placed on the right. Then, the small left is subdivided into left1 and right1. . . . Sorting is done by doing a similar recursion. In other words, if you keep subdividing it, left1 at the end of the recursion is the minimum value.
Merge sorting is to recursively divide the arrays from the left and right geometrically into the minimum granularity of 2 or 1, and then start to compare the sizes and then merge. The comparison size here is: the son's left element is compared with the son's right element, and then sorted and merged into the father's left or right. Here, until the last two arrays are sorted and merged respectively: the initial left and right, only their respective orders cannot be confirmed, and the order of the entire array cannot be confirmed. The merger still needs to be completed through the final comparison of left and right. Sorting in the truest sense.
<?php
function gbSort($arr){
if(count($arr)<=1){return $arr;}
$min = floor(count($arr)/2);//取中间数字进行拆分
$left = array_slice($arr,0,$min);
$right = array_slice($arr,$min);
$left = gbSort($left); //递归
$right = gbSort($right);
return get_merge($left,$right);//调用排序合并函数进行合并
}
function get_merge($left,$right){
while(count($left) && count($right)){
$m[] = $left[0]>$right[0] ? array_shift($right) : array_shift($left);
//进行比较，小的移除，并且放入到数组$m中。
}
return arr_merge($m,$left,$right);//进行合并（由于不知道left right 哪个会为空，所以进行统一合并）
}
?>
6. Heap sort
In this example, the fixDown function implements downward adjustment of a certain node. The default here is that the starting node is 1, which is convenient for calculating the relationship between parent and child nodes
Note:
The parent-child relationship with the starting node being 1: parent node k, child nodes are 2K, 2k+1 child node j, parent node is floor(j/2) floor is rounded down
The parent-child relationship with the starting node being 0: parent node k, child nodes are 2K+1, 2k+2 child node j, parent node is floor((j-1)/2)
The parameter $k is the adjustment point position, $lenth is the length of the array, which is the coordinates from 1 to the last node.
<?php
function fixDown(&$arr, $k, $lenth)
{
while(2*$k<=$lenth) { //只要当前节点有子节点， 就需要继续该循环
$j = $k*2;
if ($j<$lenth && $arr[$j]<$arr[$j+1]) $j++; // 只要子节点有右节点，且右节点比左节点大，那么切换到右节点操作。
if ($arr[$j] < $arr[$k]) break; // 如果子节点都没有父节点大， 那么调整结束。
exch($arr[$j], $arr[$k]);
$k = $j;
}
}
function exch(&$a, &$b) {
$tmp = $a; $a = $b; $b = $tmp;
}
function headSort(&$arr)
{
$len = count($arr);
array_unshift($arr, NULL);
for($i=$len/2;$i>=1;$i--) {
fixDown($arr, $i, $len);
}
while($len>1) {
exch($arr[1], $arr[$len]);
fixDown($arr, 1, --$len);
}
array_shift($arr);
}
$arr = array(4,6,4,9,2,3);
headSort($arr);
?>
I hope the examples of sorting algorithms described in this article will be helpful to everyone’s PHP programming.
Various sorting implemented in Java language, including insertion sort, bubble sort, selection sort, Shell sort, quick sort, merge sort, heap sort, SortUtil, etc.
Insertion sort: package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;/*** @author treeroot
* @since 2006-2-2
* @version 1.0*/public class InsertSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) */public void sort(int[] data) {int temp;for(int i=1;i
import org.rut.util.algorithm.SortUtil;/*** @author treeroot
* @since 2006-2-2
* @version 1.0*/public class BubbleSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])*/public void sort(int[] data) {int temp;for( int i=0;i
Sorting algorithm The so-called sorting is the operation of arranging a string of records in increasing or decreasing order according to the size of one or some keywords in it.
Classification
Sorting algorithms used in computer science are usually classified as:
Computational complexity (worst, average, and best performance), according to the size of the list (n) . Generally speaking, good performance is O. (n log n), and the bad behavior is Ω(n2). The ideal performance for a sort is O(n). Sorting algorithms that use only one abstract key comparison always require at least Ω(n log n) on average.
Memory usage (and other computer resource usage)
Stability: A stable sorting algorithm maintains the relative order of records according to equal keys (in other words, values). That is to say, a sorting algorithm is stable, that is, when there are two records R and S with equal keys, and R appears before S in the original sequence, R will also be before S in the sorted sequence. Before.
General methods: insert, swap, select, merge, etc. Exchange sort includes bubble sort and quicksort. Selection sort includes shaker sort and heap sort.
When equal elements are indistinguishable, such as integers, stability is not an issue. However, assume that the following pairs of numbers are to be sorted by their first digit.
(4, 1) (3, 1) (3, 7) (5, 6)
In this case, it is possible to produce two different results. One is to maintain relative results based on equal key values. order, while the other one does not:
(3, 1) (3, 7) (4, 1) (5, 6) (maintain order)
(3, 7) (3, 1) (4 , 1) (5, 6) (Order changed)
Unstable sorting algorithms may change the relative order of records within equal key values, but stable sorting algorithms never do this. Unstable sorting algorithms can specifically be considered stable. One way to do this is to manually extend the key comparison, so that a comparison between two objects with otherwise identical keys is determined to use the entry in the original data order as a tiebreaker. However, keep in mind that this order usually involves additional space overhead.
List of sorting algorithms
In this table, n is the number of records to be sorted and k is the number of distinct key values.
Stable
Bubble sort — O(n2)
Cocktail sort (bidirectional bubble sort) — O(n2)
Insertion sort — O(n2)
Bucket sort — O(n); Requires O(k) additional memory
Counting sort — O(n+k); Requires O(n+k ) Extra memory
Merge sort — O(n log n); Requires O(n) extra memory
In-place merge sort — O(n2)
Binary tree sort ) — O(n log n); requires O(n) additional memory
Pigeonhole sort — O(n+k); requires O(k) additional memory
radix sort sort) — O(n·k); requires O(n) additional memory
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, requires (1+ε) n extra memory
unstable
selection sort — O(n2)
shell sort — O(n log n) if using the best current version
Comb sort — O(n log n)
Heapsort — O(n log n)
...The rest of the text>>
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
