【JavaScript】前端必备经典算法(二)：冒泡排序

今天我们就来扒扒冒泡排序的原理到底是啥？

首先我们可以先写出简易的冒泡排序： 以下仅为示例，边界处理可自行添加

function bubbleSort(arr) {
    for(let i = 0 ; i < arr.length - 1; i++) {
      for(let j = 0; j < arr.length - i - 1; j++) {
        if(arr[j] > arr[j+1]) {
          arr[j] = arr[j] + arr[j+1];
          arr[j+1] = arr[j] - arr[j+1];
          arr[j] = arr[j] - arr[j+1];
        }
      }
    }
    return arr;
  }

排序的关键在于遍历，我们来理解一下两次for循环都做了什么事情

首先，第一遍循环很好理解，我们数组里面每一个元素都需要有一次遍历的机会，因为最后一个元素不需要再拿出来进行比较（后面没有元素可以进行比较了），所以 i < arr.length - 1

在第二次循环中，j 的起点依然是从0开始，这是因为第一次循环只是给每个元素进行比较的机会，实际上进行比较的元素是 arr[j] 和它的后一个元素 arr[j+1]

而 j < arr.length - i - 1怎么理解呢？冒泡排序意思就是如果前一个元素的值比后一个大，那么它们会交换位置，也就是如果我数组中刚好第一个元素就是最大的，那么这个元素就会一直 冒泡 到最后一个位置,也就是说，我第一次循环比较完之后，会确定一个最大值且在数组的最后，第二次循环比较后会确定一个第二大的值，那么这样就很好理解为什么 j < arr.length - i - 1， 随着 i的增大，意味着确定的值会越来越多，并且都是按顺序排好的

在第二次循环中比较 arr[j] 和 arr[j + 1]

我们判断的是如果 arr[j] 比 arr[j + 1] 大，那么它们交换位置，有两种方式

arr[j] = arr[j] + arr[j+1]; // 通过arr[j]保存它们的和
arr[j+1] = arr[j] - arr[j+1]; // 和减去较小的值得到较大的赋值给arr[j+1]
arr[j] = arr[j] - arr[j+1]; // 用它们的和减去arr[j+1]得到较小值赋值给arr[j]
// 通过这三步完成两者之间值得转换

如果你觉得这种交换方式很绕，也可以通过以下这种方式

let temp == arr[j]; // 通过一个变量存储较大值
arr[j] = arr[j+1]; // 把较小值转移到arr[j]上面
arr[j+1] = temp; // 把储存得值给arr[j+1]
// 这种方式较为简单易理解

简单解析完了之后，我们可以对这个函数做一些简单的边界处理

function bubbleSort(arr) {
// 如果传入的参数不是一个数组，或者这个数组长度没有进行比较的意义，我们抛出一个错误，错误信息可自定义
    if(!Array.isArray(arr) || arr.length <= 1) {
      throw new Error('Type Error');
    }
// 在确定满足排序的条件后，保存数组的长度，不必在每一次for循环中都去获取数组的长度，提升效率
    const arrLen = arr.length;
    for(let i = 0 ; i < arrLen - 1; i++) {
      for(let j = 0; j < arrLen - i - 1; j++) {
        if(arr[j] > arr[j+1]) {
          arr[j] = arr[j] + arr[j+1];
          arr[j+1] = arr[j] - arr[j+1];
          arr[j] = arr[j] - arr[j+1];
        }
      }
    }
    return arr;
  }

总结：虽然在大部分人日常的开发中，算法并没有很大的用处，但是学习一些简单的算法能够提升我们的思维，或许在下一场面试中你就用到了呢