JS and PHP Code Writing Eight Sorting Algorithms
- 2021-07-02 23:26:55
- OfStack
From the beginning of learning data structure, I have been exposed to various algorithm foundations, but I have never practiced them since I finished the exam. When I was developing, I used it and looked it up. Now I am learning JavaScript. Take advantage of this time to sort out various basic algorithms once again, and write codes in the way of JS and PHP syntax respectively.
1. Bubble sort
Principle: Compare adjacent numbers in pairs, and exchange them in order from small to large or from large to small, so that after one trip, the largest or smallest numbers are exchanged to the last 1 digit, and then compare and exchange them from the beginning until the end of the penultimate 2 digits
Time complexity: Average: O (n2) Best case: O (n) Worst case: O (n2)
Spatial complexity: O (1)
Stability: Stability
//JavaScript Grammar
var array = [23,0,32,45,56,75,43,0,34];
for(var i = 0; i < array.length; i++)
{
var isSort = true;
for(var j = 0; j < array.length - 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;
}
}
console.log(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. Sort by simple selection
Principle: Through the comparison between n-i keywords, the record with the smallest keyword is selected from n-i+1 records, and the record with the first i (1
<
=i
<
= n) A simple selection sort of record exchange performs slightly better than a bubble sort
Time complexity: Average: O (n2) Best case: O (n) Worst case: O (n2)
Spatial complexity: O (1)
Stability: Unstable
//JavaScript
var array = [23,0,32,45,56,75,43,0,34];
for(var i = 0; i < array.length - 1; i++)
{
var pos = i;
for(var j = i + 1; j < array.length;j++)
{
if(array[j] < array[pos])
{
pos=j;
}
}
var temp=array[i];
array[i]=array[pos];
array[pos]=temp;
}
console.log(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. Insert Sort Directly
Principle: Insert a record into the sorted ordered table, so as to get a new ordered table with 1 increase in the number of records. That is to say, the first record of the sequence is regarded as an ordered sub-sequence, and then the second record is inserted one by one until the whole sequence is ordered. It is better than bubbling method and selective sorting. 1
Time complexity: Average: O (n2) Best case: O (n) Worst case: O (n2)
Spatial complexity: O (1)
Stability: Stability
//JavaScript
var array = [23,0,32,45,56,75,43,0,34];
for(var j = 0;j < array.length;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;
}
console.log(array);
<?php
// Direct insert 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 one sorting, in which all the data in one part are smaller than all the data in the other part, and then the two parts of data are quickly sorted according to this method, and the whole sorting process can be recursively carried out, so that the whole data becomes an orderly sequence.
Time complexity: Average: O (nlog2n) Best case: O (nlog2n) Worst case: O (n2)
Spatial complexity: O (nlog2n)
Stability: Unstable
//JavaScript Quick sort
var array = [23,0,32,45,56,75,43,0,34];
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }// Check the number of elements in the array, if it is less than or equal to 1 , return.
var pivotIndex = Math.floor(arr.length / 2);//
var pivot = arr.splice(pivotIndex,1)[0];// Select " Benchmark " ( pivot ) and detach it from the original array,
var left = [];// Define two empty arrays for storing 1 Left 1 Two subsets of the right
var right = [];
for (var i = 0; i < arr.length; i++)// Traversing an array, less than " Benchmark " Elements larger than the baseline are placed in the left subset, and elements larger than the baseline are placed in the right subset.
{
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));// By repeating this process recursively, you can get the sorted array.
};
var newArray=quickSort(array);
console.log(newArray);
<?php
$array = [23,0,32,45,56,75,43,0,34];
function quick_sort($arr) {
// Determine whether you need to continue first
$length = count($arr);
if($length <= 1) {
return $arr;
}
$base_num = $arr[0];// Select 1 Ruler Select 1 Elements
// Initialize two arrays
$left_array = array();// Smaller than the ruler
$right_array = array();// Larger than the scale
for($i=1; $i<$length; $i++) { // Traversal All elements except the ruler are placed in two arrays according to their size
if($base_num > $arr[$i]) {
// Put in the left array
$left_array[] = $arr[$i];
} else {
// Put it on the right
$right_array[] = $arr[$i];
}
}
// Then respectively Left side And The array on the right is sorted in the same way
// Call this function recursively , And record the results
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
// Merging left side Ruler Right
return array_merge($left_array, array($base_num), $right_array);
}
$newArray=quick_sort($array);
var_dump($newArray);
?>
5. Hill sort
Principle: First, the whole record sequence to be sorted is divided into several sub-sequences for direct insertion and sorting, and then all records are directly inserted and sorted in turn when the records in the whole sequence are "basically ordered". .
Time complexity: Average: O (n) Best case: O (nlog2n) Worst case: O (n2)
Spatial complexity: O (1)
Stability: Unstable
//JavaScript Hill sort
var array = [23,0,32,45,56,75,43,0,34];
var shellSort = function (arr)
{
var length=arr.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);
console.log(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. Merge and sort
Principle: Assuming that the initial sequence contains n records, it can be regarded as n ordered sub-sequences, each of which has a length of 1, and then merged in pairs to obtain (not less than the smallest integer of n/2) ordered sub-sequences with a length of 2 or 1, and then merged in pairs,... so repeated until an ordered sequence with a length of n is obtained
Time complexity: Average: O (nlog2n) Best case: O (nlog2n) Worst case: O (nlog2n)
Spatial complexity: O (1)
Stability: Stability
<?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);
?>
<?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);
?>
7. Heap sorting
Principle: Heap sorting is the method of sorting by heap. The basic idea is: Construct the sequence to be sorted into a large top heap. At this time, The maximum value of the whole sequence is the root node at the top of the heap. Remove it (in fact, swap it with the end element of the heap array, where the end element is the maximum value), and then reconstruct the remaining n-1 sequence into a heap, which will result in the second largest value of n elements. If you repeat this, you will get an ordered sequence
Time complexity: Average: O (nlog2n) Best case: O (nlog2n) Worst case: O (nlog2n)
Spatial complexity: O (1)
Stability: Unstable
<?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);
?>
<?php
// Heap sort
function heapSort(&$arr) {
# Initialize large top stack
initHeap($arr, 0, count($arr) - 1);
# Start switching head and tail nodes , And decrease each time 1 End node readjustment heap , Until the rest 1 Elements
for($end = count($arr) - 1; $end > 0; $end--) {
$temp = $arr[0];
$arr[0] = $arr[$end];
$arr[$end] = $temp;
ajustNodes($arr, 0, $end - 1);
}
}
# Initialize maximum heap , From the end 1 Start with non-leaf nodes , Finally 1 The number of non-leaf nodes is Array length /2 Rounding down
function initHeap(&$arr) {
$len = count($arr);
for($start = floor($len / 2) - 1; $start >= 0; $start--) {
ajustNodes($arr, $start, $len - 1);
}
}
# Adjustment node
#@param $arr Array to be adjusted
#@param $start Adjusted parent node coordinates
#@param $end Coordinates of end node of array to be adjusted
function ajustNodes(&$arr, $start, $end) {
$maxInx = $start;
$len = $end + 1; # Length of part to be adjusted
$leftChildInx = ($start + 1) * 2 - 1; # Left child coordinates
$rightChildInx = ($start + 1) * 2; # Right child coordinates
# If there is a left child in the part 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;
}
}
}
# Exchange parent node and maximum node
if($start != $maxInx) {
$temp = $arr[$start];
$arr[$start] = $arr[$maxInx];
$arr[$maxInx] = $temp;
# If the swapped child node has child nodes , 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 integers into different numbers according to digits, and then compare them according to each digit. Because integers can also express strings (such as names or dates) and floating-point numbers in a specific format, cardinality sorting is not only used for integers.
Time complexity: Average: O (d (r+n) Best case: O (d (n+rd) Worst case: O (d (r+n) r: Base of keywords d: Length n: Number of keywords
Spatial complexity: O (rd+n)
Stability: Stability
<?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);
?>