Mean time complexity O(n²)

Worst-case time complexity O(n²)

Optimal time complexity (after optimization) O(n)

1. Bubble sort, as one of the most basic sorting algorithms, must be familiar with everyone, simple and crude;

function bubbling(list){ for(let i = 0; i < list.length; i++){ for(let j = 0; j < list.length; J++) {if (the list [j] > list [j + 1]) {/ / smallest const temp = list [j]; list[j] = list[j+1]; list[j+1] = temp; } } } return list; }Copy the code

2, sometimes we find that when the original array is an array to be sorted, such as [1,2,3,5,4], in fact, one loop has completed the sorting, the subsequent loop is futile, so we need to intercept the useless outer loop;

This is order n.

function bubbling(list){ for(let i = 0; i < list.length; i++){ let flag = false; For (let j = 0; j < list.length; J ++){if(list[j] > list[j]){// Const temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; flag = true; } } if(! flag) break; } return list; } const exampleList = [1,2,3,5,4]; bubbling(exampleList)Copy the code

Before optimization

The optimized

3, optimal version, reduce the number of internal cycles;

function bubbling(list){ let len = list.length - 1; for(let i = 0; i < list.length - 1; i++){ let flag = false; // let lastIndex = 0; for(let j = 0; j < len; J ++){if(list[j] > list[j]){// Const temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; flag = true; lastIndex = j; } console.log(j); } len = lastIndex; if(! flag) break; Console. log(' ${I} time ', list); } return list; }Copy the code

Before optimization

The optimized

If you’re careful, you’ll notice that after the 0, the last position doesn’t change, after the 1, the last two positions don’t change, and after the 2, the last three positions don’t change, so there’s no need to compare the last few elements in the inner loop;

We record the position of the last element exchanged in each inner loop. The next inner loop can be interrupted when it reaches this position.

From the above two pictures, it can be clearly seen that the inner loop has been circulated many times less, so as to achieve the effect of optimization.

Two optimizations, the first is to optimize the outermost loop, the second is to optimize the inner loop;