preface

Although the front-end interview will rarely test algorithm topics, but you will know when you go to the big factory interview, the master of the basic algorithm for computer science and technology for us, or essential, spend 10 minutes every day to understand the basic algorithm concepts and front-end implementation.

In addition, master some basic algorithm implementation, for our daily development, is also like a tiger added wings, can let our JS business logic more efficient and smooth.

Algorithm is introduced

Bubble sort is a simple process in which adjacent elements in an array are compared in pairs, and the elements with smaller values or Unicode codes are sorted forward.

Specific implementation guidance is as follows:

  1. Compare two adjacent elements, if the former is larger than the latter, then swap places;
  2. After the first round, the value of the last element is the largest;
  3. And then round two, but you don’t have to compare the last element;
  4. Except for the first round, each subsequent round has one less comparison than the previous round;

The specific implementation

var bubbleSort = function (arr){
  var i, j, m;
  var len = arr.length;
  if (len <= 1) {
    return arr;
  }

  for (i=0; i<len- 1; i++) {
    for (j=0; j<len-i- 1; j++) {
      if (arr[j] > arr[j+1]) {
        m = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = m; }}}return arr;
};
Copy the code

Algorithm to improve

If the order of the array is bubbling, or if it is done only a few times, then the subsequent comparison work is unnecessary. How to improve the above algorithm?

After a loop comparison is completed, if no swap has occurred, the array is considered to have achieved its desired effect and the next round of comparison is not required.

var bubbleSort = function (arr){
  var start = +new Date(a);var i, j, m, noswap;
  var len = arr.length;
  if (len <= 1) {
    return arr;
  }

  for (i=0; i<len- 1; i++) {
    noswap = true;
    for (j=0; j<len-i- 1; j++) {
      if (arr[j] > arr[j+1]) {
        m = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = m;
        noswap = false; }}if (noswap) {
      break; }}// When the length of arR is longer, the time difference is more obvious
  console.log(+new Date() - start);
  return arr;
};
Copy the code

Time complexity analysis

Time complexity is analyzed in the worst case, that is, if the table to be sorted is completely in reverse order. Assuming there are n elements in the array, the first round needs to compare N-1 times, the second round needs to compare N-2 times, the third round needs to compare N-3 times, and so on, the last round needs to compare 1 time, a total of N-1 rounds, so it is an arithmetic sequence, using the arithmetic sequence summation formula, can calculate the following time complexity:

So the total time is O(n ^ 2).



If you think this article is good, share it with your friends