JS玩转算法之冒泡排序

JS玩转算法之冒泡排序

冒泡排序是计算机科学中的一种相对简单的排序算法。本文从自然界中的“冒泡”现象延伸到冒泡排序算法中，详细介绍了冒泡排序的实现原理。

自然界中的冒泡

自然界中的水泡在上浮时会逐渐变大。原因在于，水下的压强随着水深增加而增大，较小的气泡受到较大的压强，因而体积变小；而气泡在上浮过程中随着深度减小，所受压强也逐渐减小，因此体积逐渐变大。

代码中的冒泡

我们可以将自然界中的水泡理解成代码中的数组中的每一个数。在冒泡排序的实现过程中，我们从数组的第一个元素开始，依次与后面的每一个元素进行比较。如果当前元素比后面的元素大，就将其交换位置，否则保持不变。这样，经过一轮比较之后，数组中的最后一个数就是整个数组中最大的数。

以下就是用 JavaScript 代码实现的一次“冒泡”：

function getMaxNumByBubble(array) {
  // 这里的循环次数是 array.length - 1，因为最后一个数不需要和任何数进行比较
  for (let i = 0; i < array.length - 1; i++) {
    // 如果前者比后者大，则将两者的位置进行交换
    if (array[i] > array[i + 1]) {
      swap(array, i, i + 1);
    }
  }
}

// 交换位置的工具函数
function swap(arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

我们来验证下 getMaxNumByBubble 方法，通过冒泡的方式，将数组arr中最大的数移至最后一位

const arr = [10, 4, 3, 1, 7, 9, 8];
getMaxNumByBubble(arr);
console.log(arr); // [4, 3, 1, 7, 9, 8, 10]

可以看到 getMaxNumByBubble 成功将数组中最大的数移到了最后一位；我们可以继续执行 getMaxNumByBubble 方法，看看会得到什么～

getMaxNumByBubble(arr2); // [4, 3, 1, 7, 8, 9, 10]
getMaxNumByBubble(arr2); // [3, 1, 4, 7, 8, 9, 10]
getMaxNumByBubble(arr2); // [1, 3, 4, 7, 8, 9, 10]

我们可以看到，在执行了3次循环后，得到了一个升序的数组，这其实就是一个冒泡排序的过程，也体现了冒泡排序的核心思想，每次冒泡都只管筛选出一个最大的数，循环一定的次数后，一个数组自然会变成有序数组。那么，外循环的次数是由什么决定的呢？

影响外循环次数的因素

实际上，循环次数和数组的长度以及数组元素的混乱程度有关，下面我们通过两个例子来说明这一点。

数组的混乱程度

下面介绍三个长度相同的数组，它们的混乱程度不同。将它们变为有序数组所需要的循环次数也不同。在最坏的情况下需要循环 n - 1 次，示例如下：


// 这是一个已经排好序的数组，循环 0 次
const arr1 = [1, 2, 3, 4, 5, 6, 7];

// 这是一个部分有序的数组，需要执行 getMaxNumByBubble 方法 2 次，才可变成有序数组
const arr2 = [1, 2, 3, 4, 7, 6, 5];
getMaxNumByBubble(arr2);  // [1, 2, 3, 4, 6, 5, 7]
getMaxNumByBubble(arr2);  // [1, 2, 3, 4, 5, 6, 7]

// 这是一个完全倒序的数组，需要执行 getMaxNumByBubble 方法 6 次，才可变成有序数组
const arr3 = [7, 6, 5, 4, 3, 2, 1];
getMaxNumByBubble(arr3);  // [6, 5, 4, 3, 2, 1, 7]
getMaxNumByBubble(arr3);  // [5, 4, 3, 2, 1, 6, 7]
getMaxNumByBubble(arr3);  // [4, 3, 2, 1, 5, 6, 7]
getMaxNumByBubble(arr3);  // [3, 2, 1, 4, 5, 6, 7]
getMaxNumByBubble(arr3);  // [2, 1, 3, 4, 5, 6, 7]
getMaxNumByBubble(arr3);  // [1, 2, 3, 4, 5, 6, 7]

数组长度

下面介绍三个混乱程度相同的数组，它们的长度不同。将它们变为有序数组所需的循环次数也不同。在最坏的情况下需要循环 n - 1 次，示例如下：


// 这是一个完全倒序的数组，需要执行 getMaxNumByBubble 方法 6 次，才可变成有序数组
const arr4 = [7, 6, 5, 4, 3, 2, 1];
getMaxNumByBubble(arr4);  // [6, 5, 4, 3, 2, 1, 7]
getMaxNumByBubble(arr4);  // [5, 4, 3, 2, 1, 6, 7]
getMaxNumByBubble(arr4);  // [4, 3, 2, 1, 5, 6, 7]
getMaxNumByBubble(arr4);  // [3, 2, 1, 4, 5, 6, 7]
getMaxNumByBubble(arr4);  // [2, 1, 3, 4, 5, 6, 7]
getMaxNumByBubble(arr4);  // [1, 2, 3, 4, 5, 6, 7]

// 这是一个完全倒序的数组，需要执行 getMaxNumByBubble 方法 4 次，才可变成有序数组
const arr5 = [7, 6, 5, 4, 3];
getMaxNumByBubble(arr5);  // [6, 5, 4, 3, 7]
getMaxNumByBubble(arr5);  // [5, 4, 3, 6, 7]
getMaxNumByBubble(arr5);  // [4, 3, 5, 6, 7]
getMaxNumByBubble(arr5);  // [3, 4, 5, 6, 7]

// 这是一个完全倒序的数组，需要执行 getMaxNumByBubble 方法 3 次，才可变成有序数组
const arr6 = [7, 6, 5, 4];
getMaxNumByBubble(arr6);  // [6, 5, 4, 7]
getMaxNumByBubble(arr6);  // [5, 4, 6, 7]
getMaxNumByBubble(arr6);  // [4, 5, 6, 7]
  • 可以看出，循环次数主要受数组长度和混乱程度的影响。最坏的情况下（数组中的每一个数都比后一个数大），冒泡排序需要循环执行 n - 1 次。用代码来表示就是：
function bubbleSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    // getMaxNumByBubble
    for (let j = 0; j < array.length - 1; j++) {
      if (array[j] > array[j + 1]) {
        swap(array, j, j + 1);
      }
    }
  }
}

