# Here JS are some big meals

2022-04-29 20:34:38

Form writing habits together ！ This is my participation 「 Nuggets day new plan · 4 Yuegengwen challenge 」 Of the 7 God , Click to see the event details .

The seventh day ！ Xi xi xi ️

# Preface

As a front-end rookie , Always have a dream of flying high and far away , therefore , Every little growth , I want to make it more meaningful , In order to yourself , And for more worthy people

Be happy to learn the great law of Technology ~~

Here it is... Here it is , He did come ~

# Text

First , We globally assume that the length of the array is n

## Introduction to algorithm complexity

Algorithms are not available in computer language , The complexity of the algorithm includes time complexity and space complexity

Time complexity refers to the time required for the algorithm to run , Space complexity refers to the storage space occupied by the algorithm

## Ten sorting algorithms

### 1. Bubble sort

#### principle

The two adjacent numbers are sorted from left to right , Put the small one on the left , Put the big one on the right , After the first cycle, the largest number will be on the far right ; Then again from the second element on the left to n-1 An element loop , Repeat the process , Sort in order , Until you get to the first element .

#### Algorithm code

function bubbleSort (list) {
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length - i; j++) {
if (list[j] > list[j + 1]) {
let temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
return list;
}
Copy code 

### 2. Selection sort

#### principle

Select the first number from the left to compare with all subsequent elements in turn , Replace with the smallest . Then select the second number from the left to compare in turn , Until the last element is sorted .

#### Algorithm code

function selectSort (list) {
for (let i = 0; i < list.length - 1; i++) {
for (let j = i + 1; j < list.length; j++) {
if (list[j] < list[i]) {
let temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
}
return list;
}
Copy code 

### 3. Insertion sort

#### principle

The first two elements compare sizes , Small on the left , Big on the right

Compare the third element with the first two , Small on the left , Big on the right

Compare the fourth element with the first three , Small on the left , Big on the right

……

Will be the first n Elements and front n-1 Compare the elements , Small on the left , Big on the right

above , Sorting complete ;

#### Algorithm code

function insertSort (list) {
for (let i = 1; i < list.length; i++) {
for (let j = i; j > 0; j--) {
if (list[j] < list[j - 1]) {
let temp = list[j];
list[j] = list[j - 1];
list[j - 1] = temp;
}
}
}
return list;
}
Copy code 

### 4. Quick sort

#### Algorithm code

var quickSort = function(arr) {

if (arr.length <= 1) { return arr; }

var pivotIndex = Math.floor(arr.length / 2);

var pivot = arr.splice(pivotIndex, 1)[0];

var left = [];

var right = [];

for (var i = 0; i < arr.length; i++){

if (arr[i] < pivot) {

left.push(arr[i]);

} else {

right.push(arr[i]);

}

}

return quickSort(left).concat([pivot], quickSort(right));

};
Copy code 

Complexity ：

n*（n-1）/2

At best, sorting can be done once

The worst-case scenario is that all array elements need to be sorted , At this time, it will degenerate into bubble sorting , Number of sorting ：n*（n-1）/2

### 5. Merge sort

#### principle

Recurse the array into separate elements for bitwise comparison , The little one is in front , The big one is behind , Insert the small alignment into the front of the array , The larger alignment continues to be compared with the new alignment element , Until this group is arranged into an ordered array from small to large , Then sort up the recursive tree in turn , Until it is merged into a new ordered array from small to large ;

#### Sort code

function mergeSort (list) {
function merge (left, right) {
let list = [];
while (left[0] && right[0]) {
if (left[0] < right[0]) {
list.push (left.shift ());
} else {
list.push (right.shift ());
}
}
list = list.concat (left).concat (right);
return list;
}
function sort (arr) {
if (arr.length === 1) {
return arr;
}
let mid = Math.floor ((arr.length + 1) / 2);
return merge (sort (arr.slice (0, mid)), sort (arr.slice (mid)));
}
return sort (list);
}
Copy code 

### 6. Sort by dichotomy

#### principle

Take the left as an ordered sequence , On the right is an unordered sequence ; Start with the second element and sort by dichotomy with the left

What is dichotomy ？

Take the midpoint on the left as the comparison value , The unordered sequence takes values from left to right to compare with the median value of the ordered sequence , By size comparison , Gradually narrow the comparison range , Finally, the value of the unordered sequence is inserted into the correct position of the ordered sequence ;

#### Algorithm code

var arr = [3,2,23,4,9,1,44,34,9];

function two(){
var len = arr.length;
var left = 0, right = 0, point = 0;   // Define three marker bits ,point It's in the middle
var nArr = [];
nArr[0] = arr[0];         // After defining an array , hold arr The first number in is assigned to nArr
for(var i=1; i<len; i++){
left = 0;
var nLen = nArr.length;
right = nLen;
for(var j=0; j<nLen; j++){
point = Math.floor((left + right)/2);   // integer
if(nArr[point] < arr[i]){
left = point + 1;          // Note that it must be added 1
}else{
right = point;
}
if(right == left){        // If right and left Equality means that the insertion position is found  , After inserting , Out of the loop
nArr.splice(left,0,arr[i]);
break;
}
}
}
console.log(nArr);
}

Copy code 

# Conclusion

Good articles in the past 「 I don't recommend , You may have missed  The best in history vscode Plug in collection  La ！！！( GA GA GA ~)」