Comics: What is Bubble Sort? https://juejin.cn/post/6844903688415215624

conventional

let arr = [5.8.6.3.9.2.1.7];
// The outer loop controls the number of rounds. Each time it finds a maximum, it replaces the maximum to the end of the array
let len = arr.length - 1 // We need to subtract 1, because we have j+1.
for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i; j++) {  // We need to subtract an I here, because round I is already sorted at the end of the array.
        if (arr[j] > arr[j + 1]) { // We need to replace the uncle after the array
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // Es6 destruct transforms array positions without defining additional variables.}}}console.log(arr); // [1, 2, 3, 5, 6, 7, 8, 9]
Copy the code

To optimize the

This version of the code made a small change to use the Boolean variable flag as a flag. If the elements are swapped in this order, the sequence is out of order; If there is no element exchange, it means that the sequence is in order, directly out of the big loop

Bubble sort always executes (n-1)+(n-2)+(n-3)+.. +2+1, but if the sorting has already been completed or the input is an ordered array, then the following comparison will be unnecessary. To avoid this situation, we add a flag to check whether the sorting has been completed in the middle (i.e. whether the element swap has occurred).

function bubbleSort (arr) {
  let len = arr.length - 1
  for (let i = 0; i < len; i++) {
    let flag = true;
    for (let j = 0; j < len - i; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false; // If the element is swapped, the sequence is out of order.
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }}if (flag) break;
  }
  return arr;
}
Copy the code

variant

For bubble sort, can we pass in a second argument (function) that controls ascending and descending order?

function buddle_sort(arr,fn){
    let len = arr.length - 1
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i; j++) {
            if (fn(arr[j], arr[j + 1) >0) {  //arr[j] -arr [j + 1]>0 is greater than 0 ascending, less than 0 descending
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }}}}let arr=[5.8.6.3.9.2.1.7]
​
buddle_sort(arr, (a, b) = > a - b)
console.log(arr)//[1, 2, 3, 5, 6, 7, 8, 9]
​
buddle_sort(arr, (a, b) = > b - a)
console.log(arr)// [9, 8, 7, 6, 5, 3, 2, 1]
Copy the code

This also line

function buddle_sort(arr,fn){
    let len = arr.length - 1
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i; j++) {
            if (fn(arr[j], arr[j + 1]) {// Take the judgment out of the way
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }}}}let arr=[5.8.6.3.9.2.1.7]
​
buddle_sort(arr, (a, b) = > a - b>0) // The value of ab is greater than 0
console.log(arr)//[1, 2, 3, 5, 6, 7, 8, 9]
​
buddle_sort(arr, (a, b) = > a - b<0) // The value of ab is greater than 0
console.log(arr)// [9, 8, 7, 6, 5, 3, 2, 1]
Copy the code