current position:Home>Here JS are some big meals

Here JS are some big meals

2022-04-29 20:34:38I'm Xiaozhen, not sad

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 ~~

 Happy

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

Text

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

 Toby

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

 Time complexity .png

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 ;

Schematic diagram

 Schematic diagram

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 ~)」

copyright notice
author[I'm Xiaozhen, not sad],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/04/202204292034327265.html

Random recommended