刚上面也提到了，这个算法是为了包含最坏的情况实现的，那么如果不是最坏的情况，该算法可以做哪些优化呢？

优化算法

减小内循环的边界

  • 在每执行一次冒泡后（也就是执行 getMaxNumByBubble），数组的最后一位或者多位可能已经是由当前数组中最大的几个数组成的有序部分。我们给代码添加一些注释来看下执行的过程

function bubbleSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    console.log(`----------第 ${i + 1} 轮冒泡-----------`);

    for (let j = 0; j < array.length - 1; j++) {
      console.log(`第 ${j + 1} 次内循环`);
      if (array[j] > array[j + 1]) {
        console.log(`${array[j]} 和 ${array[j + 1]} 交换，大值的索引为 ${j}`)
        swap(array, j, j + 1);
        console.log(`交换后数组为`, array);
      }
    }
    console.log('');
  }
}

  • 代码执行结果如下：


    WechatIMG489.png

  • 我们可以从上图中看出，数组[3, 2, 1, 4, 5]在第一轮排序的过程中，交换了2次后，索引 1 后面的数已经变为有序[3, 4, 5]，但还是执行了第3次和第4次循环，没有意义；同样在进行第二轮的时候，交换了1次，数组已全部变为有序，仍执行了后面3次无意义的循环。为了减少无意义的内循环，将每次发生交换时大值对应的索引记录下来，等这轮冒泡结束之后，将内循环的边界改为该索引，下一轮循环时将不会再对已经有序的部分比较了，优化后代码如下：


// 优化内循环边界后的代码

function bubbleSort(array) {
  let innerLoopBoundary = array.length - 1;
  let swapIndex = 0;
  for (let i = 0; i < array.length - 1; i++) {
    console.log(`----------第 ${i + 1} 轮冒泡-----------`);
    for (let j = 0; j < innerLoopBoundary; j++) {
      console.log(`第 ${j + 1} 次内循环`);
      if (array[j] > array[j + 1]) {
        console.log(`${array[j]} 和 ${array[j + 1]} 交换，大值的索引为 ${j}`)
        swap(array, j, j + 1);
        swapIndex = j;
        console.log(`交换后数组为`, array);
      }
    }
    innerLoopBoundary = swapIndex;
    console.log('');
  }
}

  • 优化后代码执行结果如下：


    WechatIMG490.png

  • 我们发现，只优化了第2轮无意义的循环，第一轮的2次无意义的循环并没有被优化。这是因为我们必须要完整的循环完一轮后，才能知道最后一次交换的索引是多少，所以我们可以得出一个结论：（内循环边界 = 内循环总次数 - 上一轮冒泡最后一次交换时大值对应的索引）

减少外循环的次数

  • 还是上面那个例子，我们看下完整的执行结果


    WechatIMG491.png

从上面的运行结果可以看出，在执行第 2 次外循环后，数组已经完全有序，但仍然执行了两次无意义的外循环。所以我们可以在每次外循环之前，先判断一下数组是否已经是有序的了，如果是有序的，就不需要再执行外循环了，优化后代码如下：


// 优化外循环后的代码

function bubbleSort(array) {
  let innerLoopBoundary = array.length - 1;
  let swapIndex = 0;
  for (let i = 0; i < array.length - 1; i++) {
    console.log(`----------第 ${i + 1} 轮冒泡-----------`);
    // 标志位，用来标识是否在内循环中做过交换
    let isSorted = true;
    for (let j = 0; j < innerLoopBoundary; j++) {
      console.log(`第 ${j + 1} 次内循环`);
      if (array[j] > array[j + 1]) {
        console.log(`${array[j]} 和 ${array[j + 1]} 交换，大值的索引为 ${j}`)
        swap(array, j, j + 1);
        swapIndex = j;
        isSorted = false;
        console.log(`交换后数组为`, array);
      }
    }

    innerLoopBoundary = swapIndex;

    // 如果为 true，则说明内循环中没做过交换，数组已经有序，跳出后续没意义的循环
    if (isSorted) {
      break;
    }
    console.log('');
  }
}

  • 执行结果如下：


    WechatIMG492.png

  • 可以看到优化后的算法减少了一次外循环，仍然执行了第 3 轮冒泡；这是因为 isSorted 标志位只有在上一轮完全有序后，本轮才不会发生交换，才不会被改变。所以第 3 轮是必须要执行的，该方法优化不掉

总结

本文简单推导了下冒泡排序，提供了两种优化该算法的思路：通过减小内循环的边界和减少外循环的次数来优化算法，可以减少无意义的循环次数，提高算法效率。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,732评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,496评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,264评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,807评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,806评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,675评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,029评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,683评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,704评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,666评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,773评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,413评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,016评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,978评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,204评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,083评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,503评论 2赞 343