preface

With the rapid development of front-end, front-end business development has put forward higher requirements for front-end engineers, so algorithm questions are appearing more and more frequently in front-end interviews. There are a lot of friends to find Hu Ge bitter complaints, in the front-end actual development (in addition to involving game development), algorithm use is a lot? Is the interview of the big factory intended to flaunt itself? In fact, the assessment algorithm is quite necessary, come on, let Brother Hu give you the reason to save the world, oh, no, is the assessment algorithm reason.

Why algorithms?

  1. Algorithm is a general skill, including a lot of logic and related technical points, excellent algorithm scheme will reflect excellent logical thinking and problem solving ability.
  2. Solid algorithms help us get better solutions to complex problems.

Algorithm implementation based on different languages have different forms, for JavaScript, algorithm implementation also has many different ways, this article is based on the latest JS ES6 syntax to achieve, you can appreciate the charm of the algorithm at the same time to master the GRAMMAR of ES6.

First, bubble algorithm

Bubbling algorithm, known for its meaning, uses a principle similar to water bubbles growing from the bottom up (if this principle is not clear, consult your physics teacher pressure problem, see if the teacher will hit you shi…). To sort the array.

collation

  1. Each time through the loop, the size of the current position item is compared to the next position item, and if the current item > the latter, the positions of the two are swapped. At the end of each loop comparison, a maximum value can be selected, and the remaining comparison items to be filtered are reduced by one.
  2. If the array has n entries, the filter needs to loop n times

Second, bubble algorithm code implementation

function bubbleSort ([...arr]) {
  for (leti = 0; i < arr.length; I ++) {// the JTH term is compared with the j+1 term, so the maximum value of j is = the maximum length - 1 - minus the number of rounds I that have been filteredfor (let j = 0; j < arr.length - 1 - i; j++) {
      if(arr [j] > arr [j + 1]) {/ / the exchange of array element position [arr [j + 1], arr [j]] = [arr [j], arr [m + 1]]}}}return arr
}

letArr = [4, 3, 2, 1letSortArr = bubbleSort(arr) console.log(sortArr) // [1, 2, 3, 4]Copy the code

ES6 syntax structure

  1. Function definition parameter: […arr] 
    Destruct the assignment and extension operators to receive elements of the original array without affecting the original arrayCopy the code
  2. [ARr [j]], ARr [j]] = [ARr [j], arr[j + 1]] expression 
    Using array deconstruction assignment, swap two positions [a, b] = [b, a] without resorting to a third variable to swap valuesCopy the code

Bubbling algorithm optimization

What is the worst case that the average time complexity of bubble sorting is O(n^2)? The array passed is completely in reverse order, that is, [4, 3, 2, 1]. But what if the array [1, 2, 3, 4] is passed in full positive order? If you continue this way, performance is wasted at execution time, so how do you optimize?

Optimization scheme

If the array is completely sequential, then no array elements are swapped during a loop comparison, so we set a flag, which is initialized to true, and false if there is a swap. After a loop, if the flag is true, there is no swap and the order is complete, and the outer loop can be stopped by break. Let’s look at the code implementation.

function bubbleSort ([...arr]) {
  for (leti = 0; i < arr.length; I++) {// sets the flag to indicate whether there are swap place elements in the current round of filtering. The default istrueIf there is a switch set tofalse
    let flag = true// compare j with j+1, so the maximum value of j is the maximum length - 1 - minus the number of rounds I that have been filteredfor (let j = 0; j < arr.length - 1 - i; j++) {
      if(arr [j] > arr [j + 1]) {/ / the exchange of array element position [arr [j + 1], arr [j]] = [arr [j], arr [m + 1]] / / swap places, set is markedfalse
        flag = false}} // If the current round did not swap places, the sorting is completeif (flag) {
      break}}return arr
}

letArr = [1, 2, 3, 4letSortArr = bubbleSort(arr) console.log(sortArr) // [1, 2, 3, 4]Copy the code

At this point, when the sorting is done, only one loop is executed, and the time at this point is order n.

Afterword.

The above is Brother Hu to share the content today, like partners remember to like, collect yo, pay attention to Brother Hu has words, learning front end don’t get lost, welcome a lot of message exchange…

Brother Hu has words, a technology, feelings of brother Hu! The current jingdong front – end siege lion. Hu Ge has words, focus on the field of front-end technology, share front-end system architecture, framework implementation principle, the latest and most efficient technology practice!