I have been exposed to various algorithm basics since I learned the data structure, but I have never practiced it since I finished the exam. When I was developing, I also checked when I used it. Now I am learning JavaScript. I will take this time to organize various basic algorithms and write code in JS and PHP syntax respectively.
1. Bubble sorting
principle:The adjacent numbers are compared in two and exchanged in order from small to large or large to small. After a trip, the largest or smallest number is exchanged to the last digit, and then the two-way comparison and exchange are exchanged from the beginning until the second to last digit ends.
Time complexity:Average case: O(n2) Best case: O(n) Worst case: O(n2)
Space complexity:O（1）
stability:Stablize
//JavaScript syntax var array = [23,0,32,45,56,75,43,0,34];
for(var i = 0; i < ; i++)
{
var isSort = true;
for(var j = 0; j < - 1 - i; j++)
{
if(array[j] > array[j+1])
{
isSort = false;
var temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
if(isSort)
{
break;
}
}
(array);
<?php
$array = [23,0,32,45,56,75,43,0,34];
for($i = 0; $i < count($array); $i++)
{
$isSort = true;
for($j = 0; $j < count($array) - 1; $j++)
{
if($array[$j] > $array[$j+1])
{
$isSort = false;
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array[$j + 1] = $temp;
}
}
if($isSort)
{
break;
}
}
var_dump($array);
?>
2. Simple selection sorting
principle:By comparing n-i keywords, select the record with the smallest keyword from n-i+1 records and exchange it with the i (1<=i<=n)th records. The performance of simple selection sorting is slightly better than bubble sorting
Time complexity:Average case: O(n2) Best case: O(n) Worst case: O(n2)
Space complexity:O（1）
stability:Unstable
//JavaScript
var array = [23,0,32,45,56,75,43,0,34];
for(var i = 0; i < - 1; i++)
{
var pos = i;
for(var j = i + 1; j < ;j++)
{
if(array[j] < array[pos])
{
pos=j;
}
}
var temp=array[i];
array[i]=array[pos];
array[pos]=temp;
}
(array);
<?php
$array = [23,0,32,45,56,75,43,0,34];
for($i = 0; $i < count($array); $i++)
{
$pos = $i;
for($j = $i + 1;$j < count($array); $j++)
{
if($array[$j] < $array[$pos])
{
$pos = $j;
}
}
$temp = $array[$i];
$array[$i] = $array[$pos];
$array[$pos] = $temp;
}
var_dump($array);
?>
3. Directly insert sort
principle:Insert a record into the sorted ordered table to obtain a new ordered table with 1 increments of records. That is, first treat the first record of the sequence as an ordered subsequence, and then insert it one by one from the second record until the entire sequence is ordered. Better performance than bubble method and selection sorting
Time complexity:Average case: O(n2) Best case: O(n) Worst case: O(n2)
Space complexity:O（1）
stability:Stablize
//JavaScript
var array = [23,0,32,45,56,75,43,0,34];
for(var j = 0;j < ;j++) {
var key = array[j];
var i = j - 1;
while (i > -1 && array[i] > key)
{
array[i + 1] = array[i];
i = i - 1;
}
array[i + 1] = key;
}
(array);
<?php
//Insert directly to sort $array = [23,0,32,45,56,75,43,0,34];
for($i = 0; $i < count($array); $i++)
{
$key = $array[$i];
$j= $i - 1;
while($j > -1 && $array[$j] > $key)
{
$array[$j +1] = $array[$j];
$j = $j - 1;
}
$array[$j + 1] = $key;
}
var_dump($array);
?>
4. Quick sort
principle:The data to be sorted is divided into two independent parts through a sorting trip, and all the data in part is smaller than all the data in the other part. Then, the two parts of the data are quickly sorted according to this method. The entire sorting process can be performed recursively to achieve the entire data becoming an ordered sequence.
Time complexity:Average case: O(nlog2n) Best case: O(nlog2n) Worst case: O(n2)
Space complexity:O（nlog2n）
stability:Unstable
//JavaScript Quick Sorting
var array = [23,0,32,45,56,75,43,0,34];
var quickSort = function(arr) {
if ( <= 1) { return arr; }//Check the number of elements in the array, if it is less than or equal to 1, it will be returned. var pivotIndex = ( / 2);//
var pivot = (pivotIndex,1)[0];//Select "pivot" and separate it from the original array. var left = [];//Define two empty arrays to store two subsets of one left and one right var right = [];
for (var i = 0; i < ; i++)//Transf the array, put elements smaller than the "base" into the subset on the left, and elements larger than the base are placed in the subset on the right. {
if (arr[i] < pivot) {
(arr[i]);
} else {
(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));//Repeat this process continuously using recursion to get the sorted array. };
var newArray=quickSort(array);
(newArray);
<?php
$array = [23,0,32,45,56,75,43,0,34];
function quick_sort($arr) {
//First determine whether it is necessary to continue $length = count($arr);
if($length <= 1) {
return $arr;
}
$base_num = $arr[0];//Select a ruler Select the first element
//Initialize two arrays $left_array = array();//Lower than the ruler $right_array = array();//Greater than the ruler for($i=1; $i<$length; $i++) { //Transaction All elements except the ruler are placed in two arrays according to the size relationship. if($base_num > $arr[$i]) {
//Put into the left array $left_array[] = $arr[$i];
} else {
//Put it to the right $right_array[] = $arr[$i];
}
}
//Then the same sorting method is performed on the arrays on the left and right respectively //Recursively call this function and record the result $left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
//Merge left ruler right return array_merge($left_array, array($base_num), $right_array);
}
$newArray=quick_sort($array);
var_dump($newArray);
?>
5. Hill sort
principle:First, divide the entire record sequence to be sorted into several sub-sequences for direct insertion and sorting. When the records in the entire sequence are "basically ordered", then insert and sort the entire records in sequence. .
Time complexity:Average situation: O(n√n) Best situation: O(nlog2n) Worst situation: O(n2)
Space complexity:O（1）
stability:Unstable
//JavaScript Hill sorting var array = [23,0,32,45,56,75,43,0,34];
var shellSort = function (arr)
{
var length=;
var h=1;
while(h<length/3)
{
h=3*h+1;//Set interval }
while(h>=1)
{
for(var i=h; i<length; i++)
{
for(var j=i; j>=h && arr[j]<arr[j-h]; j-=h)
{
var temp =arr[j-h];
arr[j-h]=arr[j];
arr[j]=temp;
}
}
h=(h-1)/3;
}
return arr;
}
var newArray = shellSort(array);
(newArray);
<?php
//Hill sort $array = [23,0,32,45,56,75,43,0,34];
function shellSort($arr)
{
$length=count($arr);
$h=1;
while($h<$length/3)
{
$h=3*$h+1;//Set interval }
while($h>=1)
{
for($i=$h; $i<$length; $i++)
{
for($j=$i; $j>=$h && $arr[$j]<$arr[$j-$h]; $j-=$h)
{
$temp =$arr[$j-$h];
$arr[$j-$h]=$arr[$j];
$arr[$j]=$temp;
}
}
$h=($h-1)/3;
}
return $arr;
}
$newArray = shellSort($array);
var_dump($newArray)
?>
6. Ordering
principle:Assuming that the initial sequence contains n records, it can be regarded as n ordered subsequences, each subsequence has a length of 1, and then merged in pairs to obtain (the smallest integer not less than n/2) ordered subsequences with lengths of 2 or 1, and merged in pairs... Repeat this way until an ordered sequence with length n is obtained.
Time complexity:Average situation: O(nlog2n) Best situation: O(nlog2n) Worst situation: O(nlog2n)
Space complexity:O（1）
stability:Stablize
//JavaScript merge sorting function isArray1(arr){
if((arr) =='[object Array]'){
return true;
}else{
return false;
}
}
function merge(left,right){
var result=[];
if(!isArray1(left)){
left = [left];
}
if(!isArray1(right)){
right = [right];
}
while( > 0&& >0){
if(left[0]<right[0]){
(());
}else{
(());
}
}
return (left).concat(right);
}
function mergeSort(arr){
var len=;
var lim ,work=[];
var i,j,k;
if(len ==1){
return arr;
}
for(i=0;i<len;i++){
(arr[i]);
}
([]);
for(lim=len;lim>1;){//lim is the group length for(j=0,k=0;k<lim;j++,k=k+2){
work[j]=merge(work[k],work[k+1]);
}
work[j]=[];
lim=((lim+1)/2);
}
return work[0];
}
var array = [23,0,32,45,56,75,43,0,34];
(mergeSort(array));
<?php
//Group sort function mergeSort(&$arr) {
$len = count($arr);//Finding the array length
mSort($arr, 0, $len-1);
}
//The actual implementation of merge sorting program function mSort(&$arr, $left, $right) {
if($left < $right) {
//Indicate that there is an extra element in the sub-sequence, then it needs to be split, sorted separately, and merged. //Calculate the position of the split, length/2 to complete $center = floor(($left+$right) / 2);
//The recursive call sorts the left side again: mSort($arr, $left, $center);
//Recursive call sorts the right side again mSort($arr, $center+1, $right);
//Merge sorting results mergeArray($arr, $left, $center, $right);
}
}
//Combine two ordered numbers into an ordered array function mergeArray(&$arr, $left, $center, $right) {
//Set two start position marks $a_i = $left;
$b_i = $center+1;
while($a_i<=$center && $b_i<=$right) {
//When neither array A nor array B crosses the boundary if($arr[$a_i] < $arr[$b_i]) {
$temp[] = $arr[$a_i++];
} else {
$temp[] = $arr[$b_i++];
}
}
//Judge whether all the elements in array A are used up. If not, insert all of them into array C: while($a_i <= $center) {
$temp[] = $arr[$a_i++];
}
//Judge whether all the elements in array B are used up. If not, insert all of them into array C: while($b_i <= $right) {
$temp[] = $arr[$b_i++];
}
//Write the sorted part in $arrC into $arr: for($i=0, $len=count($temp); $i<$len; $i++) {
$arr[$left+$i] = $temp[$i];
}
}
$arr = array(23,0,32,45,56,75,43,0,34);
mergeSort($arr);
var_dump($arr);
?>
7. Heap sorting
principle:Heap sorting is a method of sorting using the heap. The basic idea is to construct the sequence to be sorted into a large top heap. At this time, the maximum value of the entire sequence is the root node of the top of the heap. Remove it (in fact, it is to exchange it with the end element of the heap array, and the end element is the maximum value), and then reconstruct the remaining n-1 sequences into a heap, so that the submaximum value of n elements will be obtained. This will result in a repeated execution and an ordered sequence.
Time complexity:Average situation: O(nlog2n) Best situation: O(nlog2n) Worst situation: O(nlog2n)
Space complexity:O（1）
stability:Unstable
//JavaScript heap sorting var array = [23,0,32,45,56,75,43,0,34];
function heapSort(array)
{
for (var i = ( / 2); i >= 0; i--)
{
heapAdjust(array, i, - 1); //Build the array array into a large top heap }
for (i = - 1; i >= 0; i--)
{
/*Swap the root node out*/
var temp = array[i];
array[i] = array[0];
array[0] = temp;
/*The remaining array continues to be built into a large top heap*/
heapAdjust(array, 0, i - 1);
}
return array;
}
function heapAdjust(array, start, max)
{
var temp = array[start];//temp is the value of the root node for (var j = 2 * start; j < max; j *= 2)
{
if (j < max && array[j] < array[j + 1])
{ //Get the subscript of older children ++j;
}
if (temp >= array[j])
break;
array[start] = array[j];
start = j;
}
array[start] = temp;
}
var newArray = heapSort(array);
(newArray);
<?php
//Heap sort function heapSort(&$arr) {
#Initialize the big top heap initHeap($arr, 0, count($arr) - 1);
#Start swap the head and tail nodes, and reduce one end node at a time and adjust the heap until one element is left for($end = count($arr) - 1; $end > 0; $end--) {
$temp = $arr[0];
$arr[0] = $arr[$end];
$arr[$end] = $temp;
ajustNodes($arr, 0, $end - 1);
}
}
#Initialize the maximum heap, start from the last non-leaf node, and the last non-leaf node number is array length/2 round down function initHeap(&$arr) {
$len = count($arr);
for($start = floor($len / 2) - 1; $start >= 0; $start--) {
ajustNodes($arr, $start, $len - 1);
}
}
#Adjust nodes #@param $arr Array to be adjusted #@param $start Adjusted parent node coordinates #@param $end The coordinates of the end node to be adjusted function ajustNodes(&$arr, $start, $end) {
$maxInx = $start;
$len = $end + 1; #The length of the part to be adjusted $leftChildInx = ($start + 1) * 2 - 1; #Left child coordinate $rightChildInx = ($start + 1) * 2; #Right child coordinates
#If there is a left child to be adjusted if($leftChildInx + 1 <= $len) {
#Get the minimum node coordinates if($arr[$maxInx] < $arr[$leftChildInx]) {
$maxInx = $leftChildInx;
}
#If the part to be adjusted has a right child node if($rightChildInx + 1 <= $len) {
if($arr[$maxInx] < $arr[$rightChildInx]) {
$maxInx = $rightChildInx;
}
}
}
#Swap parent node and maximum node if($start != $maxInx) {
$temp = $arr[$start];
$arr[$start] = $arr[$maxInx];
$arr[$maxInx] = $temp;
#If there are still children after the exchange, continue to adjust if(($maxInx + 1) * 2 <= $len) {
ajustNodes($arr, $maxInx, $end);
}
}
}
$arr = array(23,0,32,45,56,75,43,0,34);
heapSort($arr);
var_dump($arr);
?>
8. Cardinality sorting
principle:Cut the integer into different numbers by digits and compare them separately by each digit. Since integers can also express strings (such as names or dates) and floating-point numbers in specific formats, radix sorting is not only used for integers.
Time complexity:Average situation: O(d(r+n)) Best situation: O(d(n+rd)) Worst situation: O(d(r+n)) r: The cardinality of keywords d: length n: the number of keywords
Space complexity:O（rd+n）
stability:Stablize
<?php
#Black sorting, here only positive integers are sorted. As for negative numbers and floating point numbers, complement codes are needed. You are interested in researching them yourself.
#Count sort #@param $arr Array to be sorted #@param $digit_num sorts according to the number of digits function counting_sort(&$arr, $digit_num = false) {
if ($digit_num !== false) { #If the parameter $digit_num is not empty, sort according to the number of $digit_num bits of the element for ($i = 0; $i < count($arr); $i++) {
$arr_temp[$i] = get_specific_digit($arr[$i], $digit_num);
}
} else {
$arr_temp = $arr;
}
$max = max($arr);
$time_arr = array(); #Storage array of elements occurrences
#Initialize the occurrence number array for ($i = 0; $i <= $max; $i++) {
$time_arr[$i] = 0;
}
#Count the number of occurrences of each element for ($i = 0; $i < count($arr_temp); $i++) {
$time_arr[$arr_temp[$i]]++;
}
#Count the number of occurrences of each element smaller or equal elements than it for ($i = 0; $i < count($time_arr) - 1; $i++) {
$time_arr[$i + 1] += $time_arr[$i];
}
#Sort the array using the number of occurrences for($i = count($arr) - 1; $i >= 0; $i--) {
$sorted_arr[$time_arr[$arr_temp[$i]] - 1] = $arr[$i];
$time_arr[$arr_temp[$i]]--;
}
$arr = $sorted_arr;
ksort($arr); #Ignore the efficiency loss of key sorting this time }
#Calculate the number of bits of a certain number function get_digit($number) {
$i = 1;
while ($number >= pow(10, $i)) {
$i++;
}
return $i;
}
#Get the i-th digit of a number from a single digit function get_specific_digit($num, $i) {
if ($num < pow(10, $i - 1)) {
return 0;
}
return floor($num % pow(10, $i) / pow(10, $i - 1));
}
#Black sorting, count sorting as the sub-sorting process function radix_sort(&$arr) {
#First find the largest number of bits in the array $max = max($arr);
$max_digit = get_digit($max);
for ($i = 1; $i <= $max_digit; $i++) {
counting_sort($arr, $i);
}
}
$arr = array(23,0,32,45,56,75,43,0,34);
radix_sort($arr);
var_dump($arr);
?>
The above is all the content of this article. I hope it will be helpful to everyone's study and I hope everyone will support me more.