乐趣区

关于前端:你确定懂冒泡排序用动画的方式讲懂冒泡排序及其优化方式

点击在线浏览,体验更好 链接
古代 JavaScript 高级小册 链接
深入浅出 Dart 链接
古代 TypeScript 高级小册 链接

基本概念

冒泡排序是一种根底的排序算法。其根本思维是通过一直地比拟相邻元素并在必要时进行替换,将最大(或最小)的元素 ” 冒 ” 到序列的一端。

排序步骤

先来感触到冒泡排序的步骤吧

jcode

以数组 [5, 3, 8, 4, 6] 为例,冒泡排序的步骤如下:

  • 第一轮排序:

比拟相邻的元素。第一次比拟 5 和 3,5 大于 3,替换它们两个,数组变成 [3, 5, 8, 4, 6];接着比拟 5 和 8,5 小于 8,不必替换,而后比拟 8 和 4,8 大于 4,替换,数组变为 [3, 5, 4, 8, 6];最初比拟 8 和 6,8 大于 6,替换,数组变为 [3, 5, 4, 6, 8]。这样,第一轮比拟完结后,最大的数 8 被排到了最初。

  • 第二轮排序:

再次从前向后比拟相邻的元素,这次因为 8 曾经是最大的元素在开端,所以不再参加比拟。先比拟 3 和 5,3 小于 5,不必替换;而后比拟 5 和 4,5 大于 4,替换,数组变为 [3, 4, 5, 6, 8];接着比拟 5 和 6,5 小于 6,不必替换。这样,第二轮排序完结,第二大的元素 6 也排到了它应该在的地位。

  • 后续轮排序:

如此重复进行,每一轮比拟的元素对都比上一轮少一对。直至实现所有的排序。

最终,数组 [5, 3, 8, 4, 6] 被排序为 [3, 4, 5, 6, 8]

冒泡排序的实现

let array = [5, 3, 8, 4, 6];

for(let i = 0; i < array.length; i++) {for(let j = 0; j < array.length - i - 1; j++) {if(array[j] > array[j + 1]) {
      // 替换元素
      let temp = array[j];
      array[j] = array[j + 1];
      array[j + 1] = temp;
    }
  }
}

console.log(array);  // 输入: [3, 

4, 5, 6, 8]

此算法的工夫复杂度为 O(n^2),因而在解决大量数据时可能效率较低。

优化策略

替换标记

如果在一次遍历过程中没有产生过替换,那么意味着序列曾经是有序的,不须要持续排序。咱们能够通过设置一个标记来优化算法。如果在某次遍历中没有产生替换,则间接完结排序。

这个优化对于曾经局部有序的序列来说,能够大幅度提高效率。

let array = [5, 3, 8, 4, 6];
let swapped = true;

while(swapped) {
  swapped = false;
  for(let i = 0; i < array.length - 1; i++) {if(array[i] > array[i + 1]) {let temp = array[i];
      array[i] = array[i + 1];
      array[i + 1] = temp;
      swapped = true;
    }
  }
}

console.log(array);  // 输入: [3, 4, 5, 6, 8]

双向冒泡排序

一趟遍历只能确保最大(或最小)的数被移到序列一端,在双向冒泡排序中,一趟遍历包含了两个过程,一个从头至尾,一个从尾至头,这样就能确保在一趟遍历后,最大和最小的数都被移到了正确的地位。

let array = [5, 3, 8, 4, 6];
let swapped;
let start = 0;
let end = array.length - 1;

while(start < end) {for(let i = start; i < end; i++) {if(array[i] > array[i + 1]) {let temp = array[i];
      array[i] = array[i + 1];
      array[i + 1] = temp;
      swapped = i;
    }
  }
  end = swapped;

  for(let i = end; i > start; i--) {if(array[i] < array[i - 1]) {let temp = array[i];
      array[i] = array[i - 1];
      array[i - 1] = temp;
      swapped = i;
    }
  }
  start = swapped;
}

console.log(array);  // 输入: [3, 4, 5, 6, 8]

记录上次替换的地位

在理论的数据序列中,尾部的有序序列通常不只一个,因而咱们能够记住最初一次替换产生的地位,下一次比拟到这个地位即可。

let array = [5, 3, 8, 4, 6];
let lastExchangeIndex = 0;
let sortBorder = array.length - 1;

for(let i =

 0; i < array.length - 1; i++) {
  let isSorted = true;
  for(let j = 0; j < sortBorder; j++) {if(array[j] > array[j + 1]) {let temp = array[j];
      array[j] = array[j + 1];
      array[j + 1] = temp;
      
      isSorted = false;
      lastExchangeIndex = j;
    }
  }
  sortBorder = lastExchangeIndex;
  if(isSorted) {break;}
}

console.log(array);  // 输入: [3, 4, 5, 6, 8]
退出移动版