冒泡排序

2019-03-31

似乎生活中常常会遇到这种情况，你去一家公司面试，前面面的都挺好，你觉得你对基础的了解很好，进阶知识也都答上来了，然后面试官说，”那么好吧，就写一个最简单的冒泡算法看看吧。”

？？？我头发。我leetcode上刷了100题，你叫我写冒泡算法？

为了应对这种情况，本文列举几种冒泡算法仅供参考。

简单冒泡：

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

这种没有什么好说的了。

进阶简单冒泡

const bubble = arr => {
  let i = arr.length - 1;
  while (i > 0) {
    let pos = 0;
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        pos = j;
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
    i = pos;
  }
  return arr;
};

记住上次交换的位置，该位置后的都是已经排好序的，下次冒泡时到该位置停止，若pos等于0，则说明全部排序完成。

进一步优化

为了避免一些极端的情况，可以正向反向冒泡同时进行，并记录位置，代码略。

图示

bubble