冒泡排序

冒泡排序是一种简单的比较排序，其排序方式有点像自然界中水泡上升的过程，虽说冒泡排序在开发当中不会去使用，但是对于以后理解算法会有很大的帮助，冒泡排序如果不看懂它的排序过程直接读代码还是难理解的，接下来就让我们进入排序篇的第一个排序——冒泡排序

动画演示

思路

考虑一下，现在我们有下面这样一堆数，5、0、8、2，1、4、7、2、5，我们如何才能在不使用js提供的数组方法的情况下对这一堆数据进行由小到大的排序。大部分人可能这样想，先拿第一个数和第二个数比较，如果第一个数比第二个数大的话就交换两个数的位置，以此类推，直到到最后一个数，此时最后一个数就是最大的了，然后再重复此操作，但这一次最后面的那个数不参与排序，剩余的元素按此方法交换之后倒数第二个数是第二大的，直到只剩下一个数，这个时候整个数组不就是有序的了吗？没错，这种排序算法就是冒泡排序。说是这么说可是如何实现这个过程，我想大家在第一次写的时候也犯了难，首先我我们要准备一个交换的函数，如下：

  /**
  * @param {number[]} arr - 要操作的数组
  * @param {number} a - 要交换元素的下标
  * @param {number} b - 要交换元素的下标
  * @description 交换所提供下标元素的位置
  */
  function swap(arr, a, b) {
    const temp = arr[a]; // 用临时变量保存a下标的值
    arr[a] = arr[b];
    arr[b] = temp;
  }

冒泡排序排序过程如下：

  /**
  *@param {number[]} arr - 需要排序的数组
  */
  function bubbleSort(arr) {
    const n = arr.length; // 改数组属性值为局部变量，提高反问速度
    for(let i = 1; i < n; i++) {
      for (let j = 0; j < n-i; j++) { // 注意这里的n-i，这个循环没次都做完第n-i个元素都是最大的（本轮）
        if(arr[j] > arr[j+1]) {
          swap(arr, j, j+1);
        }
      }
    }
  }

冒泡排序是不是很简单，你别看它代码短，时间复杂度可达到了惊人的O( $n^2$)。

优化

了解冒泡排序过程之后，很容易的发现冒泡排序在比较上面花了大量的时间，每一轮两两之间都会比较，有没有这样一种情况:

[1, 2, 3, 4, 5, 6, 7, 9, 8]

在前面我们都没有交换元素，只有到了最后两个元素的时候我们才交换元素，之后的所有操作都不会交换元素，也就是说，只要有一轮循环结束我们没有交换元素，那么这一轮所有的元素就是有序的，比如上面这个数组1-7都是有序的，我们只需在每一轮的开始设置一个标志，默认为true代表这一轮所遍历的元素是有序的，如果中途有交换操作我们就把它设置为false，如果一轮下来标志没有变我们就结束函数，因为已经有序了。

    /**
  *@param {number[]} arr - 需要排序的数组
  */
  function bubbleSort(arr) {
    const n = arr.length; // 改数组属性值为局部变量，提高反问速度
    for(let i = 1; i < n; i++) {
      // 添加标志，默认为true
      let hasSort = true;
      for (let j = 0; j < n-i; j++) { // 注意这里的n-i，这个循环没次都做完第n-i个元素都是最大的（本轮）
        if(arr[j] > arr[j+1]) {
          swap(arr, j, j+1);
          if(hasSort) hasSort = false; // 如果为true才设置，减少不必要的赋值操作
        }
      }
      if(hasSort) break; // 跳出外部循环结束排序；
    }
  }

优化2

再想一想还有哪个地方可以优化的，我们可以注意到，在第二个for循环中n-i在每一轮中都是一个不变的值，我们可以用一个常量k保存起来,这个常量的值等于每一轮最后一个数的下标（每一轮最大的那个数的下标），代码修改如下：

    /**
  *@param {number[]} arr - 需要排序的数组
  */
  function bubbleSort(arr) {
    const n = arr.length; // 改数组属性值为局部变量，提高反问速度
    let k = n - 1, swapPos = 0;
    for(let i = 1; i < n; i++) {
      // 添加标志，默认为true
      let hasSort = true;
      for (let j = 0; j < k; j++) { // 注意这里的n-i，这个循环没次都做完第n-i个元素都是最大的（本轮）
        if(arr[j] > arr[j+1]) {
          swap(arr, j, j+1);
          if(hasSort) hasSort = false; // 如果为true才设置，减少不必要的赋值操作
          swapPos = j; // 使用一个中间变量保存最后一个值
        }
      }
      if(hasSort) break; // 跳出外部循环结束排序；
      k = swapPos // 本轮结束后把这个值给k
    }
  }

鸡尾酒排序

鸡尾酒排序是一种双向的冒泡排序，也叫涟漪排序。鸡尾酒排序是冒泡排序的一种变形，此算法与冒泡排序的不同之处在于排序时是以双向在序列中进行排序的。

// 鸡尾酒排序(冒泡排序变形)
export function cocktailSort(arr) {
  let left = 0;
  let right = arr.length - 1;
  let index;
  while (left < right) {
    // 大的排在后面
    for (let i = left; i < right; i++) {
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1);
        index = i;
      }
    }
    // 第一轮排完之后index右侧的数字都是有序的,只需从index开始排就行（重点）
    right = index;
    // 小的排前面
    for (let i = right; i > left; i--) {
      if (arr[i] < arr[i - 1]) {
        swap(arr, i, i - 1);
        index = i;
      }
    }
    left = index;
  }
}

总结

冒泡排序是一种十分直观的排序，书写过程也不难，但是要理解冒泡排序的过程，冒泡排序是一种比较排序，通过数两两之间进行比较，如果前面的数比后面的数大，就交换位置，这样比较下来会产生一个结果就是，每一轮结束之后，最后一个数都是最大的，这样当我们进行下一轮排序的时候就不再对最后一个数进行比较，直到每一轮都比较完，此时的数组就是有序的了。在这个排序过程当中我们发现，在某些时候数组已经是有序的情况下还是比较，这个时候我们需要在每一轮开始的时候，设置一个标志变量（默认true），这个变量代表本轮数组是否是有序的，如果在本轮发生了交换操作，我们就把这个变量赋值为false，在结尾的时候我们再判断这个变量是否为true，如果为true就表明没有发生改变，这样的话这一轮就是有效的，再加上冒泡排序会使每一轮最后一个数都大于前面的数，所以整个数组就是有序的，这个时候我们就可以跳出外层循环，从而结束排序，当然这个时候直接间return也是可以个。还有一个优化的点就是在某一轮比较中如果只在中间的某一个位置发生交换操作，其他地方都没变，这个时候我们可以断定，在最后一个交换操作之后的元素都是有序的，这个时候保存这个值，作为下一轮遍历的结尾。说了这么多，发现冒泡排序也没有想象中的那么简单，里面需要理解的东西还是挺多的，理解了冒泡排序，之后的排序算法会好理解很多。