本文作者:文蔺
本文地址:http://www.wemlion.com/2016/algo-bubble-sort/
本文由 @文蔺 创作,转载请保留此声明。
所有权利保留,请勿用于商业目的。

从基础入手。前面学习了插入排序选择排序

接下来看冒泡排序。

依然假设手上有 N 张扑克牌,记作 cards。

第一步,先比较第 1 张与第 2 张,如果第 1 张比第 2 张大,则将两者调换位置;

第二步,重复上面的方法,比较第 2 张、第 3 张;

……

第 (n - 1) 步,比较第 (n - 1) 张、第 n 张,若第 (n - 1) 张比第 n 张大,则将两者调换位置。

仔细想下,发现没有?这样 (n - 1) 个步骤下来,整个数组中最大数已经被顺利推到最右侧啦!也就是说,现在第 n 个数已经是最大的。这就是冒泡排序叫“冒泡”的原因。

那么接下来,我们只需要对前面的 (n - 1) 个数再进行同样的 (n - 2) 次操作,找到第二大的数放在第 (n - 1) 个位置上。

最后的实现如下:

const bubbleSort = (cards) => {
cards = cards.slice(0);

let len = cards.length;
let temp = 0;

for (let i = len - 1; i >= 0; i--) {

for (let j = 0; j < len - i; j++) {

if (cards[j] > cards[j + 1]) {
temp = cards[j + 1];
cards[j + 1] = cards[j];
cards[j] = temp;
}
}
}

return cards;
};

仅仅看循环次数,评估下冒泡排序的复杂度。很简单,因为每次需要 (i - 1) 步的两两对比,因此总的时间是:

(n - 1) + (n - 2) + ... + (2 - 1) + (1 - 1) = n * (n - 1) / 2

复杂度为 O(n^n)。不过,在最坏的情况下,交换操作也是 O(n^n),这对数组来说,还是有些可怕。

本文作者:文蔺
本文地址:http://www.wemlion.com/2016/algo-bubble-sort/
转载请注明来源