JS提供的最简单的排序方法：

  1. arr.sort((a,b) => {
  2.     return a - b
  3. })

思路：冒泡排序的过程，就是从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置，反之不动。

每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。

冒泡排序不会因为后面的顺序已经拍好了就停下，所以我们需要优化。

基本冒泡思路编码实现

  1. function bubbleSort(arr) {
  2.     // 缓存数组长度
  3.     const len = arr.length  
  4.     // 外层循环用于控制从头到尾的比较+交换到底有多少轮
  5.     for(let i=0;i<len;i++) {  
  6.         // 内层循环用于完成每一轮遍历过程中的重复比较+交换
  7.         for(let j=0;j<len-1;j++) {
  8.             // 若相邻元素前面的数比后面的大
  9.             if(arr[j] > arr[j+1]) {  
  10.                 // 交换两者
  11.                 [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
  12.             }
  13.         }
  14.     }
  15.     // 返回数组
  16.     return arr
  17. }

基本冒泡思路的改进

在上面的示例中，我们已经初步分析出了这样一个结论：在冒泡排序的过程中，有一些”动作“是不太必要的。比如数组在已经有序的情况下，为什么还要强行再从头到尾再对数组做一次遍历？

这背后的根本原因是，我们忽略了这样一个事实：随着外层循环的进行，数组尾部的元素会渐渐变得有序——当我们走完第1轮循环的时候，最大的元素被排到了数组末尾；走完第2轮循环的时候，第2大的元素被排到了数组倒数第2位；走完第3轮循环的时候，第3大的元素被排到了数组倒数第3位……以此类推，走完第 n 轮循环的时候，数组的后 n 个元素就已经是有序的。

楼上基本冒泡思路的问题在于，没有区别处理这一部分已经有序的元素，而是把它和未排序的部分做了无差别的处理，进而造成了许多不必要的比较。

为了避免这些冗余的比较动作，我们需要规避掉数组中的后 n 个元素，对应的代码可以这样写：

  1. function betterBubbleSort(arr) {
  2.     const len = arr.length  
  3.     for(let i=0;i<len;i++) {
  4.         // 注意差别在这行，我们对内层循环的范围作了限制
  5.         for(let j=0;j<len-1-i;j++) {
  6.             if(arr[j] > arr[j+1]) {
  7.                 [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
  8.             }
  9.         }
  10.     }
  11.     return arr
  12. }

面向“最好情况”的进一步改进

冒泡排序通过进一步的改进，确实是可以做到最好情况下 O(n)复杂度的，这里我先把代码给大家写出来（注意解析在注释里）：

  1. function betterBubbleSort(arr) {
  2.     const len = arr.length  
  4.     for(let i=0;i<len;i++) {
  5.         // 区别在这里，我们加了一个标志位
  6.         let flag = false
  7.         for(let j=0;j<len-1-i;j++) {
  8.             if(arr[j] > arr[j+1]) {
  9.                 [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
  10.                 // 只要发生了一次交换，就修改标志位
  11.                 flag = true
  12.             }
  13.         }
  15.         // 若一次交换也没发生，则说明数组有序，直接放过
  16.         if(flag === false)  return arr;
  17.     }
  18.     return arr
  19. }

冒泡排序的时间复杂度

我们分最好、最坏和平均来看：

  • 最好时间复杂度：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 O(n)
  • 最坏时间复杂度： 它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n^2)
  • 平均时间复杂度：这个东西比较难搞，它涉及到一些概率论的知识。实际面试的时候也不会有面试官摁着你让你算这个，这里记住平均时间复杂度是 O(n^2) 即可。

    对于每一种排序算法的时间复杂度，大家对计算依据有了解即可，重点在于记忆。面试的时候不要靠现场推导，要靠直觉+条件反射。